trotter 0.8.1

  • README.md
  • CHANGELOG.md
  • Installing
  • Versions
  • --

Welcome to trotter, a Dart library that simplifies working with structures commonly encountered in combinatorics such as combinations and permutations.

Trotter gives the developer access to pseuso-lists that "contain" all arrangements (combinations, permutations, etc.) of objects taken from a specified list of items. The order of arrangements is based on the Steinhaus–Johnson–Trotter algorithm for ordering permutations, which has been generalized to combinations and arrangements that allow for replacement after item selection.

The pseudo-list classes available are:

  • Combinations.
  • Permutations.
  • Selections (combinations with replacement).
  • Amalgams (permutations with replacement).
  • Subsets (combinations of unspecified size).
  • Compounds (permutations of unspecified size).

For example, the following programme creates a pseudo-list "containing" all the 3-combinations of the first five letters.


  print("Here is a bag of items:");

  var bagOfItems = characters("abcde");
  print(bagOfItems);

  print("\n\nHere are all the combinations of three items taken from this bag.");

  var combos = new Combinations(3, bagOfItems);

  for (List combo in combos) {
    print(combo);
  }

And here is the output:


Here is a bag of items:
[a, b, c, d, e]


Here are all the combinations of three items taken from this bag.

[a, b, c]
[a, b, d]
[a, b, e]
[a, c, d]
[a, c, e]
[a, d, e]
[b, c, d]
[b, c, e]
[b, d, e]
[c, d, e]

Technically, the pseudo-list classes encapsulate mappings from integers to various item arrangements and vice versa, and so it is possible for them to "store" - and look up from - a very large number of item arrangements.

Here is an example that shows how we can work with a huge pseudo-list:


var largeBagOfItems = characters("abcdefghijklmnopqrstuvwxyz");
var hugePseudoList = new Permutations(10, largeBagOfItems);

print("\n\nThere are ${hugePseudoList.length} permutatations of 10 letters");
print("taken from the alphabet. Don't try to access them all!!!\n");
print("However, we can access whichever permutations in the pseudo-list");
print("we are interested in. For example, the billionth to the billion-tenth");
print("permutations of these letters are:\n");

for (List x in hugePseudoList.range(999999999, 1000000009)) print(x);

print("\n\nWe can also find the index of a given permutation...\n");

int algorithmsIndex = hugePseudoList.indexOf(
    ["a", "l", "g", "o", "r", "i", "t", "h", "m", "s"]);
print("The index of [a, l, g, o, r, i, t, h, m, s] is $algorithmsIndex.\n");

print("(That's almost seven trillion! Luckily we didn't have to search");
print("through all the permutations!)\n");

print("hugePseudoList[$algorithmsIndex] = ${hugePseudoList[algorithmsIndex]}.");

And here is the output:

There are 19275223968000 permutatations of 10 letters
taken from the alphabet. Don't try to access them all!!!

However, we can access whichever permutations in the pseudo-list
we are interested in. For example, the billionth to the billion-tenth
permutations of these letters are:

[u, i, c, f, g, d, b, e, a, w]
[i, u, c, f, g, d, b, e, a, w]
[i, u, c, f, g, d, b, e, w, a]
[i, u, c, f, g, d, b, w, e, a]
[i, u, c, f, g, d, w, b, e, a]
[i, u, c, f, g, w, d, b, e, a]
[i, u, c, f, w, g, d, b, e, a]
[i, u, c, w, f, g, d, b, e, a]
[i, u, w, c, f, g, d, b, e, a]
[i, w, u, c, f, g, d, b, e, a]


We can also find the index of a given permutation...

The index of [a, l, g, o, r, i, t, h, m, s] is 6831894769563.

(That's almost seven trillion! Luckily we didn't have to search
through all the permutations!)

hugePseudoList[6831894769563] = [a, l, g, o, r, i, t, h, m, s].

For more information and examples of use, see the Trotter wiki.

Enjoy!

Changelog

0.5.0

First Dart release: support for classes:

  • Permutations
  • Combinations
  • Amalgams (permutations with replacement during arranging)
  • Selections (combinations with replacement during arranging)
  • Subsets

0.5.1

Improved the documentation; minor bug fixes.

0.8.0

  • Added inverses to all the functions so that we can look up arrangements non iteratively (now possible to look up values in arbitrarily large pseudo-lists; this library was incomplete without this functionality!).
  • Made the code more readable. Made a few minor tweaks to the existing code.

0.8.1

  • Added the Coumpounds class (permutations of unspecified size).
  • Added the contains method for all classes.
  • Corrected indexOf behaviour for when arrangements that don't exist are passed as arguments; returns -1 if the arrangement is not in the pseudo-list.

Use this package as a library

1. Depend on it

Add this to your package's pubspec.yaml file:


dependencies:
  trotter: "^0.8.1"

2. Install it

You can install packages from the command line:

with pub:


$ pub get

Alternatively, your editor might support pub get. Check the docs for your editor to learn more.

3. Import it

Now in your Dart code, you can use:


      import 'package:trotter/trotter.dart';
  
Version Uploaded Documentation Archive
0.9.5 May 7, 2018 Go to the documentation of trotter 0.9.5 Download trotter 0.9.5 archive
0.9.1 Dec 10, 2017 Go to the documentation of trotter 0.9.1 Download trotter 0.9.1 archive
0.9.0 Dec 7, 2017 Go to the documentation of trotter 0.9.0 Download trotter 0.9.0 archive
0.8.5 Jan 13, 2017 Go to the documentation of trotter 0.8.5 Download trotter 0.8.5 archive
0.8.1 Feb 10, 2016 Go to the documentation of trotter 0.8.1 Download trotter 0.8.1 archive
0.8.0 Feb 8, 2016 Go to the documentation of trotter 0.8.0 Download trotter 0.8.0 archive
0.5.2 Nov 26, 2014 Go to the documentation of trotter 0.5.2 Download trotter 0.5.2 archive
0.5.1 Sep 27, 2014 Go to the documentation of trotter 0.5.1 Download trotter 0.5.1 archive
0.5.0 Sep 27, 2014 Go to the documentation of trotter 0.5.0 Download trotter 0.5.0 archive

Analysis

This package version is not analyzed, because it is more than two years old. Check the latest stable version for its analysis.