trotter 0.9.1

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

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

  • Fixed an error introduced during the changes made for 0.9.0.

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!");
}

1. Depend on it

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


dependencies:
  trotter: "^0.9.1"

2. Install it

You can install packages from the command line:

with pub:


$ pub get

with Flutter:


$ flutter packages get

Alternatively, your editor might support pub get or packages 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.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 failed Download trotter 0.5.2 archive
0.5.1 Sep 27, 2014 failed Download trotter 0.5.1 archive
0.5.0 Sep 27, 2014 failed Download trotter 0.5.0 archive

Analysis

We analyzed this package on Apr 23, 2018, and provided a score, details, and suggestions below. Analysis was completed with status completed using:

  • Dart: 2.0.0-dev.49.0
  • pana: 0.10.6

Scores

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

Platforms

Detected platforms: Flutter, web, other

No platform restriction found in primary library package:trotter/trotter.dart.

Suggestions

  • Package is pre-v1 release.

    While there is nothing inherently wrong with versions of 0.*.*, it usually means that the author is still experimenting with the general direction API.

  • Fix analysis and formatting issues.

    Analysis or formatting checks reported 7 hints.

    Run dartfmt to format lib/src/amalgams.dart.

    Run dartfmt to format lib/src/combinations.dart.

    Similar analysis of the following files failed:

    • lib/src/compounds.dart (hint)
    • lib/src/permutations.dart (hint)
    • lib/src/selections.dart (hint)
    • lib/src/subsets.dart (hint)
    • lib/src/trotter_helpers.dart (hint)
  • Use analysis_options.yaml.

    Rename old .analysis_options file to analysis_options.yaml.

Dependencies

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