Permutations

+10

You get a list nums of different integers. Return every ordering of those values, each a list that uses every value exactly once, so n values give n! orderings. List them in lexicographic order: compare two orderings position by position and let the first difference decide. For [1, 2, 3] that puts [1, 2, 3] first and [3, 2, 1] last.

Function

permute(nums: integer-array) → integer-2d-array

numsinteger-array: the values, all different, in any order
Returnsinteger-2d-array: every ordering of the values, listed in lexicographic order

Constraints

1 ≤ nums.length ≤ 6
-10 ≤ nums[i] ≤ 10
All values in nums are different.
nums may come in any order.

Examples

Input: nums = [3, 1, 2]
Output: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
Explanation: The orderings that start with 1 come first, and [1, 2, 3] comes before [1, 3, 2] because 2 is smaller than 3 at the second position. The input order does not matter.

Input: nums = [2, -1]
Output: [[-1, 2], [2, -1]]
Explanation: Two values can be written in two orders. [-1, 2] comes first because -1 is smaller than 2.

Follow-up

Given one ordering, can you produce the next one in lexicographic order in place, in O(n) time and O(1) extra space?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

n different values have n! orderings, 720 for six, and you must list them all, so the work is at least n × n!. Backtracking over the sorted values, always trying the smallest unused value first, builds each ordering once and emits them in lexicographic order.

Insert into every gap, then sort

Intuition

Grow the orderings one value at a time, starting from the empty list. To add 3 to [1, 2], insert it into each of the three gaps: [3, 1, 2], [1, 3, 2] and [1, 2, 3]. Every ordering of k+1 values is built exactly once: remove the newest value and you get the ordering it grew from, while its position names the gap.

The orderings do not come out in order: for [1, 2, 3] the first one built is [3, 2, 1]. So you finish with a sort, about n! × log(n!) comparisons of up to n values each, roughly 720 × 9.5 × 6 ≈ 41,000 reads for six values. It also holds a whole generation of orderings in memory.

Algorithm

Start with a list that holds one empty ordering.
For each value in nums, build a new list: for every ordering so far and every gap from 0 to its length, copy the ordering with the value inserted at that gap.
Replace the old list with the new one.
Sort the orderings position by position and return them.

def permute(nums):
    perms = [[]]
    for value in nums:
        grown = []
        for perm in perms:
            # Put value into every gap of perm, both ends included.
            for gap in range(len(perm) + 1):
                grown.append(perm[:gap] + [value] + perm[gap:])
        perms = grown
    # Insertion order is not lexicographic, so sort at the end.
    perms.sort()
    return perms

Backtracking with a used array

Intuition

Fill n slots from left to right: n candidates for the first, n-1 for the second, and so on. As a tree, each edge places one more value and each leaf at depth n is one ordering. Walk it with one shared path and a used flag per value: for each free value, choose it, explore one level deeper, then un-choose it. Un-choosing restores the exact state, so the loop tries the next value from the same node.

The order comes out right on its own. The loop tries the smallest free value first and finishes every ordering with a given prefix before it changes that prefix, so [1, 2, ...] comes before [1, 3, ...], which comes before [2, ...]. That is why you sort nums first. The tree has about e × n! nodes, each running a loop of n: O(n × n!) time.

Algorithm

Sort the values and make a used array of n false flags.
Write explore(). If path holds n values, append a copy to the result and return.
Otherwise, for each index i from 0 to n-1 whose value is free: mark it used and append values[i] (choose), call explore() (explore), then remove it and mark it free (un-choose).
Call explore() once and return the result.

def permute(nums):
    values = sorted(nums)
    n = len(values)
    result = []
    path = []
    used = [False] * n

    def explore():
        # A full path is a leaf of the decision tree: one finished ordering.
        if len(path) == n:
            result.append(path[:])
            return
        # Smallest unused value first, so the leaves come out in lexicographic order.
        for i in range(n):
            if used[i]:
                continue
            used[i] = True
            path.append(values[i])  # choose
            explore()               # explore
            path.pop()              # un-choose
            used[i] = False

    explore()
    return result

Pitfalls and edge cases

Recording path instead of a copy of it. All n! entries end up as the same list, which is empty once the walk is over.
Undoing half a choice. If you remove the value but leave used[i] set, that value never appears in a later branch and you return fewer than n! orderings.
Not sorting nums first. The orderings then follow the input, so [3, 1, 2] would be listed first.
Using the swap method (swap nums[start] with each later position, recurse, swap back) without a final sort. For [1, 2, 3] it lists [3, 2, 1] before [3, 1, 2].
Searching path to see whether a value is used. It costs n per check and breaks when values repeat; a flag per index is O(1).

Frequently asked questions3

How many permutations does a list of n distinct elements have?

n!, read n factorial: n choices for the first position, n-1 for the second, down to one for the last, multiplied together. Three values give 6 orderings, six give 720, and ten already give 3,628,800, which is why permutation problems keep n small.

What is the time complexity of generating all permutations?

O(n × n!). There are n! orderings and writing each one out takes n steps, so no method does better when it has to return them all. Backtracking reaches this bound and, besides the output, needs O(n) space for the path, the used flags and the recursion.

How do you generate permutations when the input has duplicates?

Sort the values and, at each position, skip a value that equals the value before it while that earlier copy is not in use: i > 0, values[i] == values[i-1] and !used[i-1]. That forces equal values to be placed in their original order, so each distinct ordering is built once.

def permute(nums):
    # Write code here

Test #1

Test #2

Test #3

Argument

nums = [3, 1, 2]

Expected Output

[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]