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

Answered By – superb rain

Answer Checked By – Mildred Charles (BugsFixing Admin)

Leave a Reply

Your email address will not be published. Required fields are marked *