Welcome to trotter, a library that simplifies working with meta-arrangements commonly encountered in combinatorics, such as arrangements of combinations and permutations.
Trotter gives the developer access to pseudo-lists that "contain" all selections (combinations, permutations, etc.) of objects taken from a specified set of items, which can be helpful in "embarrassingly parallel" distributed workloads, steganography and other contexts.
The order of arrangements is inspired by that of 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 in trotter are:
- Combinations
- Permutations
- Compositions (combinations with replacement)
- Amalgams (permutations with replacement)
- Subsets (combinations with unspecified number of items taken)
- Compounds (permutations with unspecified number of items taken)
Using Trotter
Add the package to your project:
dart pub add trotter
Then, to import the library:
import 'package:trotter/trotter.dart'
The Basic Classes
The following classes can be conceptually thought of as "containers" of combinatorics selections of elements. Under the hood, they provide mappings between indices and the selections, which means that they consume a very small amount of space, even if they conceptually "contain" vast numbers of arrangements of elements.
We can access individual arrangements through indexing on an instance (using BigInt indices where necessary), or iterate through generated arrangements by calling the instance.
Combinations
A combination is a selection of items for which order is not important and items are not replaced after being selected.
Example:
final combinations = Combinations(
items: {'a', 'b', 'c', 'd', 'e'},
take: 3,
);
for (final (i, combination) in combinations().indexed) {
print('[$i]: $combination');
}
[0]: [a, b, c]
[1]: [a, b, d]
[2]: [a, b, e]
[3]: [a, c, d]
[4]: [a, c, e]
[5]: [a, d, e]
[6]: [b, c, d]
[7]: [b, c, e]
[8]: [b, d, e]
[9]: [c, d, e]
Permutations
A permutation is a selection of items for which order is important and items are not replaced after being selected.
Example:
final permutations = Permutations(
items: {'a', 'b', 'c', 'd', 'e'},
take: 3,
);
for (final (i, permutation) in permutations().indexed) {
print('[$i]: $permutation');
}
[0]: [a, b, c]
[1]: [a, c, b]
[2]: [c, a, b]
[3]: [c, b, a]
[4]: [b, c, a]
[5]: [b, a, c]
[6]: [a, b, d]
[7]: [a, d, b]
[8]: [d, a, b]
[9]: [d, b, a]
[10]: [b, d, a]
[11]: [b, a, d]
[12]: [a, b, e]
[13]: [a, e, b]
[14]: [e, a, b]
[15]: [e, b, a]
[16]: [b, e, a]
[17]: [b, a, e]
[18]: [a, c, d]
[19]: [a, d, c]
[20]: [d, a, c]
[21]: [d, c, a]
[22]: [c, d, a]
[23]: [c, a, d]
[24]: [a, c, e]
[25]: [a, e, c]
[26]: [e, a, c]
[27]: [e, c, a]
[28]: [c, e, a]
[29]: [c, a, e]
[30]: [a, d, e]
[31]: [a, e, d]
[32]: [e, a, d]
[33]: [e, d, a]
[34]: [d, e, a]
[35]: [d, a, e]
[36]: [b, c, d]
[37]: [b, d, c]
[38]: [d, b, c]
[39]: [d, c, b]
[40]: [c, d, b]
[41]: [c, b, d]
[42]: [b, c, e]
[43]: [b, e, c]
[44]: [e, b, c]
[45]: [e, c, b]
[46]: [c, e, b]
[47]: [c, b, e]
[48]: [b, d, e]
[49]: [b, e, d]
[50]: [e, b, d]
[51]: [e, d, b]
[52]: [d, e, b]
[53]: [d, b, e]
[54]: [c, d, e]
[55]: [c, e, d]
[56]: [e, c, d]
[57]: [e, d, c]
[58]: [d, e, c]
[59]: [d, c, e]
Notice that this library arranges permutations similarly to the way the Steinhaus-Johnson-Trotter algorithm arranges permutations (if we get the permutations of all the specified items, in the above code, the arrangement of permutations is exactly what would have resulted from applying the SJT algorithm). Of course, the algorithms in this library do not iterate through all k - 1 permutations in order to determine the kth permutation.
Compositions
A composition (or combination with replacement) is a selection of items for which order is not important and items are replaced after being selected.
Example:
final compositions = Compositions(
items: {'a', 'b', 'c', 'd', 'e'},
take: 3,
);
for (final (i, composition) in compositions().indexed) {
print('[$i]: $composition');
}
[0]: [a, a, a]
[1]: [a, a, b]
[2]: [a, a, c]
[3]: [a, a, d]
[4]: [a, a, e]
[5]: [a, b, b]
[6]: [a, b, c]
[7]: [a, b, d]
[8]: [a, b, e]
[9]: [a, c, c]
[10]: [a, c, d]
[11]: [a, c, e]
[12]: [a, d, d]
[13]: [a, d, e]
[14]: [a, e, e]
[15]: [b, b, b]
[16]: [b, b, c]
[17]: [b, b, d]
[18]: [b, b, e]
[19]: [b, c, c]
[20]: [b, c, d]
[21]: [b, c, e]
[22]: [b, d, d]
[23]: [b, d, e]
[24]: [b, e, e]
[25]: [c, c, c]
[26]: [c, c, d]
[27]: [c, c, e]
[28]: [c, d, d]
[29]: [c, d, e]
[30]: [c, e, e]
[31]: [d, d, d]
[32]: [d, d, e]
[33]: [d, e, e]
[34]: [e, e, e]
Amalgams
An amalgam (or permutation with replacement) is a selection of items for which order is important and items are replaced after being selected.
Example:
final amalgams = Amalgams(
items: {'a', 'b', 'c', 'd', 'e'},
take: 3,
);
for (final (i, amalgam) in amalgams().indexed) {
print('[$i]: $amalgam');
}
[0]: [a, a, a]
[1]: [a, a, b]
[2]: [a, a, c]
[3]: [a, a, d]
[4]: [a, a, e]
[5]: [a, b, a]
[6]: [a, b, b]
[7]: [a, b, c]
[8]: [a, b, d]
[9]: [a, b, e]
[10]: [a, c, a]
[11]: [a, c, b]
[12]: [a, c, c]
[13]: [a, c, d]
[14]: [a, c, e]
[15]: [a, d, a]
[16]: [a, d, b]
[17]: [a, d, c]
[18]: [a, d, d]
[19]: [a, d, e]
[20]: [a, e, a]
[21]: [a, e, b]
[22]: [a, e, c]
[23]: [a, e, d]
[24]: [a, e, e]
[25]: [b, a, a]
[26]: [b, a, b]
[27]: [b, a, c]
[28]: [b, a, d]
[29]: [b, a, e]
[30]: [b, b, a]
[31]: [b, b, b]
[32]: [b, b, c]
[33]: [b, b, d]
[34]: [b, b, e]
[35]: [b, c, a]
[36]: [b, c, b]
[37]: [b, c, c]
[38]: [b, c, d]
[39]: [b, c, e]
[40]: [b, d, a]
[41]: [b, d, b]
[42]: [b, d, c]
[43]: [b, d, d]
[44]: [b, d, e]
[45]: [b, e, a]
[46]: [b, e, b]
[47]: [b, e, c]
[48]: [b, e, d]
[49]: [b, e, e]
[50]: [c, a, a]
[51]: [c, a, b]
[52]: [c, a, c]
[53]: [c, a, d]
[54]: [c, a, e]
[55]: [c, b, a]
[56]: [c, b, b]
[57]: [c, b, c]
[58]: [c, b, d]
[59]: [c, b, e]
[60]: [c, c, a]
[61]: [c, c, b]
[62]: [c, c, c]
[63]: [c, c, d]
[64]: [c, c, e]
[65]: [c, d, a]
[66]: [c, d, b]
[67]: [c, d, c]
[68]: [c, d, d]
[69]: [c, d, e]
[70]: [c, e, a]
[71]: [c, e, b]
[72]: [c, e, c]
[73]: [c, e, d]
[74]: [c, e, e]
[75]: [d, a, a]
[76]: [d, a, b]
[77]: [d, a, c]
[78]: [d, a, d]
[79]: [d, a, e]
[80]: [d, b, a]
[81]: [d, b, b]
[82]: [d, b, c]
[83]: [d, b, d]
[84]: [d, b, e]
[85]: [d, c, a]
[86]: [d, c, b]
[87]: [d, c, c]
[88]: [d, c, d]
[89]: [d, c, e]
[90]: [d, d, a]
[91]: [d, d, b]
[92]: [d, d, c]
[93]: [d, d, d]
[94]: [d, d, e]
[95]: [d, e, a]
[96]: [d, e, b]
[97]: [d, e, c]
[98]: [d, e, d]
[99]: [d, e, e]
[100]: [e, a, a]
[101]: [e, a, b]
[102]: [e, a, c]
[103]: [e, a, d]
[104]: [e, a, e]
[105]: [e, b, a]
[106]: [e, b, b]
[107]: [e, b, c]
[108]: [e, b, d]
[109]: [e, b, e]
[110]: [e, c, a]
[111]: [e, c, b]
[112]: [e, c, c]
[113]: [e, c, d]
[114]: [e, c, e]
[115]: [e, d, a]
[116]: [e, d, b]
[117]: [e, d, c]
[118]: [e, d, d]
[119]: [e, d, e]
[120]: [e, e, a]
[121]: [e, e, b]
[122]: [e, e, c]
[123]: [e, e, d]
[124]: [e, e, e]
Subsets
A subset (or combination of unspecified length) is a selection of items for which order is not important, items are not replaced and the number of items is not specified.
Example:
final subsets = Subsets(items: {'a', 'b', 'c', 'd', 'e'});
for (final (i, subset) in subsets().indexed) {
print('[$i]: $subset');
}
[0]: []
[1]: [a]
[2]: [b]
[3]: [a, b]
[4]: [c]
[5]: [a, c]
[6]: [b, c]
[7]: [a, b, c]
[8]: [d]
[9]: [a, d]
[10]: [b, d]
[11]: [a, b, d]
[12]: [c, d]
[13]: [a, c, d]
[14]: [b, c, d]
[15]: [a, b, c, d]
[16]: [e]
[17]: [a, e]
[18]: [b, e]
[19]: [a, b, e]
[20]: [c, e]
[21]: [a, c, e]
[22]: [b, c, e]
[23]: [a, b, c, e]
[24]: [d, e]
[25]: [a, d, e]
[26]: [b, d, e]
[27]: [a, b, d, e]
[28]: [c, d, e]
[29]: [a, c, d, e]
[30]: [b, c, d, e]
[31]: [a, b, c, d, e]
Compounds
A compound (or permutation of unspecified length) is a selection of items for which order is important, items are not replaced and the number of items is not specified.
Example:
final compounds = Compounds(items: {'a', 'b', 'c', 'd', 'e'});
for (final (i, compound) in compounds().indexed) {
print('[$i]: $compound');
}
[0]: []
[1]: [a]
[2]: [b]
[3]: [c]
[4]: [d]
[5]: [e]
[6]: [a, b]
[7]: [b, a]
[8]: [a, c]
[9]: [c, a]
[10]: [a, d]
[11]: [d, a]
[12]: [a, e]
[13]: [e, a]
[14]: [b, c]
[15]: [c, b]
[16]: [b, d]
[17]: [d, b]
[18]: [b, e]
[19]: [e, b]
[20]: [c, d]
[21]: [d, c]
[22]: [c, e]
[23]: [e, c]
[24]: [d, e]
[25]: [e, d]
[26]: [a, b, c]
[27]: [a, c, b]
[28]: [c, a, b]
[29]: [c, b, a]
[30]: [b, c, a]
[31]: [b, a, c]
[32]: [a, b, d]
[33]: [a, d, b]
[34]: [d, a, b]
[35]: [d, b, a]
[36]: [b, d, a]
[37]: [b, a, d]
[38]: [a, b, e]
[39]: [a, e, b]
[40]: [e, a, b]
[41]: [e, b, a]
[42]: [b, e, a]
[43]: [b, a, e]
[44]: [a, c, d]
[45]: [a, d, c]
[46]: [d, a, c]
[47]: [d, c, a]
[48]: [c, d, a]
[49]: [c, a, d]
[50]: [a, c, e]
[51]: [a, e, c]
[52]: [e, a, c]
[53]: [e, c, a]
[54]: [c, e, a]
[55]: [c, a, e]
[56]: [a, d, e]
[57]: [a, e, d]
[58]: [e, a, d]
[59]: [e, d, a]
[60]: [d, e, a]
[61]: [d, a, e]
[62]: [b, c, d]
[63]: [b, d, c]
[64]: [d, b, c]
[65]: [d, c, b]
[66]: [c, d, b]
[67]: [c, b, d]
[68]: [b, c, e]
[69]: [b, e, c]
[70]: [e, b, c]
[71]: [e, c, b]
[72]: [c, e, b]
[73]: [c, b, e]
[74]: [b, d, e]
[75]: [b, e, d]
[76]: [e, b, d]
[77]: [e, d, b]
[78]: [d, e, b]
[79]: [d, b, e]
[80]: [c, d, e]
[81]: [c, e, d]
[82]: [e, c, d]
[83]: [e, d, c]
[84]: [d, e, c]
[85]: [d, c, e]
[86]: [a, b, c, d]
[87]: [a, b, d, c]
[88]: [a, d, b, c]
[89]: [d, a, b, c]
[90]: [d, a, c, b]
[91]: [a, d, c, b]
[92]: [a, c, d, b]
[93]: [a, c, b, d]
[94]: [c, a, b, d]
[95]: [c, a, d, b]
[96]: [c, d, a, b]
[97]: [d, c, a, b]
[98]: [d, c, b, a]
[99]: [c, d, b, a]
[100]: [c, b, d, a]
[101]: [c, b, a, d]
[102]: [b, c, a, d]
[103]: [b, c, d, a]
[104]: [b, d, c, a]
[105]: [d, b, c, a]
[106]: [d, b, a, c]
[107]: [b, d, a, c]
[108]: [b, a, d, c]
[109]: [b, a, c, d]
[110]: [a, b, c, e]
[111]: [a, b, e, c]
[112]: [a, e, b, c]
[113]: [e, a, b, c]
[114]: [e, a, c, b]
[115]: [a, e, c, b]
[116]: [a, c, e, b]
[117]: [a, c, b, e]
[118]: [c, a, b, e]
[119]: [c, a, e, b]
[120]: [c, e, a, b]
[121]: [e, c, a, b]
[122]: [e, c, b, a]
[123]: [c, e, b, a]
[124]: [c, b, e, a]
[125]: [c, b, a, e]
[126]: [b, c, a, e]
[127]: [b, c, e, a]
[128]: [b, e, c, a]
[129]: [e, b, c, a]
[130]: [e, b, a, c]
[131]: [b, e, a, c]
[132]: [b, a, e, c]
[133]: [b, a, c, e]
[134]: [a, b, d, e]
[135]: [a, b, e, d]
[136]: [a, e, b, d]
[137]: [e, a, b, d]
[138]: [e, a, d, b]
[139]: [a, e, d, b]
[140]: [a, d, e, b]
[141]: [a, d, b, e]
[142]: [d, a, b, e]
[143]: [d, a, e, b]
[144]: [d, e, a, b]
[145]: [e, d, a, b]
[146]: [e, d, b, a]
[147]: [d, e, b, a]
[148]: [d, b, e, a]
[149]: [d, b, a, e]
[150]: [b, d, a, e]
[151]: [b, d, e, a]
[152]: [b, e, d, a]
[153]: [e, b, d, a]
[154]: [e, b, a, d]
[155]: [b, e, a, d]
[156]: [b, a, e, d]
[157]: [b, a, d, e]
[158]: [a, c, d, e]
[159]: [a, c, e, d]
[160]: [a, e, c, d]
[161]: [e, a, c, d]
[162]: [e, a, d, c]
[163]: [a, e, d, c]
[164]: [a, d, e, c]
[165]: [a, d, c, e]
[166]: [d, a, c, e]
[167]: [d, a, e, c]
[168]: [d, e, a, c]
[169]: [e, d, a, c]
[170]: [e, d, c, a]
[171]: [d, e, c, a]
[172]: [d, c, e, a]
[173]: [d, c, a, e]
[174]: [c, d, a, e]
[175]: [c, d, e, a]
[176]: [c, e, d, a]
[177]: [e, c, d, a]
[178]: [e, c, a, d]
[179]: [c, e, a, d]
[180]: [c, a, e, d]
[181]: [c, a, d, e]
[182]: [b, c, d, e]
[183]: [b, c, e, d]
[184]: [b, e, c, d]
[185]: [e, b, c, d]
[186]: [e, b, d, c]
[187]: [b, e, d, c]
[188]: [b, d, e, c]
[189]: [b, d, c, e]
[190]: [d, b, c, e]
[191]: [d, b, e, c]
[192]: [d, e, b, c]
[193]: [e, d, b, c]
[194]: [e, d, c, b]
[195]: [d, e, c, b]
[196]: [d, c, e, b]
[197]: [d, c, b, e]
[198]: [c, d, b, e]
[199]: [c, d, e, b]
[200]: [c, e, d, b]
[201]: [e, c, d, b]
[202]: [e, c, b, d]
[203]: [c, e, b, d]
[204]: [c, b, e, d]
[205]: [c, b, d, e]
[206]: [a, b, c, d, e]
[207]: [a, b, c, e, d]
[208]: [a, b, e, c, d]
[209]: [a, e, b, c, d]
[210]: [e, a, b, c, d]
[211]: [e, a, b, d, c]
[212]: [a, e, b, d, c]
[213]: [a, b, e, d, c]
[214]: [a, b, d, e, c]
[215]: [a, b, d, c, e]
[216]: [a, d, b, c, e]
[217]: [a, d, b, e, c]
[218]: [a, d, e, b, c]
[219]: [a, e, d, b, c]
[220]: [e, a, d, b, c]
[221]: [e, d, a, b, c]
[222]: [d, e, a, b, c]
[223]: [d, a, e, b, c]
[224]: [d, a, b, e, c]
[225]: [d, a, b, c, e]
[226]: [d, a, c, b, e]
[227]: [d, a, c, e, b]
[228]: [d, a, e, c, b]
[229]: [d, e, a, c, b]
[230]: [e, d, a, c, b]
[231]: [e, a, d, c, b]
[232]: [a, e, d, c, b]
[233]: [a, d, e, c, b]
[234]: [a, d, c, e, b]
[235]: [a, d, c, b, e]
[236]: [a, c, d, b, e]
[237]: [a, c, d, e, b]
[238]: [a, c, e, d, b]
[239]: [a, e, c, d, b]
[240]: [e, a, c, d, b]
[241]: [e, a, c, b, d]
[242]: [a, e, c, b, d]
[243]: [a, c, e, b, d]
[244]: [a, c, b, e, d]
[245]: [a, c, b, d, e]
[246]: [c, a, b, d, e]
[247]: [c, a, b, e, d]
[248]: [c, a, e, b, d]
[249]: [c, e, a, b, d]
[250]: [e, c, a, b, d]
[251]: [e, c, a, d, b]
[252]: [c, e, a, d, b]
[253]: [c, a, e, d, b]
[254]: [c, a, d, e, b]
[255]: [c, a, d, b, e]
[256]: [c, d, a, b, e]
[257]: [c, d, a, e, b]
[258]: [c, d, e, a, b]
[259]: [c, e, d, a, b]
[260]: [e, c, d, a, b]
[261]: [e, d, c, a, b]
[262]: [d, e, c, a, b]
[263]: [d, c, e, a, b]
[264]: [d, c, a, e, b]
[265]: [d, c, a, b, e]
[266]: [d, c, b, a, e]
[267]: [d, c, b, e, a]
[268]: [d, c, e, b, a]
[269]: [d, e, c, b, a]
[270]: [e, d, c, b, a]
[271]: [e, c, d, b, a]
[272]: [c, e, d, b, a]
[273]: [c, d, e, b, a]
[274]: [c, d, b, e, a]
[275]: [c, d, b, a, e]
[276]: [c, b, d, a, e]
[277]: [c, b, d, e, a]
[278]: [c, b, e, d, a]
[279]: [c, e, b, d, a]
[280]: [e, c, b, d, a]
[281]: [e, c, b, a, d]
[282]: [c, e, b, a, d]
[283]: [c, b, e, a, d]
[284]: [c, b, a, e, d]
[285]: [c, b, a, d, e]
[286]: [b, c, a, d, e]
[287]: [b, c, a, e, d]
[288]: [b, c, e, a, d]
[289]: [b, e, c, a, d]
[290]: [e, b, c, a, d]
[291]: [e, b, c, d, a]
[292]: [b, e, c, d, a]
[293]: [b, c, e, d, a]
[294]: [b, c, d, e, a]
[295]: [b, c, d, a, e]
[296]: [b, d, c, a, e]
[297]: [b, d, c, e, a]
[298]: [b, d, e, c, a]
[299]: [b, e, d, c, a]
[300]: [e, b, d, c, a]
[301]: [e, d, b, c, a]
[302]: [d, e, b, c, a]
[303]: [d, b, e, c, a]
[304]: [d, b, c, e, a]
[305]: [d, b, c, a, e]
[306]: [d, b, a, c, e]
[307]: [d, b, a, e, c]
[308]: [d, b, e, a, c]
[309]: [d, e, b, a, c]
[310]: [e, d, b, a, c]
[311]: [e, b, d, a, c]
[312]: [b, e, d, a, c]
[313]: [b, d, e, a, c]
[314]: [b, d, a, e, c]
[315]: [b, d, a, c, e]
[316]: [b, a, d, c, e]
[317]: [b, a, d, e, c]
[318]: [b, a, e, d, c]
[319]: [b, e, a, d, c]
[320]: [e, b, a, d, c]
[321]: [e, b, a, c, d]
[322]: [b, e, a, c, d]
[323]: [b, a, e, c, d]
[324]: [b, a, c, e, d]
[325]: [b, a, c, d, e]
Calling instances
Calling an instance accepts two optional arguments to indicate the indices for which iteration is to start and end. Indexing is wrap-around, so starting and ending at the same index still generates all arrangements.
Example:
final combos = Combinations(items: {1, 2, 3, 4, 5}, take: 3);
print('All combinations:');
for (final (i, c) in combos().indexed) {
print('[$i]: $c');
}
print('\nUntil index 2:');
for (final c in combos(2)) {
print(c);
}
print('\nFrom index 2 to <5:');
for (final c in combos(2, 5)) {
print(c);
}
print('\nAll combinations from index 2 on, wrapping around to <2:');
for (final c in combos(2, 2)) {
print(c);
}
All combinations:
[0]: [1, 2, 3]
[1]: [1, 2, 4]
[2]: [1, 2, 5]
[3]: [1, 3, 4]
[4]: [1, 3, 5]
[5]: [1, 4, 5]
[6]: [2, 3, 4]
[7]: [2, 3, 5]
[8]: [2, 4, 5]
[9]: [3, 4, 5]
Until index 2:
[1, 2, 3]
[1, 2, 4]
From index 2 to <5:
[1, 2, 5]
[1, 3, 4]
[1, 3, 5]
All combinations from index 2 on, wrapping around to <2:
[1, 2, 5]
[1, 3, 4]
[1, 3, 5]
[1, 4, 5]
[2, 3, 4]
[2, 3, 5]
[2, 4, 5]
[3, 4, 5]
[1, 2, 3]
[1, 2, 4]
Large Indices
Arrangement indices often grow very quickly with the number of items to choose from. For example, consider the number of 10-permutations of the letters of the alphabet:
Example:
final letters = 'abcdefghijklmnopqrstuvwxyz'.split(''),
permutations = Permutations(items: letters, take: 10);
print(permutations);
Pseudo-list containing all 19,275,223,968,000 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].
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 letters = 'abcdefghijklmnopqrstuvwxyz'.split(''),
permutations = Permutations(items: letters, take: 10),
needle = 'algorithms'.split(''),
index = permutations.indexOf(needle);
print('The index of $needle is ${addCommas(index)}.');
print('permutations[${addCommas(index)}]: ${permutations[index]}');
The index of [a, l, g, o, r, i, t, h, m, s] is 6,831,894,769,563.
permutations[6,831,894,769,563]: [a, l, g, o, r, i, t, h, m, s]
Because we often deal with such large numbers, this package uses BigInt indices. For example, let's say we want to know the last permutation "contained" in this "large" structure:
Example:
final letters = 'abcdefghijklmnopqrstuvwxyz'.split(''),
permutations = Permutations(items: letters, take: 10),
lastElementIndex = permutations.length - BigInt.one;
print(permutations[lastElementIndex]);
[r, q, s, t, u, v, w, x, y, z]
(Unless you're immortal, don't use permutations().last to access the last compound in this example!)
Syntactic Sugar
Lists & Sets
Trotter provides extensions that allow us to conveniently generate combinatorics arrangements directly from iterables, like lists and sets.
Example:
final subsets = [1, 2, 3, 4].toSubsets();
for (final subset in subsets()) {
print(subset);
}
[]
[1]
[2]
[1, 2]
[3]
[1, 3]
[2, 3]
[1, 2, 3]
[4]
[1, 4]
[2, 4]
[1, 2, 4]
[3, 4]
[1, 3, 4]
[2, 3, 4]
[1, 2, 3, 4]
Example:
final combinations = {1, 2, 3, 4, 5}.toCombinations(take: 3);
for (final combination in combinations()) {
print(combination);
}
[1, 2, 3]
[1, 2, 4]
[1, 2, 5]
[1, 3, 4]
[1, 3, 5]
[1, 4, 5]
[2, 3, 4]
[2, 3, 5]
[2, 4, 5]
[3, 4, 5]
Strings
Similarly, we can conveniently generate combinatorics structures on strings, in which case the string is treated as the set of characters it contains.
Example:
final subsets = 'abcd'.toSubsets();
for (final subset in subsets()) {
print(subset);
}
[]
[a]
[b]
[a, b]
[c]
[a, c]
[b, c]
[a, b, c]
[d]
[a, d]
[b, d]
[a, b, d]
[c, d]
[a, c, d]
[b, c, d]
[a, b, c, d]
final combinations = 'abcde'.toCombinations(take: 3);
for (final combination in combinations()) {
print(combination);
}
[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]
The Importance of Order
Some of the classes (namely Combinations, Subsets and Compositions) are order-agnostic. They thus do not take order into account when checking whether an arrangement is contained or when finding the position of an arrangement.
Example:
final combos = {'a', 'b', 'c', 'd', 'e'}.toCombinations(take: 3);
for (final (i, combo) in combos().indexed) {
print('[$i] $combo');
}
final needle = ['b', 'e', 'd'];
print('\n$needle does not appear to be listed...');
print('$needle is in combos: ${combos.contains(needle)}');
print('$needle is at index: ${combos.indexOf(needle)}');
[0] [a, b, c]
[1] [a, b, d]
[2] [a, b, e]
[3] [a, c, d]
[4] [a, c, e]
[5] [a, d, e]
[6] [b, c, d]
[7] [b, c, e]
[8] [b, d, e]
[9] [c, d, e]
[b, e, d] does not appear to be listed...
[b, e, d] is in combos: true
[b, e, d] is at index: 8
Sampling
We can generate a random sample of elements using the drawSample method:
Example:
final combinations = '12345abcde'.toPermutations(take: 4);
final sample = combinations.drawSample(
10,
seed: 0,
withReplacement: true,
);
for (final combination in sample) {
print(combination.join(''));
}
2a4d
be4d
45b1
ba4e
cb3d
e4c2
ecb4
a3e1
23ad
1d35
The Storage Class
In some use cases (e.g., see fun_with_mastermind), it can be helpful to keep track of which arrangements have been processed. The Storage class can be used to mark this. Storage uses a minimal amount of memory (one bit per arrangement), but is still only suitable for structures "containing" a small to moderate number of arrangements.
Example:
final storage = Storage({'a', 'b', 'c', 'd', 'e'}.toCombinations(take: 3));
for (final c in storage.combinatorics()) {
if (storage.contains(c)) {
print(c);
}
}
print('\nRemoving all combinations containing "b"...\n');
storage.removeWhere((c) => c.contains('b'));
for (final c in storage.combinatorics()) {
if (storage.contains(c)) {
print(c);
}
}
[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]
Removing all combinations containing "b"...
[a, c, d]
[a, c, e]
[a, d, e]
[c, d, e]
Examples
The example folder has several examples of trotter applications, including:
Mastermind
Demonstrates using trotter to solve the game of Mastermind by guessing amalgams of colors and responding to clues, for example:
The secret code: EAEF
| Guess number | Guess | Clues |
|---|---|---|
| 1 | CFBB | ⚪ |
| 2 | DCEE | ⚫⚪ |
| 3 | EBAE | ⚫⚪⚪ |
| 4 | ABED | ⚫⚪ |
| 5 | AEFE | ⚪⚪⚪⚪ |
| 6 | EAEF | ⚫⚫⚫⚫ |
Solved in 6 guesses.
Piggy Sprites
Demonstrates using trotter to generate images of sprites in a web application, such as the combinations of three sprites selected from five:

