Permutations
Algorithm · Core
Step through it: Backtracking pattern
holding [ ]
Step 1 of 7
Goal: list every subset of [1, 2]. At each number we choose: take it or skip it. All the choices form a tree of decisions. Start with nothing chosen.
Step 2 of 7
Choose to take 1.
Step 3 of 7
Take 2 as well. No numbers are left, so write this subset down.
Step 4 of 7
Undo that last choice (the "back" in backtracking) and skip 2 instead. Write [1] down.
Step 5 of 7
Undo taking 1 and skip it instead: holding [ ] again.
Step 6 of 7
From [ ], take or skip 2 the same way: [2] and [ ]. The four leaves are every subset. The recipe is choose, explore, undo. If a choice breaks a rule, stop that branch early (pruning).
Step 7 of 7
Your turn.
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.
Below are the permutations of string ABC.
ABC ACB BAC BCA CBA CAB
Or for example the first three people in a running race: you can't be first and second.
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 lock below could be 333.
Number of combinations
n * n * n ... (r times) = n^rCheatsheet
 |  |
Made with okso.app
Code
/**
* @param {*[]} permutationOptions
* @param {number} permutationLength
* @return {*[]}
*/
export default function permutateWithRepetitions(
permutationOptions,
permutationLength = permutationOptions.length,
) {
if (permutationLength === 1) {
return permutationOptions.map((permutationOption) => [permutationOption]);
}
// Init permutations array.
const permutations = [];
// Get smaller permutations.
const smallerPermutations = permutateWithRepetitions(
permutationOptions,
permutationLength - 1,
);
// Go through all options and join it to the smaller permutations.
permutationOptions.forEach((currentOption) => {
smallerPermutations.forEach((smallerPermutation) => {
permutations.push([currentOption].concat(smallerPermutation));
});
});
return permutations;
}/**
* @param {*[]} permutationOptions
* @return {*[]}
*/
export default function permutateWithoutRepetitions(permutationOptions) {
if (permutationOptions.length === 1) {
return [permutationOptions];
}
// Init permutations array.
const permutations = [];
// Get all permutations for permutationOptions excluding the first element.
const smallerPermutations = permutateWithoutRepetitions(permutationOptions.slice(1));
// Insert first option into every possible position of every smaller permutation.
const firstOption = permutationOptions[0];
for (let permIndex = 0; permIndex < smallerPermutations.length; permIndex += 1) {
const smallerPermutation = smallerPermutations[permIndex];
// 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));
}
}
return permutations;
}References
Practice
Backtracking
- Binary Tree PathsEasy
- SubsetsMedium
- Subsets IIMedium
- PermutationsMedium
- Permutations IIMedium
- CombinationsMedium
- Combination SumMedium
- Combination Sum IIMedium
- Combination Sum IIIMedium
- Letter Combinations of a Phone NumberMedium
- Generate ParenthesesMedium
- Palindrome PartitioningMedium
- Word SearchMedium
- Restore IP AddressesMedium
- Letter Case PermutationMedium
- Partition to K Equal Sum SubsetsMedium
- N-QueensHard
- Sudoku SolverHard
- Word Break IIHard
- Expression Add OperatorsHard
Spotted a mistake or something unclear? Report it on GitHub.