trotter 0.5.0

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. Their distinguishing properties can be summarised in the following table.

	Order Important	Order Not Important
Repetition Not Allowed	Permutations	Combinations
Repetition Allowed	Amalgams	Selections

All of these classes can be used similarly to the way Permutations was 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].