add recursive solution to permutations with repetitions problem (trekhleb#52)

mmapplebeck · trekhleb · commit b0c55ec817c1 · 2018-06-13T08:03:56.000+03:00
* add recursive solution to permutations with repetitions problem

* fix untested function, failing test

* add comments
diff --git a/src/algorithms/sets/permutations/__test__/permutateWithRepetitions.test.js b/src/algorithms/sets/permutations/__test__/permutateWithRepetitions.test.js
@@ -1,55 +1,8 @@
 import permutateWithRepetitions from '../permutateWithRepetitions';
+import testPermutateWithRepetitionsFn from './testPermutateWithRepetitionsFn';
 
 describe('permutateWithRepetitions', () => {
   it('should permutate string with repetition', () => {
-    const permutations0 = permutateWithRepetitions([]);
-    expect(permutations0).toEqual([]);
-
-    const permutations1 = permutateWithRepetitions(['A']);
-    expect(permutations1).toEqual([
-      ['A'],
-    ]);
-
-    const permutations2 = permutateWithRepetitions(['A', 'B']);
-    expect(permutations2).toEqual([
-      ['A', 'A'],
-      ['A', 'B'],
-      ['B', 'A'],
-      ['B', 'B'],
-    ]);
-
-    const permutations3 = permutateWithRepetitions(['A', 'B', 'C']);
-    expect(permutations3).toEqual([
-      ['A', 'A', 'A'],
-      ['A', 'A', 'B'],
-      ['A', 'A', 'C'],
-      ['A', 'B', 'A'],
-      ['A', 'B', 'B'],
-      ['A', 'B', 'C'],
-      ['A', 'C', 'A'],
-      ['A', 'C', 'B'],
-      ['A', 'C', 'C'],
-      ['B', 'A', 'A'],
-      ['B', 'A', 'B'],
-      ['B', 'A', 'C'],
-      ['B', 'B', 'A'],
-      ['B', 'B', 'B'],
-      ['B', 'B', 'C'],
-      ['B', 'C', 'A'],
-      ['B', 'C', 'B'],
-      ['B', 'C', 'C'],
-      ['C', 'A', 'A'],
-      ['C', 'A', 'B'],
-      ['C', 'A', 'C'],
-      ['C', 'B', 'A'],
-      ['C', 'B', 'B'],
-      ['C', 'B', 'C'],
-      ['C', 'C', 'A'],
-      ['C', 'C', 'B'],
-      ['C', 'C', 'C'],
-    ]);
-
-    const permutations4 = permutateWithRepetitions(['A', 'B', 'C', 'D']);
-    expect(permutations4.length).toBe(4 * 4 * 4 * 4);
+    testPermutateWithRepetitionsFn(permutateWithRepetitions);
   });
 });
diff --git a/src/algorithms/sets/permutations/__test__/permutateWithRepetitionsRecursive.test.js b/src/algorithms/sets/permutations/__test__/permutateWithRepetitionsRecursive.test.js
@@ -0,0 +1,8 @@
+import permutateWithRepetitionsRecursive from '../permutateWithRepetitionsRecursive';
+import testPermutateWithRepetitionsFn from './testPermutateWithRepetitionsFn';
+
+describe('permutateWithRepetitionsRecursive', () => {
+  it('should permutate string with repetition', () => {
+    testPermutateWithRepetitionsFn(permutateWithRepetitionsRecursive);
+  });
+});
diff --git a/src/algorithms/sets/permutations/__test__/testPermutateWithRepetitionsFn.js b/src/algorithms/sets/permutations/__test__/testPermutateWithRepetitionsFn.js
@@ -0,0 +1,51 @@
+export default function testPermutateWithRepetitionsFn(fn) {
+  const permutations0 = fn([]);
+  expect(permutations0).toEqual([]);
+
+  const permutations1 = fn(['A']);
+  expect(permutations1).toEqual([
+    ['A'],
+  ]);
+
+  const permutations2 = fn(['A', 'B']);
+  expect(permutations2).toEqual([
+    ['A', 'A'],
+    ['A', 'B'],
+    ['B', 'A'],
+    ['B', 'B'],
+  ]);
+
+  const permutations3 = fn(['A', 'B', 'C']);
+  expect(permutations3).toEqual([
+    ['A', 'A', 'A'],
+    ['A', 'A', 'B'],
+    ['A', 'A', 'C'],
+    ['A', 'B', 'A'],
+    ['A', 'B', 'B'],
+    ['A', 'B', 'C'],
+    ['A', 'C', 'A'],
+    ['A', 'C', 'B'],
+    ['A', 'C', 'C'],
+    ['B', 'A', 'A'],
+    ['B', 'A', 'B'],
+    ['B', 'A', 'C'],
+    ['B', 'B', 'A'],
+    ['B', 'B', 'B'],
+    ['B', 'B', 'C'],
+    ['B', 'C', 'A'],
+    ['B', 'C', 'B'],
+    ['B', 'C', 'C'],
+    ['C', 'A', 'A'],
+    ['C', 'A', 'B'],
+    ['C', 'A', 'C'],
+    ['C', 'B', 'A'],
+    ['C', 'B', 'B'],
+    ['C', 'B', 'C'],
+    ['C', 'C', 'A'],
+    ['C', 'C', 'B'],
+    ['C', 'C', 'C'],
+  ]);
+
+  const permutations4 = fn(['A', 'B', 'C', 'D']);
+  expect(permutations4.length).toBe(4 * 4 * 4 * 4);
+}
diff --git a/src/algorithms/sets/permutations/permutateWithRepetitionsRecursive.js b/src/algorithms/sets/permutations/permutateWithRepetitionsRecursive.js
@@ -0,0 +1,26 @@
+/**
+ * @param {*[]} permutationOptions
+ * @return {*[]}
+ */
+export default function permutateWithRepetitionsRecursive(
+  options,
+  n = options.length || 0,
+  prefix = [],
+  perms = [],
+) {
+  // If initial options are null or empty then return empty array
+  if (!options || !options.length) return [];
+
+  // If no more iterations then add current prefix to perms array
+  if (n === 0) {
+    perms.push(prefix);
+    return perms;
+  }
+
+  // Recursively find permutations and store in perms array
+  options.forEach((option) => {
+    permutateWithRepetitionsRecursive(options, n - 1, prefix.concat([option]), perms);
+  });
+
+  return perms;
+}
