Published by Dimitris Kougioumtzis · Updated
Choose unused positions and skip equal unused siblings to emit every distinct value permutation once.
Sort the values, then choose an unused position at each depth. Skip a duplicate value when its equal predecessor is still unused, preventing equal sibling branches from generating duplicate permutations.
When to use Distinct permutations by backtracking
Enumerating every distinct order of a small multiset.
Choosing an alternative
Combinations choose increasing positions without considering order. This view considers all orders while merging branches that differ only by identical values.
Worked example: input and state changes
Example input
2,1,2
These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.
Step 0: Input 1,2,2. Build a choice path; completed rows appear below it.
State at this checkpoint
{ "values": [ "�", "�", "�" ], "active": [], "kind": "matrix", "columns": 3, "result": 0, "output": [] }Step 5: Undo the choice and explore another branch.
State at this checkpoint
{ "values": [ 1, 2, "�", 1, 2, 2 ], "active": [], "kind": "matrix", "columns": 3, "result": 1, "output": [ 1, 2, 2 ] }Step 10: Choose input index 2.
State at this checkpoint
{ "values": [ 2, 1, 2, 1, 2, 2 ], "active": [], "kind": "matrix", "columns": 3, "result": 1, "output": [ 1, 2, 2 ] }Step 15: Choose input index 0.
State at this checkpoint
{ "values": [ 2, 2, 1, 1, 2, 2, 2, 1, 2 ], "active": [], "kind": "matrix", "columns": 3, "result": 2, "output": [ 1, 2, 2, 2, 1, 2 ] }Step 20: Generated 3 distinct permutations.
State at this checkpoint
{ "values": [ "�", "�", "�", 1, 2, 2, 2, 1, 2, 2, 2, 1 ], "active": [], "kind": "matrix", "columns": 3, "result": 3, "output": [ 1, 2, 2, 2, 1, 2, 2, 2, 1 ] }
Expected final state
Generated 3 distinct permutations.
Complexity and input bounds
Family: Combinatorics. Time complexity: O(n n!) output-sensitive.
Implementation detail: At most four values bound the output to 24 rows and 96 cells. Downloads sort the input array in place, return the row count and write n values per row in lexicographic value order. Portable versions use an explicit traversal stack; the Python reference recurses.
Space complexity: O(n) traversal state excluding output; Python stores result rows before flattening. Recorded frames add space.
Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.
1..4 values 0..99. Inputs are sorted first; duplicate values do not duplicate results.
The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.
Common mistakes and limitations
Restore used markers on backtracking. Sorting alone does not remove duplicate outputs; the unused-predecessor rule is required. The empty input has one empty permutation.
Further reading
For background on algorithm analysis and the JavaScript function interface:
- MIT OpenCourseWare: algorithm design and analysis foundations
- MDN: JavaScript function parameters and return values
Editorial and testing approach · Browse all algorithm guides
Complete JavaScript implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 | // n 0..4 integer values 0..99. Sorts a in place and emits distinct value permutations in lexicographic order, skipping duplicate unused siblings. Returns row count; output is row-major with n values per row, capacity at least n*n! (at most 96). Empty input has one empty permutation and writes nothing. Explicit stack in portable versions, recursive Python; O(n*n!) worst-case time, O(n) traversal scratch excluding output. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation. function algorithm(a, n, output) { let key = 0; let j = 0; for (let i = 1; i < n; i++) { key = a[i]; j = i-1; while (j >= 0 && a[j] > key) { a[j+1] = a[j]; j--; } a[j+1] = key; } if (n == 0) { return 1; } let chosen = Array(256).fill(0); let next = Array(256).fill(0); let used = Array(256).fill(0); let depth = 0; let count = 0; let candidate = 0; while (depth >= 0) { if (depth == n) { for (let k = 0; k < n; k++) { output[count*n+k] = a[chosen[k]]; } count++; depth--; used[chosen[depth]] = 0; } else { candidate = next[depth]; while (candidate < n && (used[candidate] != 0 || (candidate > 0 && a[candidate] == a[candidate-1] && used[candidate-1] == 0))) { candidate++; } if (candidate == n) { next[depth] = 0; depth--; if (depth >= 0) { used[chosen[depth]] = 0; } } else { next[depth] = candidate+1; chosen[depth] = candidate; used[candidate] = 1; depth++; next[depth] = 0; } } } return count; } |
Source
Author reference for combinatorial generation, not a claim to an original research paper. The playground specifies its own bounded enumeration order and duplicate/position semantics.
- The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1
Donald E. Knuth (2011). Author reference book.