# [SOLVED] Generating all permutations efficiently

## Issue

I need to generate as fast as possible all permutations of integers `0`, `1`, `2`, `...`, `n - 1` and have result as a NumPy array of shape `(factorial(n), n)`, or to iterate through large portions of such an array to conserve memory.

Is there some built-in function in NumPy for doing this? Or some combination of functions.

Using `itertools.permutations(...)` is too slow, I need a faster method.

## Solution

Here’s a NumPy solution that builds the permutations of size m by modifying the permutations of size m-1 (see more explanation further down):

``````def permutations(n):
a = np.zeros((np.math.factorial(n), n), np.uint8)
f = 1
for m in range(2, n+1):
b = a[:f, n-m+1:]      # the block of permutations of range(m-1)
for i in range(1, m):
a[i*f:(i+1)*f, n-m] = i
a[i*f:(i+1)*f, n-m+1:] = b + (b >= i)
b += 1
f *= m
return a
``````

Demo:

``````>>> permutations(3)
array([[0, 1, 2],
[0, 2, 1],
[1, 0, 2],
[1, 2, 0],
[2, 0, 1],
[2, 1, 0]], dtype=uint8)
``````

For n=10, the itertools solution takes 5.5 seconds for me while this NumPy solution takes 0.2 seconds.

How it proceeds: It starts with a zero-array of the goal size, which already contains the permutations for `range(1)` at the top-right (I "dotted out" the other parts of the array):

``````[[. . 0]
[. . .]
[. . .]
[. . .]
[. . .]
[. . .]]
``````

Then it turns that into the permutations of `range(2)`:

``````[[. 0 1]
[. 1 0]
[. . .]
[. . .]
[. . .]
[. . .]]
``````

And then into the permutations of `range(3)`:

``````[[0 1 2]
[0 2 1]
[1 0 2]
[1 2 0]
[2 0 1]
[2 1 0]]
``````

It does so by filling the next-left column and by copying/modifying the previous block of permutations downwards.