trotter 0.9.0

  • README.md
  • CHANGELOG.md
  • Example
  • Installing
  • Versions
  • 34

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.9.0

  • Cleaned up and simplified the code so that the structures extend Lists more naturally. (Structures extend ListBase now instead of Iterable.)
  • Should be backwards compatable in that code that works in previous versions should also work in this version.
  • Structures should now behave better with List methods like map, where, every and so on.

0.8.5

  • Cleaned up the code so that the library may be used in strong mode.
  • Added subset of the functionality associated with Iterables (first, last, any, every, forEach etc.). Some functionality that would be redundant (e.g. isEmpty) or less meaningful/useful (e.g. fold) neglected. Since structures we can represent can "contain" a huge number of arrangements, we need to be careful about using methods that iterate over the structures (like any, every, forEach).

0.8.1

  • Added the Compounds 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.

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.5.1

Improved the documentation; minor bug fixes.

0.5.0

First Dart release: support for classes:

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

example/trotter_example.dart

import "package:trotter/trotter.dart";

void main() {
  print("\n" * 10);
  print("Welcome to trotter, a library for working with structures");
  print("commonly encoundered in combinatorics.\n\n");

  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.");
  print("(For combinations, order is NOT important and items are NOT replaced.)\n");
  var combos = new Combinations(3, bagOfItems);
  for (List combo in combos) {
    print(combo);
  }

  print("\n\nHere are all the permutations of three items taken from this bag.");
  print("(For permutations, order IS important and items are NOT replaced.)\n");
  var permos = new Permutations(3, bagOfItems);
  for (int i = 0; i < permos.length; i++) {
    print("$i\t${permos[i]}");
  }

  print("\n\nHere are all the 'selections' of three items taken from this bag.");
  print("(For selections, order is NOT important and items ARE replaced.)\n");
  var sels = new Selections(3, bagOfItems);
  for (int i = 0; i < sels.length; i++) {
    print("$i\t${sels[i]}");
  }

  print("\n\nHere are all the 'amalgams' of three items taken from this bag.");
  print("(For amalgams, order IS important and items ARE replaced.)\n");
  var ams = new Amalgams(3, bagOfItems);
  for (int i = 0; i < ams.length; i++) {
    print("$i\t${ams[i]}");
  }

  print("\n\nHere are all the subsets of three items taken from this bag.");
  print("(For subsets, order is NOT important, items are NOT replaced and the");
  print("number of items taken is not specified.)\n");
  var subs = new Subsets(bagOfItems);
  for (int i = 0; i < subs.length; i++) {
    print("$i\t${subs[i]}");
  }

  print("\n\nItems can be accessed using the 'in' keyword. Take care not to do this");
  print("when dealing with large pseudo-lists! There is only so much time and");
  print("memory in this universe!\n");
  for (List x in sels) print(x);

  print("\n(We could have accomplished this using the 'forEach' method too...)\n");
  sels.forEach(print);

  print("Much of the funtionality associated with Dart 'iterables' work on these");
  print("combinatorics structures too.\n");

  print("sels.first: ${sels.first}");
  print("sels.last: ${sels.last}");
  print("sels.firstWhere((List x) => x. contains(\"d\")): ${
    sels.firstWhere((x) => x. contains("d"))}");
  print("sels.any((x) => x. contains(\"f\")): ${
    sels.any((x) => x. contains("f"))}");

  print("\n\nBetter to be more specific using the `range` method:\n");

  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");
  print("The world 'ALGORITHMS'is a 10-permutation of letters: what is its position?");

  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]}.\n");

  print("With replacement, we can select more items than there are items:\n");

  var q = new Amalgams(3, ["a", "b"]);
  for (int i = 0; i < q.length; i++) {
    print("$i\t->\t${q[i]}\t->\t${q.indexOf(q[i])}");
  }

  print("\nWe can also work with negative indices. Of course, the indices are");
  print("restricted in the definitions of the inverse functions:\n");

  for (int i = -q.length; i < 0; i++) {
    print("$i\t->\t${q[i]}\t->\t${q.indexOf(q[i])}");
  }

  print("\nThe structures extend lists. We can use such methods associated with lists");
  print("as map, where, any, every and so on. Of course, this means we need to be");
  print("careful when dealing with structures containing a arge number of elements!");
}

Use this package as a library

1. Depend on it

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


dependencies:
  trotter: ^0.9.0

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
1.0.2 Aug 10, 2018 Go to the documentation of trotter 1.0.2 Download trotter 1.0.2 archive
1.0.1 Aug 8, 2018 Go to the documentation of trotter 1.0.1 Download trotter 1.0.1 archive
1.0.0 Aug 3, 2018 Go to the documentation of trotter 1.0.0 Download trotter 1.0.0 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

All 12 versions...

Popularity:
Describes how popular the package is relative to other packages. [more]
69
Health:
Code health derived from static analysis. [more]
0
Maintenance:
Reflects how tidy and up-to-date the package is. [more]
0
Overall:
Weighted score of the above. [more]
34
Learn more about scoring.

The package version is not analyzed, because it does not support Dart 2. Until this is resolved, the package will receive a health and maintenance score of 0.

Issues and suggestions

Support Dart 2 in pubspec.yaml.

The SDK constraint in pubspec.yaml doesn't allow the Dart 2.0.0 release. For information about upgrading it to be Dart 2 compatible, please see https://www.dartlang.org/dart-2#migration.

Dependencies

Package Constraint Resolved Available
Direct dependencies
Dart SDK >=1.20.1 <2.0.0