Skip to content

Commit 19f4cc7

Browse files
trekhlebtrekhleb
committed
Add recursive way of generating permutations with repetitions.
1 parent b0c55ec commit 19f4cc7

4 files changed

Lines changed: 123 additions & 69 deletions

File tree

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

Lines changed: 49 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,8 +1,55 @@
11
import permutateWithRepetitions from '../permutateWithRepetitions';
2-
import testPermutateWithRepetitionsFn from './testPermutateWithRepetitionsFn';
32

43
describe('permutateWithRepetitions', () => {
54
it('should permutate string with repetition', () => {
6-
testPermutateWithRepetitionsFn(permutateWithRepetitions);
5+
const permutations0 = permutateWithRepetitions([]);
6+
expect(permutations0).toEqual([]);
7+
8+
const permutations1 = permutateWithRepetitions(['A']);
9+
expect(permutations1).toEqual([
10+
['A'],
11+
]);
12+
13+
const permutations2 = permutateWithRepetitions(['A', 'B']);
14+
expect(permutations2).toEqual([
15+
['A', 'A'],
16+
['A', 'B'],
17+
['B', 'A'],
18+
['B', 'B'],
19+
]);
20+
21+
const permutations3 = permutateWithRepetitions(['A', 'B', 'C']);
22+
expect(permutations3).toEqual([
23+
['A', 'A', 'A'],
24+
['A', 'A', 'B'],
25+
['A', 'A', 'C'],
26+
['A', 'B', 'A'],
27+
['A', 'B', 'B'],
28+
['A', 'B', 'C'],
29+
['A', 'C', 'A'],
30+
['A', 'C', 'B'],
31+
['A', 'C', 'C'],
32+
['B', 'A', 'A'],
33+
['B', 'A', 'B'],
34+
['B', 'A', 'C'],
35+
['B', 'B', 'A'],
36+
['B', 'B', 'B'],
37+
['B', 'B', 'C'],
38+
['B', 'C', 'A'],
39+
['B', 'C', 'B'],
40+
['B', 'C', 'C'],
41+
['C', 'A', 'A'],
42+
['C', 'A', 'B'],
43+
['C', 'A', 'C'],
44+
['C', 'B', 'A'],
45+
['C', 'B', 'B'],
46+
['C', 'B', 'C'],
47+
['C', 'C', 'A'],
48+
['C', 'C', 'B'],
49+
['C', 'C', 'C'],
50+
]);
51+
52+
const permutations4 = permutateWithRepetitions(['A', 'B', 'C', 'D']);
53+
expect(permutations4.length).toBe(4 * 4 * 4 * 4);
754
});
855
});

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

Lines changed: 49 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,8 +1,55 @@
11
import permutateWithRepetitionsRecursive from '../permutateWithRepetitionsRecursive';
2-
import testPermutateWithRepetitionsFn from './testPermutateWithRepetitionsFn';
32

43
describe('permutateWithRepetitionsRecursive', () => {
54
it('should permutate string with repetition', () => {
6-
testPermutateWithRepetitionsFn(permutateWithRepetitionsRecursive);
5+
const permutations0 = permutateWithRepetitionsRecursive([]);
6+
expect(permutations0).toEqual([]);
7+
8+
const permutations1 = permutateWithRepetitionsRecursive(['A']);
9+
expect(permutations1).toEqual([
10+
['A'],
11+
]);
12+
13+
const permutations2 = permutateWithRepetitionsRecursive(['A', 'B']);
14+
expect(permutations2).toEqual([
15+
['A', 'A'],
16+
['A', 'B'],
17+
['B', 'A'],
18+
['B', 'B'],
19+
]);
20+
21+
const permutations3 = permutateWithRepetitionsRecursive(['A', 'B', 'C']);
22+
expect(permutations3).toEqual([
23+
['A', 'A', 'A'],
24+
['A', 'A', 'B'],
25+
['A', 'A', 'C'],
26+
['A', 'B', 'A'],
27+
['A', 'B', 'B'],
28+
['A', 'B', 'C'],
29+
['A', 'C', 'A'],
30+
['A', 'C', 'B'],
31+
['A', 'C', 'C'],
32+
['B', 'A', 'A'],
33+
['B', 'A', 'B'],
34+
['B', 'A', 'C'],
35+
['B', 'B', 'A'],
36+
['B', 'B', 'B'],
37+
['B', 'B', 'C'],
38+
['B', 'C', 'A'],
39+
['B', 'C', 'B'],
40+
['B', 'C', 'C'],
41+
['C', 'A', 'A'],
42+
['C', 'A', 'B'],
43+
['C', 'A', 'C'],
44+
['C', 'B', 'A'],
45+
['C', 'B', 'B'],
46+
['C', 'B', 'C'],
47+
['C', 'C', 'A'],
48+
['C', 'C', 'B'],
49+
['C', 'C', 'C'],
50+
]);
51+
52+
const permutations4 = permutateWithRepetitionsRecursive(['A', 'B', 'C', 'D']);
53+
expect(permutations4.length).toBe(4 * 4 * 4 * 4);
754
});
855
});

‎src/algorithms/sets/permutations/__test__/testPermutateWithRepetitionsFn.js‎

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

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

Lines changed: 25 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -1,26 +1,37 @@
11
/**
22
* @param {*[]} permutationOptions
3+
* @param {number} permutationLength
4+
* @param {*[]} currentPermutation
5+
* @param {*[][]} permutations
36
* @return {*[]}
47
*/
58
export default function permutateWithRepetitionsRecursive(
6-
options,
7-
n = options.length || 0,
8-
prefix = [],
9-
perms = [],
9+
permutationOptions,
10+
permutationLength = permutationOptions.length || 0,
11+
currentPermutation = [],
12+
permutations = [],
1013
) {
11-
// If initial options are null or empty then return empty array
12-
if (!options || !options.length) return [];
14+
// If initial options are null or empty then return empty array.
15+
if (!permutationOptions || !permutationOptions.length) {
16+
return [];
17+
}
18+
19+
// If no more iterations required then add current permutation to permutations array.
20+
if (permutationLength === 0) {
21+
permutations.push(currentPermutation);
1322

14-
// If no more iterations then add current prefix to perms array
15-
if (n === 0) {
16-
perms.push(prefix);
17-
return perms;
23+
return permutations;
1824
}
1925

20-
// Recursively find permutations and store in perms array
21-
options.forEach((option) => {
22-
permutateWithRepetitionsRecursive(options, n - 1, prefix.concat([option]), perms);
26+
// Recursively find permutations and store in permutations array.
27+
permutationOptions.forEach((permutationOption) => {
28+
permutateWithRepetitionsRecursive(
29+
permutationOptions,
30+
permutationLength - 1,
31+
currentPermutation.concat([permutationOption]),
32+
permutations,
33+
);
2334
});
2435

25-
return perms;
36+
return permutations;
2637
}

0 commit comments

Comments
 (0)