Simplify permutateWithoutRepetitions algorithm.

trekhleb · trekhleb · commit 00f75028bfe7 · 2018-06-29T12:23:26.000+03:00
diff --git a/src/algorithms/sets/permutations/__test__/permutateWithoutRepetitions.test.js b/src/algorithms/sets/permutations/__test__/permutateWithoutRepetitions.test.js
@@ -3,9 +3,6 @@ import factorial from '../../../math/factorial/factorial';
 
 describe('permutateWithoutRepetitions', () => {
   it('should permutate string', () => {
-    const permutations0 = permutateWithoutRepetitions([]);
-    expect(permutations0).toEqual([]);
-
     const permutations1 = permutateWithoutRepetitions(['A']);
     expect(permutations1).toEqual([
       ['A'],
@@ -14,8 +11,8 @@ describe('permutateWithoutRepetitions', () => {
     const permutations2 = permutateWithoutRepetitions(['A', 'B']);
     expect(permutations2.length).toBe(2);
     expect(permutations2).toEqual([
-      ['B', 'A'],
       ['A', 'B'],
+      ['B', 'A'],
     ]);
 
     const permutations6 = permutateWithoutRepetitions(['A', 'A']);
@@ -28,41 +25,41 @@ describe('permutateWithoutRepetitions', () => {
     const permutations3 = permutateWithoutRepetitions(['A', 'B', 'C']);
     expect(permutations3.length).toBe(factorial(3));
     expect(permutations3).toEqual([
-      ['C', 'B', 'A'],
-      ['B', 'C', 'A'],
+      ['A', 'B', 'C'],
       ['B', 'A', 'C'],
-      ['C', 'A', 'B'],
+      ['B', 'C', 'A'],
       ['A', 'C', 'B'],
-      ['A', 'B', 'C'],
+      ['C', 'A', 'B'],
+      ['C', 'B', 'A'],
     ]);
 
     const permutations4 = permutateWithoutRepetitions(['A', 'B', 'C', 'D']);
     expect(permutations4.length).toBe(factorial(4));
     expect(permutations4).toEqual([
-      ['D', 'C', 'B', 'A'],
-      ['C', 'D', 'B', 'A'],
-      ['C', 'B', 'D', 'A'],
-      ['C', 'B', 'A', 'D'],
-      ['D', 'B', 'C', 'A'],
-      ['B', 'D', 'C', 'A'],
-      ['B', 'C', 'D', 'A'],
-      ['B', 'C', 'A', 'D'],
-      ['D', 'B', 'A', 'C'],
-      ['B', 'D', 'A', 'C'],
-      ['B', 'A', 'D', 'C'],
+      ['A', 'B', 'C', 'D'],
       ['B', 'A', 'C', 'D'],
-      ['D', 'C', 'A', 'B'],
-      ['C', 'D', 'A', 'B'],
-      ['C', 'A', 'D', 'B'],
+      ['B', 'C', 'A', 'D'],
+      ['B', 'C', 'D', 'A'],
+      ['A', 'C', 'B', 'D'],
       ['C', 'A', 'B', 'D'],
-      ['D', 'A', 'C', 'B'],
-      ['A', 'D', 'C', 'B'],
+      ['C', 'B', 'A', 'D'],
+      ['C', 'B', 'D', 'A'],
       ['A', 'C', 'D', 'B'],
-      ['A', 'C', 'B', 'D'],
-      ['D', 'A', 'B', 'C'],
-      ['A', 'D', 'B', 'C'],
+      ['C', 'A', 'D', 'B'],
+      ['C', 'D', 'A', 'B'],
+      ['C', 'D', 'B', 'A'],
       ['A', 'B', 'D', 'C'],
-      ['A', 'B', 'C', 'D'],
+      ['B', 'A', 'D', 'C'],
+      ['B', 'D', 'A', 'C'],
+      ['B', 'D', 'C', 'A'],
+      ['A', 'D', 'B', 'C'],
+      ['D', 'A', 'B', 'C'],
+      ['D', 'B', 'A', 'C'],
+      ['D', 'B', 'C', 'A'],
+      ['A', 'D', 'C', 'B'],
+      ['D', 'A', 'C', 'B'],
+      ['D', 'C', 'A', 'B'],
+      ['D', 'C', 'B', 'A'],
     ]);
 
     const permutations5 = permutateWithoutRepetitions(['A', 'B', 'C', 'D', 'E', 'F']);
diff --git a/src/algorithms/sets/permutations/permutateWithoutRepetitions.js b/src/algorithms/sets/permutations/permutateWithoutRepetitions.js
@@ -3,35 +3,27 @@
  * @return {*[]}
  */
 export default function permutateWithoutRepetitions(permutationOptions) {
-  if (permutationOptions.length === 0) {
-    return [];
-  }
-
   if (permutationOptions.length === 1) {
     return [permutationOptions];
   }
 
+  // Init permutations array.
   const permutations = [];
 
-  // Get all permutations of length (n - 1).
-  const previousOptions = permutationOptions.slice(0, permutationOptions.length - 1);
-  const previousPermutations = permutateWithoutRepetitions(previousOptions);
+  // Get all permutations for permutationOptions excluding the first element.
+  const smallerPermutations = permutateWithoutRepetitions(permutationOptions.slice(1));
 
-  // Insert last option into every possible position of every previous permutation.
-  const lastOption = permutationOptions.slice(permutationOptions.length - 1);
+  // Insert first option into every possible position of every smaller permutation.
+  const firstOption = permutationOptions[0];
 
-  for (
-    let permutationIndex = 0;
-    permutationIndex < previousPermutations.length;
-    permutationIndex += 1
-  ) {
-    const currentPermutation = previousPermutations[permutationIndex];
+  for (let permIndex = 0; permIndex < smallerPermutations.length; permIndex += 1) {
+    const smallerPermutation = smallerPermutations[permIndex];
 
-    // Insert last option into every possible position of currentPermutation.
-    for (let positionIndex = 0; positionIndex <= currentPermutation.length; positionIndex += 1) {
-      const permutationPrefix = currentPermutation.slice(0, positionIndex);
-      const permutationSuffix = currentPermutation.slice(positionIndex);
-      permutations.push(permutationPrefix.concat(lastOption, permutationSuffix));
+    // Insert first option into every possible position of smallerPermutation.
+    for (let positionIndex = 0; positionIndex <= smallerPermutation.length; positionIndex += 1) {
+      const permutationPrefix = smallerPermutation.slice(0, positionIndex);
+      const permutationSuffix = smallerPermutation.slice(positionIndex);
+      permutations.push(permutationPrefix.concat([firstOption], permutationSuffix));
     }
   }
 
