There are tons of methods to generate every permutation of some elements. And here’s another intuitive and efficient (beats 98.00% of submissions on LeetCode) one I came up with.

Suppose we have $N$ elements $a_1, a_2 … a_N$ and $answer$ is a 1-index (yeah, burn me) list sized $n!$ (so it can just hold all of the permutations). Suppose that we also have function $f(n)$ which fills $answer[1..n!]$ with the permutation of $a_1, a_2 … a_n$. Thus if we call $f(1), f(2) … f(N)$ in sequence, $answer$ should hold what we want.

$f(1)$ is pretty simple. We simply set $answer[1] = [a_1]$.

When we are calling $f(n)$, we know that $f(n-1)$ has been called and $answer[1..(n-1)!] = P$ already holds the permutations of $a_1…a_{n-1}$. We observe that for each permutation $p$ in $P$, if we replace any of $p_i$ with $a_n$ and put $p_i$ in the back instead, we get a new unique (obviously) permutation of $a_1…a_n$: $[p_1, p_2 … p_{i-1}, p_i, p_{i+1} … p_{n-1}] \rightarrow [p_1, p_2 … p_{i-1}, a_n, p_{i+1} … p_{n-1}, p_i]$

Note that we can also change nothing and just append $a_n$ to the back.

So this is what we do for $f(n)$: we loop through $answer[1..(n-1)!] = P$. For each permutation $p$ in $P$, we generate $n-1$ new permutations by the aforementioned “replacing” and append $a_n$ to the original $p$. Because we’re always appending to lists, there is no nasty memory move-around. Because each “replacing” is constant time, we’re at the minimal $O(n!)$ complexity.

Here is a Python implementation that passes the LeetCode problem. Because it’s real-world, we starts with $n=0$ instead:

def permute(a):
N = len(a)

# Manual case when n = 0

# n = [1 .. N)
for n in range(1, N):
# i = [0 .. (n-1)!)
# because len(answer) = (n-1)! anyway