Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit00f7502

Browse files
committed
Simplify permutateWithoutRepetitions algorithm.
1 parentdb7ab9e commit00f7502

File tree

2 files changed

+37
-48
lines changed

2 files changed

+37
-48
lines changed

‎src/algorithms/sets/permutations/__test__/permutateWithoutRepetitions.test.js

Lines changed: 25 additions & 28 deletions
Original file line numberDiff line numberDiff line change
@@ -3,9 +3,6 @@ import factorial from '../../../math/factorial/factorial';
33

44
describe('permutateWithoutRepetitions',()=>{
55
it('should permutate string',()=>{
6-
constpermutations0=permutateWithoutRepetitions([]);
7-
expect(permutations0).toEqual([]);
8-
96
constpermutations1=permutateWithoutRepetitions(['A']);
107
expect(permutations1).toEqual([
118
['A'],
@@ -14,8 +11,8 @@ describe('permutateWithoutRepetitions', () => {
1411
constpermutations2=permutateWithoutRepetitions(['A','B']);
1512
expect(permutations2.length).toBe(2);
1613
expect(permutations2).toEqual([
17-
['B','A'],
1814
['A','B'],
15+
['B','A'],
1916
]);
2017

2118
constpermutations6=permutateWithoutRepetitions(['A','A']);
@@ -28,41 +25,41 @@ describe('permutateWithoutRepetitions', () => {
2825
constpermutations3=permutateWithoutRepetitions(['A','B','C']);
2926
expect(permutations3.length).toBe(factorial(3));
3027
expect(permutations3).toEqual([
31-
['C','B','A'],
32-
['B','C','A'],
28+
['A','B','C'],
3329
['B','A','C'],
34-
['C','A','B'],
30+
['B','C','A'],
3531
['A','C','B'],
36-
['A','B','C'],
32+
['C','A','B'],
33+
['C','B','A'],
3734
]);
3835

3936
constpermutations4=permutateWithoutRepetitions(['A','B','C','D']);
4037
expect(permutations4.length).toBe(factorial(4));
4138
expect(permutations4).toEqual([
42-
['D','C','B','A'],
43-
['C','D','B','A'],
44-
['C','B','D','A'],
45-
['C','B','A','D'],
46-
['D','B','C','A'],
47-
['B','D','C','A'],
48-
['B','C','D','A'],
49-
['B','C','A','D'],
50-
['D','B','A','C'],
51-
['B','D','A','C'],
52-
['B','A','D','C'],
39+
['A','B','C','D'],
5340
['B','A','C','D'],
54-
['D','C','A','B'],
55-
['C','D','A','B'],
56-
['C','A','D','B'],
41+
['B','C','A','D'],
42+
['B','C','D','A'],
43+
['A','C','B','D'],
5744
['C','A','B','D'],
58-
['D','A','C','B'],
59-
['A','D','C','B'],
45+
['C','B','A','D'],
46+
['C','B','D','A'],
6047
['A','C','D','B'],
61-
['A','C','B','D'],
62-
['D','A','B','C'],
63-
['A','D','B','C'],
48+
['C','A','D','B'],
49+
['C','D','A','B'],
50+
['C','D','B','A'],
6451
['A','B','D','C'],
65-
['A','B','C','D'],
52+
['B','A','D','C'],
53+
['B','D','A','C'],
54+
['B','D','C','A'],
55+
['A','D','B','C'],
56+
['D','A','B','C'],
57+
['D','B','A','C'],
58+
['D','B','C','A'],
59+
['A','D','C','B'],
60+
['D','A','C','B'],
61+
['D','C','A','B'],
62+
['D','C','B','A'],
6663
]);
6764

6865
constpermutations5=permutateWithoutRepetitions(['A','B','C','D','E','F']);

‎src/algorithms/sets/permutations/permutateWithoutRepetitions.js

Lines changed: 12 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -3,35 +3,27 @@
33
*@return {*[]}
44
*/
55
exportdefaultfunctionpermutateWithoutRepetitions(permutationOptions){
6-
if(permutationOptions.length===0){
7-
return[];
8-
}
9-
106
if(permutationOptions.length===1){
117
return[permutationOptions];
128
}
139

10+
// Init permutations array.
1411
constpermutations=[];
1512

16-
// Get all permutations of length (n - 1).
17-
constpreviousOptions=permutationOptions.slice(0,permutationOptions.length-1);
18-
constpreviousPermutations=permutateWithoutRepetitions(previousOptions);
13+
// Get all permutations for permutationOptions excluding the first element.
14+
constsmallerPermutations=permutateWithoutRepetitions(permutationOptions.slice(1));
1915

20-
// Insertlast option into every possible position of everyprevious permutation.
21-
constlastOption=permutationOptions.slice(permutationOptions.length-1);
16+
// Insertfirst option into every possible position of everysmaller permutation.
17+
constfirstOption=permutationOptions[0];
2218

23-
for(
24-
letpermutationIndex=0;
25-
permutationIndex<previousPermutations.length;
26-
permutationIndex+=1
27-
){
28-
constcurrentPermutation=previousPermutations[permutationIndex];
19+
for(letpermIndex=0;permIndex<smallerPermutations.length;permIndex+=1){
20+
constsmallerPermutation=smallerPermutations[permIndex];
2921

30-
// Insertlast option into every possible position ofcurrentPermutation.
31-
for(letpositionIndex=0;positionIndex<=currentPermutation.length;positionIndex+=1){
32-
constpermutationPrefix=currentPermutation.slice(0,positionIndex);
33-
constpermutationSuffix=currentPermutation.slice(positionIndex);
34-
permutations.push(permutationPrefix.concat(lastOption,permutationSuffix));
22+
// Insertfirst option into every possible position ofsmallerPermutation.
23+
for(letpositionIndex=0;positionIndex<=smallerPermutation.length;positionIndex+=1){
24+
constpermutationPrefix=smallerPermutation.slice(0,positionIndex);
25+
constpermutationSuffix=smallerPermutation.slice(positionIndex);
26+
permutations.push(permutationPrefix.concat([firstOption],permutationSuffix));
3527
}
3628
}
3729

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp