## 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.

Answered By – superb rain

Answer Checked By – Mildred Charles (BugsFixing Admin)