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