Trotter는 순열, 조합 및 부분집합과 같은 조합 구조를 다루기 쉽게 해주는 Dart 패키지입니다. 모든 요소를 메모리에 실체화하지 않고도 이러한 수학적 구조를 효율적으로 반복하고 조작할 수 있습니다. 알고리즘 문제 해결 및 이산수학 관련 교육용 애플리케이션에 적합하며, 모바일, 웹, 데스크톱을 포함한 주요 플랫폼을 지원합니다. 패키지는 가볍고 조합 관련 작업에서 명확성과 사용 편의성을 위해 설계되었습니다.
사용 사례
알고리즘 테스트를 위한 순열 생성
데이터 분석에서 조합 만들기
이산 수학에서 부분 집합 패턴 탐색
조합 퍼즐 해결
조합론의 교육적 설명
주요 기능
메모리 효율적인 가짜 목록
순열을 위한 Iterable 지원
조합 및 부분 집합 지원
깔끔하고 직관적인 API
크로스 플랫폼 호환성
적합한 대상
수학 교육자
알고리즘 개발자
경쟁 프로그래밍
데이터 과학 워크플로
조합론 배우기
고려 사항
매우 큰 데이터 세트에 최적화되지 않음
조합 구조에 국한됨
조합론에 대한 이해가 필요합니다
내장 시리얼라이제이션 없음
중간 크기의 입력을 가진 시나리오에서 가장 적합함
원본 README
연결된 소스 저장소의 README 원문 스냅샷입니다. 최신 내용은 저장소에서 확인하세요.
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 list of items.
The order of arrangements is based on the the order produced by the
Steinhaus–Johnson–Trotter algorithm
for ordering permutations, which I have generalized to combinations and arrangements
that allow for replacement after item selection.
The pseudo-list classes available 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).
Demos
To see trotter in action:
Play Falco Shapes, a little puzzle
based on Marsha Falco's game of Set.
Explore the huge number of permutations of letters of the alphabet with
Permutation Products.
Using trotter
Include the following dependency in your pubspec.yaml:
dependencies:trotter:^2.2.2
Then, to import the library:
import'package:trotter/trotter.dart'
The basic classes
Combinations
A combination is a selection of items for which order is not
important and items are not replaced after being selected.
The Combinations class "contains" all combinations of a set of items.
Example:
final bagOfItems = characters('abcde'),
combinations = Combinations(3, bagOfItems);
for (final (i, combination) incombinations().indexed) {
print('[$i]: $combination');
}
A permutation is a selection of items for which order is important
and items are not replaced after being selected.
The Permutations class "contains" all permutations of a set of items.
Example:
final bagOfItems = characters('abcde'), permutations = Permutations(3, bagOfItems);
for (final (i, permutation) inpermutations().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. In fact, if we get the permutations of
all the specified items, e.g. final permutations = Permutations(bagOfItems.length, bagOfItems);
in the above code, the arrangement of permutations is exactly what would
have resulted from applying the S-J-T algorithm. The algorithms in this library
have an advantage in that they do not iterate through all k - 1 permutations in
order to determine the kth permutation, however.)
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.
The Compositions class "contains" all compositions of a set of items.
Here are all the compositions of three items taken from a bag of five items:
Example:
final bagOfItems = characters('abcde'), compositions = Compositions(3, bagOfItems);
for (final (i, composition) incompositions().indexed) {
print('[$i]: $composition');
}
An amalgam (or permutation with replacement) is a selection of items for
which order is important and items are replaced after being selected.
The Amalgams class "contains" all amalgams of a set of items.
Example:
final bagOfItems = characters('abcde'), amalgams = Amalgams(3, bagOfItems);
for (final (i, amalgam) inamalgams().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.
The Subsets class "contains" all subsets of a set of items.
Example:
final bagOfItems = characters('abcde'), subsets = Subsets(bagOfItems);
for (final (i, subset) insubsets().indexed) {
print('[$i]: $subset');
}
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.
The Compounds class "contains" all compounds of a set of items.
Example:
final bagOfItems = characters('abcde'), compounds = Compounds(bagOfItems);
for (final (i, compound) incompounds().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]
Large indices
Arrangement numbers often grow very quickly. For example, consider the number
of 10-permutations of the letters of the alphabet:
Example:
final largeBagOfItems = characters('abcdefghijklmnopqrstuvwxyz'),
permutations = Permutations(10, largeBagOfItems);
print(permutations);
Pseudo-list containing all 19275223968000 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].
Wow! 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 largeBagOfItems = characters('abcdefghijklmnopqrstuvwxyz'),
permutations = Permutations(10, largeBagOfItems),
permutationOfInterest = characters('algorithms'),
index = permutations.indexOf(permutationOfInterest);
print('The index of $permutationOfInterest is $index.');
print('permutations[$index]: ${permutations[index]}');
The index of [a, l, g, o, r, i, t, h, m, s] is 6831894769563.
permutations[6831894769563]: [a, l, g, o, r, i, t, h, m, s]
Wow! That's almost seven trillion! Luckily we didn't need to perform that
search using brute force!
Since we sometimes can be working with indices so large they cannot be
represented using a 64 bit int, indexing and length are implemented using BigInt.
Example:
final largeBagOfItems = characters('abcdefghijklmnopqrstuvwxyz'),
compounds = Compounds(largeBagOfItems);
print('There are ${compounds.length} compounds of these letters!');
BigInt lastCompoundIndex = compounds.length - BigInt.one;
print('The last compound is ${compounds[lastCompoundIndex]}.');
There are 1096259850353149530222034277 compounds of these letters!
The last compound is [b, a, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z].
Unless you're immortal, don't use compounds().last to access the last compound in the previous example!
Syntactic sugar
Lists
trotter provides extensions that allow us to generate combinatorics
arrangements directly from lists...
Example:
final subsets = [1, 2, 3, 4, 5].subsets();
for (final subset insubsets()) {
print(subset);
}