trotter 0.5.1

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

Introduction

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 of objects taken from a specified set.

For example, the following programme creates a pseudo-list "containing" all the 3-permutations of the first five letters and reports some information.

import "package:trotter/trotter.dart";
void main() {
  var perms3 = new Permutations(3, "abcde".split(""));
  print("There are ${perms3.length} 3-permutations of the objects in ${perms3.elements}.");
  print("The first 3-permutation is ${perms3[0]}.");
  print("The first three 3-permutations are: ${perms3.range(0, 3)}.");
}

Output

There are 60 3-permutations of the objects in [a, b, c, d, e].
The first 3-permutation is [a, b, c].
The first three 3-permutations are: [[a, b, c], [a, c, b], [c, a, b]].

The classes defined in trotter technically provide a mapping between integers and the structures contained within a pseudo-list; they do not store the structures in memory. This allows us to work with pseudo-lists "containing" very large numbers of arrangements with very little overhead. For example, consider the following programme that works with a very large list of permutations.

import "package:trotter/trotter.dart";
void main() {
  var perms10 = new Permutations(10, "abcdefghijklmno".split(""));
  print("There are ${perms10.length} 10-permutations of the first 15 letters.");
  print("The 10,000,000,000th permutation 'stored' in perms10 is ${perms10[9999999999]}.");
}

Output

There are 10897286400 10-permutations of the first 15 letters.
The 10,000,000,000th permutation 'stored' in perms10 is [m, k, j, d, e, g, f, i, c, n].

Classes

Trotter contains four classes for working with some items taken from a list.

• Permutations: Order is important; items cannot be chosen more than once.
• Combinations: Order is not important; items cannot be chosen more than once.
• Amalgams: Order is important; items can be chosen more than once.
• Selections: Order is not important; items can be chosen more than once.

All of these classes can be used similarly to the way Permutations is used in the examples above.

Further, a class Subsets exists to create a pseudo-list of all the subsets of objects stored in a list. For example, the following programme creates a pseudo-list containing all the subsets (combinations of any size) created from the first five letters.

import "package:trotter/trotter.dart";
void main() {
  var subs = new Subsets("abcde".split(""));
  print("There are ${subs.length} subsets of the objects in ${subs.elements}.");
  print("The first subset is the empty set: ${subs[0]}.");
  print("The tenth subset in subs contains the elements ${subs[9]}.");
}

Output

There are 32 subsets of the objects in [a, b, c, d, e].
The first subset is the empty set: [].
The tenth subset in subs contains the elements [a, d].