Add permutations and combinations.

trekhleb · trekhleb · commit 21999cc9d14f · 2018-04-17T19:39:44.000+03:00
diff --git a/README.md b/README.md
@@ -36,7 +36,7 @@
   * [Least Common Multiple (LCM)](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/math/least-common-multiple)
   * [Fisher–Yates Shuffle](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/math/fisher-yates) - random permutation of a finite sequence
 * **String**
-  * [String Permutations](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/string/permutations)
+  * [String Permutations](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/string/permutations) - with and without repetitions
   * Combination
   * Minimum Edit distance (Levenshtein Distance)
   * Hamming
diff --git a/src/algorithms/string/permutations/README.md b/src/algorithms/string/permutations/README.md
@@ -1,22 +1,41 @@
-# String Permutations
+# Permutations
+
+When the order doesn't matter, it is a **Combination**.
+
+When the order **does** matter it is a **Permutation**.
+
+**"The combination to the safe is 472"**. We do care about the order. `724` won't work, nor will `247`. 
+It has to be exactly `4-7-2`.
+
+## Permutations without repetitions
 
 A permutation, also called an “arrangement number” or “order”, is a rearrangement of 
 the elements of an ordered list `S` into a one-to-one correspondence with `S` itself. 
-A string of length `n` has `n!` permutation.
 
 Below are the permutations of string `ABC`.
 
 `ABC ACB BAC BCA CBA CAB`
 
-When the order doesn't matter, it is a **Combination**.
+Or for example the first three people in a running race: you can't be first and second.
 
-When the order **does** matter it is a **Permutation**.
+**Number of combinations**
+
+```
+n * (n-1) * (n -2) * ... * 1 = n!
+```
+
+## Permutations with repetitions
+
+When repetition is allowed we have permutations with repetitions.
+For example the the lock below: it could be `333`.
 
 ![Permutation Lock](https://www.mathsisfun.com/combinatorics/images/combination-lock.jpg)
 
-Permutation with repetitions example
+**Number of combinations**
 
-![Permutation With Repetitions](https://upload.wikimedia.org/wikipedia/commons/6/69/Permutations-With-Repetition.gif)
+```
+n * n * n ... (r times) = n^r
+```
 
 ## References
 
diff --git a/src/algorithms/string/permutations/__test__/permutateWithoutRepetitions.test.js b/src/algorithms/string/permutations/__test__/permutateWithoutRepetitions.test.js
@@ -1,28 +1,28 @@
-import permutateString from '../permutateString';
+import permutateWithoutRepetitions from '../permutateWithoutRepetitions';
 
 describe('permutateString', () => {
   it('should permutate string', () => {
-    const permutations0 = permutateString('');
+    const permutations0 = permutateWithoutRepetitions('');
     expect(permutations0).toEqual([]);
 
-    const permutations1 = permutateString('A');
+    const permutations1 = permutateWithoutRepetitions('A');
     expect(permutations1).toEqual(['A']);
 
-    const permutations2 = permutateString('AB');
+    const permutations2 = permutateWithoutRepetitions('AB');
     expect(permutations2.length).toBe(2);
     expect(permutations2).toEqual([
       'BA',
       'AB',
     ]);
 
-    const permutations6 = permutateString('AA');
+    const permutations6 = permutateWithoutRepetitions('AA');
     expect(permutations6.length).toBe(2);
     expect(permutations6).toEqual([
       'AA',
       'AA',
     ]);
 
-    const permutations3 = permutateString('ABC');
+    const permutations3 = permutateWithoutRepetitions('ABC');
     expect(permutations3.length).toBe(2 * 3);
     expect(permutations3).toEqual([
       'CBA',
@@ -33,7 +33,7 @@ describe('permutateString', () => {
       'ABC',
     ]);
 
-    const permutations4 = permutateString('ABCD');
+    const permutations4 = permutateWithoutRepetitions('ABCD');
     expect(permutations4.length).toBe(2 * 3 * 4);
     expect(permutations4).toEqual([
       'DCBA',
@@ -62,7 +62,7 @@ describe('permutateString', () => {
       'ABCD',
     ]);
 
-    const permutations5 = permutateString('ABCDEF');
+    const permutations5 = permutateWithoutRepetitions('ABCDEF');
     expect(permutations5.length).toBe(2 * 3 * 4 * 5 * 6);
   });
 });
diff --git a/src/algorithms/string/permutations/permutateWithoutRepetitions.js b/src/algorithms/string/permutations/permutateWithoutRepetitions.js
@@ -1,4 +1,4 @@
-export default function permutateString(str) {
+export default function permutateWithoutRepetitions(str) {
   if (str.length === 0) {
     return [];
   }
@@ -11,7 +11,7 @@ export default function permutateString(str) {
 
   // Get all permutations of string of length (n - 1).
   const previousString = str.substring(0, str.length - 1);
-  const previousPermutations = permutateString(previousString);
+  const previousPermutations = permutateWithoutRepetitions(previousString);
 
   // Insert last character into every possible position of every previous permutation.
   const lastCharacter = str.substring(str.length - 1);
