DSA Permutations

The problem

Permutations asks for every ordering of a list of values. An ordering uses every value exactly once. Two orderings differ when some position holds a different value.

Repeated values need care. Equal values are interchangeable, so swapping the two copies makes no new ordering. This article counts distinct orderings only, and its solution sorts the values before searching.

cases = [
    ([1, 2], [[1, 2], [2, 1]]),
    ([1, 2, 3], [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]),
    ([1, 1, 2], [[1, 1, 2], [1, 2, 1], [2, 1, 1]]),
    ([5], [[5]]),
]
for nums, expected in cases:
    print("nums", nums, "orderings:", expected)

Three distinct values give six orderings. The list [1, 1, 2] gives only three. The two copies of 1 are interchangeable, and that halves the count.

Intuition: fill one slot at a time, but guard each pick

The first idea fills one slot at a time. Any value could fill the first slot. Any value could fill the second slot too.

That freedom is the trap. It lets one value fill two slots, which no ordering may do. The next block counts the damage on a two-value list.

nums = [1, 2]
built = []
for first in nums:
    for second in nums:
        built.append([first, second])
valid = [row for row in built if sorted(row) == nums]
invalid = [row for row in built if sorted(row) != nums]
print("sequences built:", len(built))
print("real orderings:", valid)
print("invalid:", invalid)

Half of the built sequences are waste. The search needs a memory of which values already sit in the path. That memory is the fix the optimal solution adds.

Brute force: build every sequence, then filter

The brute force builds every sequence of length n over the values, repeats allowed. It keeps a sequence only when the sorted sequence equals the sorted input. A counter records how many sequences were built.

The count of orderings of n distinct values is n factorial, written n!. It is the product 1 times 2 times every whole number up to n, so three values give 6 orderings.

def permutations_brute(nums):
    results = []
    path = []
    built = [0]
    def search():
        if len(path) == len(nums):
            built[0] += 1
            if sorted(path) == sorted(nums):
                results.append(list(path))
            return
        for value in nums:
            path.append(value)
            search()
            path.pop()
    search()
    return results, built[0]

result, built = permutations_brute([1, 2, 3])
for row in result:
    print(row)
print("orderings kept:", len(result))
print("sequences built:", built)

The brute force built 27 sequences to keep 6. The waste grows as n to the power n. The surviving orderings grow only as n factorial, so the gap widens fast.

The optimal solution: a used list guards each slot

The state is the path built so far plus a used list that marks which positions already sit in the path, and the search picks only an unused position, clearing its mark when the branch returns. That one sentence is the core method.

One more rule handles repeats. The function sorts the values first, so equal values sit side by side. It then skips a value whose equal left neighbour is unused, because that ordering is built through the neighbour instead.

def permutations(nums):
    nums = sorted(nums)
    results = []
    path = []
    used = [False] * len(nums)
    def search():
        if len(path) == len(nums):
            results.append(list(path))
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                continue
            used[i] = True
            path.append(nums[i])
            search()
            path.pop()
            used[i] = False
    search()
    return results

cases = [
    ([1, 2], [[1, 2], [2, 1]]),
    ([1, 2, 3], [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]),
    ([1, 1, 2], [[1, 1, 2], [1, 2, 1], [2, 1, 1]]),
    ([1, 2, 1], [[1, 1, 2], [1, 2, 1], [2, 1, 1]]),
    ([5], [[5]]),
]
for nums, expected in cases:
    result = permutations(nums)
    print("nums", nums, "->", result, "match:", result == expected)

Every case passes, including the unsorted [1, 2, 1]. Sorting inside the function is what makes that row work. The equal values land side by side before the skip rule ever sees them.

Walkthrough: building the orderings of [1, 2]

The walk picks one value at a time. Each pick prints the path and the used marks. Each release line is a backtrack step, where a value leaves the path and its mark clears.

nums = [1, 2]
path = []
used = [False] * len(nums)
def search():
    if len(path) == len(nums):
        print("record", list(path))
        return
    for i in range(len(nums)):
        if used[i]:
            continue
        used[i] = True
        path.append(nums[i])
        print("pick", nums[i], "- path:", list(path), "- used:", list(used))
        search()
        path.pop()
        used[i] = False
        print("release", nums[i], "- path:", list(path), "- used:", list(used))
search()

Read the two records in order. They are [1, 2] and [2, 1]. The release lines are what let the second record exist, because value 1 becomes pickable again for a later slot.

Complexity

Time is O(n times n!) for n distinct values. The search builds n! orderings, and copying each finished ordering costs n steps.

Extra space is O(n) besides the stored results. The path holds at most n values, and the used list holds one mark per value.

import math
for n in [2, 3, 4]:
    print("values", n, "- brute sequences:", n ** n, "- orderings:", math.factorial(n))

At four values the brute force builds 256 sequences for 24 orderings. The used list removes that waste before it happens, by refusing a taken value at pick time.

Edge cases and pitfalls

An empty list has one ordering, the empty ordering. A single value has one ordering too. Repeated values in any input order give each distinct ordering exactly once.

def permutations(nums):
    nums = sorted(nums)
    results = []
    path = []
    used = [False] * len(nums)
    def search():
        if len(path) == len(nums):
            results.append(list(path))
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                continue
            used[i] = True
            path.append(nums[i])
            search()
            path.pop()
            used[i] = False
    search()
    return results

print("empty list:", permutations([]))
print("one value:", permutations([5]))
result = permutations([1, 2, 1])
print("non-adjacent twins:", result)
print("count:", len(result), "- distinct:", len({tuple(row) for row in result}))

Forgetting to clear a used mark after a branch is the classic bug in this search. Later branches then see the value as taken forever. Orderings go missing silently, with no error to announce the loss.

def permutations_buggy(nums):
    results = []
    path = []
    used = [False] * len(nums)
    def search():
        if len(path) == len(nums):
            results.append(list(path))
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True
            path.append(nums[i])
            search()
            path.pop()
    search()
    return results

result = permutations_buggy([1, 2, 3])
print("orderings found:", result)
print("count:", len(result))

One ordering survives out of six. The count exposes the bug at once, which is why every block in this article prints its count beside its results.