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

Commitdb7ab9e

Browse files
committed
Simplify permutateWithRepetitions algorithm.
1 parentc5ed81d commitdb7ab9e

File tree

6 files changed

+24
-135
lines changed

6 files changed

+24
-135
lines changed

‎src/algorithms/sets/combinations/combineWithRepetitions.js

Lines changed: 2 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -13,9 +13,7 @@ export default function combineWithRepetitions(comboOptions, comboLength) {
1313

1414
// Eliminate characters one by one and concatenate them to
1515
// combinations of smaller lengths.
16-
for(letoptionIndex=0;optionIndex<comboOptions.length;optionIndex+=1){
17-
constcurrentOption=comboOptions[optionIndex];
18-
16+
comboOptions.forEach((currentOption,optionIndex)=>{
1917
constsmallerCombos=combineWithRepetitions(
2018
comboOptions.slice(optionIndex),
2119
comboLength-1,
@@ -24,7 +22,7 @@ export default function combineWithRepetitions(comboOptions, comboLength) {
2422
smallerCombos.forEach((smallerCombo)=>{
2523
combos.push([currentOption].concat(smallerCombo));
2624
});
27-
}
25+
});
2826

2927
returncombos;
3028
}

‎src/algorithms/sets/combinations/combineWithoutRepetitions.js

Lines changed: 2 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -13,9 +13,7 @@ export default function combineWithoutRepetitions(comboOptions, comboLength) {
1313

1414
// Eliminate characters one by one and concatenate them to
1515
// combinations of smaller lengths.
16-
for(letoptionIndex=0;optionIndex<=(comboOptions.length-comboLength);optionIndex+=1){
17-
constcurrentOption=comboOptions[optionIndex];
18-
16+
comboOptions.forEach((currentOption,optionIndex)=>{
1917
constsmallerCombos=combineWithoutRepetitions(
2018
comboOptions.slice(optionIndex+1),
2119
comboLength-1,
@@ -24,7 +22,7 @@ export default function combineWithoutRepetitions(comboOptions, comboLength) {
2422
smallerCombos.forEach((smallerCombo)=>{
2523
combos.push([currentOption].concat(smallerCombo));
2624
});
27-
}
25+
});
2826

2927
returncombos;
3028
}

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

Lines changed: 0 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -2,9 +2,6 @@ import permutateWithRepetitions from '../permutateWithRepetitions';
22

33
describe('permutateWithRepetitions',()=>{
44
it('should permutate string with repetition',()=>{
5-
constpermutations0=permutateWithRepetitions([]);
6-
expect(permutations0).toEqual([]);
7-
85
constpermutations1=permutateWithRepetitions(['A']);
96
expect(permutations1).toEqual([
107
['A'],

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

Lines changed: 0 additions & 55 deletions
This file was deleted.
Lines changed: 20 additions & 32 deletions
Original file line numberDiff line numberDiff line change
@@ -1,42 +1,30 @@
11
/**
22
*@param {*[]} permutationOptions
3+
*@param {number} permutationLength
34
*@return {*[]}
45
*/
5-
exportdefaultfunctionpermutateWithRepetitions(permutationOptions){
6-
// There is no permutations for empty array.
7-
if(!permutationOptions||permutationOptions.length===0){
8-
return[];
6+
exportdefaultfunctionpermutateWithRepetitions(
7+
permutationOptions,
8+
permutationLength=permutationOptions.length,
9+
){
10+
if(permutationLength===1){
11+
returnpermutationOptions.map(permutationOption=>[permutationOption]);
912
}
1013

11-
// There is only one permutation for the 1-element array.
12-
if(permutationOptions.length===1){
13-
return[permutationOptions];
14-
}
15-
16-
// Let's create initial set of permutations.
17-
letpreviousPermutations=permutationOptions.map(option=>[option]);
18-
letcurrentPermutations=[];
19-
letpermutationSize=1;
20-
21-
// While the size of each permutation is less then or equal to options length...
22-
while(permutationSize<permutationOptions.length){
23-
// Reset all current permutations.
24-
currentPermutations=[];
14+
// Init permutations array.
15+
constpermutations=[];
2516

26-
for(letpermIndex=0;permIndex<previousPermutations.length;permIndex+=1){
27-
for(letoptionIndex=0;optionIndex<permutationOptions.length;optionIndex+=1){
28-
letcurrentPermutation=previousPermutations[permIndex];
29-
currentPermutation=currentPermutation.concat([permutationOptions[optionIndex]]);
30-
currentPermutations.push(currentPermutation);
31-
}
32-
}
17+
// Go through all options and join it to the smaller permutations.
18+
permutationOptions.forEach((currentOption)=>{
19+
constsmallerPermutations=permutateWithRepetitions(
20+
permutationOptions,
21+
permutationLength-1,
22+
);
3323

34-
// Make current permutations to be the previous ones.
35-
previousPermutations=currentPermutations.slice(0);
36-
37-
// Increase permutation size counter.
38-
permutationSize+=1;
39-
}
24+
smallerPermutations.forEach((smallerPermutation)=>{
25+
permutations.push([currentOption].concat(smallerPermutation));
26+
});
27+
});
4028

41-
returncurrentPermutations;
29+
returnpermutations;
4230
}

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

Lines changed: 0 additions & 37 deletions
This file was deleted.

0 commit comments

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