有效地生成所有排列

Question

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

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

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

Answer 1

这是一个 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]]

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

Answer 2

更新：更快的版本

由于避免了不必要的计算，该解决方案比我原来的答案快大约 5 倍。这种方法通过从一个角扩展来构建一个数组，使用与Superrain 的答案中解释的相同基本思想，但速度要快得多，因为它避免了不必要的工作。

def faster_permutations(n):
    # empty() is fast because it does not initialize the values of the array
    # order='F' uses Fortran ordering, which makes accessing elements in the same column fast
    perms = np.empty((np.math.factorial(n), n), dtype=np.uint8, order='F')
    perms[0, 0] = 0

    rows_to_copy = 1
    for i in range(1, n):
        perms[:rows_to_copy, i] = i
        for j in range(1, i + 1):
            start_row = rows_to_copy * j
            end_row = rows_to_copy * (j + 1)
            splitter = i - j
            perms[start_row: end_row, splitter] = i
            perms[start_row: end_row, :splitter] = perms[:rows_to_copy, :splitter]  # left side
            perms[start_row: end_row, splitter + 1:i + 1] = perms[:rows_to_copy, splitter:i]  # right side

        rows_to_copy *= i + 1

    return perms

我的机器上的计时n=11：

def faster_permutations(n):
    # empty() is fast because it does not initialize the values of the array
    # order='F' uses Fortran ordering, which makes accessing elements in the same column fast
    perms = np.empty((np.math.factorial(n), n), dtype=np.uint8, order='F')
    perms[0, 0] = 0

    rows_to_copy = 1
    for i in range(1, n):
        perms[:rows_to_copy, i] = i
        for j in range(1, i + 1):
            start_row = rows_to_copy * j
            end_row = rows_to_copy * (j + 1)
            splitter = i - j
            perms[start_row: end_row, splitter] = i
            perms[start_row: end_row, :splitter] = perms[:rows_to_copy, :splitter]  # left side
            perms[start_row: end_row, splitter + 1:i + 1] = perms[:rows_to_copy, splitter:i]  # right side

        rows_to_copy *= i + 1

    return perms

原答案：

基于Super Rain 的回答，这是一个更快的版本，具有更高效的内存访问模式：

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

这本质上是 Super Rain 版本的转置。它更有效，因为访问的内存位置更接近。

在我的机器上，它的速度大约是原始版本的 2 倍（0.05 秒 vs 0.12 秒n=10）。