Permutations

Generate every ordering of a set of values.

Time O(n · n!)Space O(n)Code C++, Python and C#

Watch it animatedStep through it, with the running line highlighted. Free with an account.

The idea

Fill positions left to right. For each position try every value not used yet, recurse to fill the rest, then release the value so another branch can use it.

Code

C++PythonC#

void permute(const vector<int>& a, vector<bool>& used, vector<int>& path, vector<vector<int>>& result) {
    if (path.size() == a.size()) { result.push_back(path); return; }
    for (int i = 0; i < (int)a.size(); i++) {
        if (used[i]) continue;
        used[i] = true; path.push_back(a[i]);
        permute(a, used, path, result);
        used[i] = false; path.pop_back();
    }
}

def permute(a: list[int], used: list[bool], path: list[int], result: list[list[int]]) -> None:
    if len(path) == len(a): result.append(path[:]); return
    for i in range(len(a)):
        if used[i]: continue
        used[i] = True; path.append(a[i])
        permute(a, used, path, result)
        used[i] = False; path.pop()

public static void Permute(int[] a, bool[] used, List<int> path, List<List<int>> result) {
    if (path.Count == a.Length) { result.Add(new List<int>(path)); return; }
    for (int i = 0; i < a.Length; i++) {
        if (used[i]) continue;
        used[i] = true; path.Add(a[i]);
        Permute(a, used, path, result);
        used[i] = false; path.RemoveAt(path.Count - 1);
    }
}

Tips

Unlike subsets, the loop always starts at 0, because order matters. The used array prevents repeats.
n! grows very fast: 10 values already have 3,628,800 orderings.

In the .NET library

bool[] used is the cheapest "is it taken?" check. For up to 32 items you can pack it into a single int bitmask.