Permutation Multiplication
Demonstrates using trotter to calculate and locate permutation products:
There are 3,628,800 permutations of the digits 0-9. Here are the first, middle and last ten in the Johnson-Trotter ordering: Index Permutation Cyclic Notation 0 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] () 1 [0, 1, 2, 3, 4, 5, 6, 7, 9, 8] (89) 2 [0, 1, 2, 3, 4, 5, 6, 9, 7, 8] (798) 3 [0, 1, 2, 3, 4, 5, 9, 6, 7, 8] (6987) 4 [0, 1, 2, 3, 4, 9, 5, 6, 7, 8] (59876) 5 [0, 1, 2, 3, 9, 4, 5, 6, 7, 8] (498765) 6 [0, 1, 2, 9, 3, 4, 5, 6, 7, 8] (3987654) 7 [0, 1, 9, 2, 3, 4, 5, 6, 7, 8] (29876543) 8 [0, 9, 1, 2, 3, 4, 5, 6, 7, 8] (198765432) 9 [9, 0, 1, 2, 3, 4, 5, 6, 7, 8] (0987654321) 1,814,400 [3, 2, 1, 0, 4, 5, 6, 7, 8, 9] (03)(12) 1,814,401 [3, 2, 1, 0, 4, 5, 6, 7, 9, 8] (03)(12)(89) 1,814,402 [3, 2, 1, 0, 4, 5, 6, 9, 7, 8] (03)(12)(798) 1,814,403 [3, 2, 1, 0, 4, 5, 9, 6, 7, 8] (03)(12)(6987) 1,814,404 [3, 2, 1, 0, 4, 9, 5, 6, 7, 8] (03)(12)(59876) 1,814,405 [3, 2, 1, 0, 9, 4, 5, 6, 7, 8] (03)(12)(498765) 1,814,406 [3, 2, 1, 9, 0, 4, 5, 6, 7, 8] (03987654)(12) 1,814,407 [3, 2, 9, 1, 0, 4, 5, 6, 7, 8] (0312987654) 1,814,408 [3, 9, 2, 1, 0, 4, 5, 6, 7, 8] (031987654) 1,814,409 [9, 3, 2, 1, 0, 4, 5, 6, 7, 8] (0987654)(13) 3,628,790 [9, 1, 0, 2, 3, 4, 5, 6, 7, 8] (098765432) 3,628,791 [1, 9, 0, 2, 3, 4, 5, 6, 7, 8] (0198765432) 3,628,792 [1, 0, 9, 2, 3, 4, 5, 6, 7, 8] (01)(29876543) 3,628,793 [1, 0, 2, 9, 3, 4, 5, 6, 7, 8] (01)(3987654) 3,628,794 [1, 0, 2, 3, 9, 4, 5, 6, 7, 8] (01)(498765) 3,628,795 [1, 0, 2, 3, 4, 9, 5, 6, 7, 8] (01)(59876) 3,628,796 [1, 0, 2, 3, 4, 5, 9, 6, 7, 8] (01)(6987) 3,628,797 [1, 0, 2, 3, 4, 5, 6, 9, 7, 8] (01)(798) 3,628,798 [1, 0, 2, 3, 4, 5, 6, 7, 9, 8] (01)(89) 3,628,799 [1, 0, 2, 3, 4, 5, 6, 7, 8, 9] (01) Input permutation p in cyclic notation: (58)(1932) 52,063 [0, 1, 2, 4, 8, 6, 9, 7, 5, 3] (348569) 52,064 [0, 1, 2, 4, 8, 9, 6, 7, 5, 3] (34859) 52,065 [0, 1, 2, 4, 9, 8, 6, 7, 5, 3] (349)(58) 52,066 [0, 1, 2, 9, 4, 8, 6, 7, 5, 3] (39)(58) 52,067 [0, 1, 9, 2, 4, 8, 6, 7, 5, 3] (293)(58) 52,068 [0, 9, 1, 2, 4, 8, 6, 7, 5, 3] (1932)(58) <---- Here! 52,069 [9, 0, 1, 2, 4, 8, 6, 7, 5, 3] (09321)(58) 52,070 [9, 0, 1, 2, 8, 4, 6, 7, 5, 3] (09321)(485) 52,071 [0, 9, 1, 2, 8, 4, 6, 7, 5, 3] (1932)(485) 52,072 [0, 1, 9, 2, 8, 4, 6, 7, 5, 3] (293)(485) Input permutation q in cyclic notation: (246)(357) 72,175 [0, 1, 4, 5, 6, 9, 2, 7, 3, 8] (246)(3598) 72,176 [0, 1, 4, 5, 6, 2, 9, 7, 3, 8] (2469835) 72,177 [0, 1, 4, 5, 6, 2, 7, 9, 3, 8] (24679835) 72,178 [0, 1, 4, 5, 6, 2, 7, 3, 9, 8] (246735)(89) 72,179 [0, 1, 4, 5, 6, 2, 7, 3, 8, 9] (246735) 72,180 [0, 1, 4, 5, 6, 7, 2, 3, 8, 9] (246)(357) <---- Here! 72,181 [0, 1, 4, 5, 6, 7, 2, 3, 9, 8] (246)(357)(89) 72,182 [0, 1, 4, 5, 6, 7, 2, 9, 3, 8] (246)(35798) 72,183 [0, 1, 4, 5, 6, 7, 9, 2, 3, 8] (24698357) 72,184 [0, 1, 4, 5, 6, 9, 7, 2, 3, 8] (2467)(3598) The product of p and q is (193857246): 114,183 [0, 4, 8, 6, 7, 1, 9, 2, 5, 3] (147285)(369) 114,184 [0, 4, 8, 6, 7, 9, 1, 2, 5, 3] (147285936) 114,185 [0, 4, 8, 6, 9, 7, 1, 2, 5, 3] (14936)(2857) 114,186 [0, 4, 8, 9, 6, 7, 1, 2, 5, 3] (146)(2857)(39) 114,187 [0, 4, 9, 8, 6, 7, 1, 2, 5, 3] (146)(293857) 114,188 [0, 9, 4, 8, 6, 7, 1, 2, 5, 3] (193857246) <---- Here! 114,189 [9, 0, 4, 8, 6, 7, 1, 2, 5, 3] (0938572461) 114,190 [9, 0, 8, 4, 6, 7, 1, 2, 5, 3] (093461)(2857) 114,191 [0, 9, 8, 4, 6, 7, 1, 2, 5, 3] (19346)(2857) 114,192 [0, 8, 9, 4, 6, 7, 1, 2, 5, 3] (185729346)
Time & Space Complexity
Trotter uses mathematical mapping for ranking (finding the location of a given arrangement), which takes place in O(k), and un-ranking (finding the arrangement at a given location), which takes place in O(k log n). We can thus access element in fairly optimized time. Because trotter maintains no internal state (except for the Storage class), we can query vast containers without risking memory exhaustion.
Disclosure: Use of AI
Trotter was written by a human (at least his mother claims he's human) long before the advent of large language models. From version 3.0.0, AI has been used to assist with bug-checking, edge-case considerations, optimization (e.g., rewriting the original tail-recursion functions as iteration-based functions), test generation and final checks before publication.
Thanks!
Thanks for your interest in this library. Please file any bugs, issues and suggestions here.