python - 有效地生成所有排列

问题描述

我需要尽可能快地生成整数、、、的所有排列，并将结果作为一个NumPy数组 shape ，或者迭代这样一个数组的大部分以节省内存。012...n - 1(factorial(n), n)

NumPy 中是否有一些内置函数可以执行此操作？或者一些功能的组合。

使用itertools.permutations(...)太慢，我需要一个更快的方法。

标签： pythonperformancenumpypermutation

这是一个 NumPy 解决方案，它通过修改大小 m-1 的排列来构建大小 m 的排列（请参阅下面的更多解释）：

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

演示：

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

对于 n=10，itertools 解决方案对我来说需要 5.5 秒，而这个 NumPy 解决方案需要 0.2 秒。

它是如何进行的：它从目标大小的零数组开始，它已经包含range(1)右上角的排列（我“点缀”了数组的其他部分）：

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

然后它把它变成的排列range(2)：

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

然后进入的排列range(3)：

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

它通过填充左下一列并向下复制/修改前一个排列块来实现。

python - 有效地生成所有排列

问题描述

解决方案

推荐阅读