trotter 2.2.0

Class definitions for pseudo-lists that simplify working with structures commonly encountered in combinatorics such as permutations, combinations and subsets.

example/example.md

Example

Large indices

Arrangement numbers often grow very quickly. For example, consider the number of 10-permutations of the letters of the alphabet:

Example:

final largeBagOfItems = characters("abcdefghijklmnopqrstuvwxyz"),
  permutations = Permutations(10, largeBagOfItems);
print(permutations);

copied to clipboard

Pseudo-list containing all 19275223968000 10-permutations of items from [a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z].

copied to clipboard

Wow! That"s a lot of permutations! Don"t iterate over them all!

Notice that the word algorithms is a 10-permutation of the letters of the alphabet. What is the index of this permutation in our list of permutations?

Example:

final largeBagOfItems = characters("abcdefghijklmnopqrstuvwxyz"),
    permutations = Permutations(10, largeBagOfItems),
    permutationOfInterest = characters("algorithms"),
    index = permutations.indexOf(permutationOfInterest);
print("The index of $permutationOfInterest is $index.");
print("permutations[$index]: ${permutations[index]}");

copied to clipboard

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

copied to clipboard

Wow! That"s almost seven trillion! Luckily we didn"t need to perform that search using brute force!

Since we sometimes can be working with indexes so large they cannot be represented using a 64 bit int, indexing and length are implemented using BigInt.

Example:

final largeBagOfItems = characters("abcdefghijklmnopqrstuvwxyz"),
    compounds = Compounds(largeBagOfItems);
print("There are ${compounds.length} compounds of these letters!");
BigInt lastCompoundIndex = compounds.length - BigInt.one;
print("The last compound is ${compounds[lastCompoundIndex]}.");

copied to clipboard

There are 1096259850353149530222034277 compounds of these letters!
The last compound is [b, a, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z].

copied to clipboard

Unless you"re immortal, don"t use compounds().last to access the last compound in the previous example!