生成前n个正整数的置换: With/without numpy

gux

我写了两段代码，用于返回前 n 个自然数的置换全体：例如当 n = 2 时， 返回 [1,2], [2,1]； n = 3 时, 返回 [1, 2, 3], [1, 3, 2], [2, 1, 3],  [2, 3, 1],  [3, 1, 2],  [3, 2, 1]. 数学上采用同一个原理，区别是一个用numpy的数据结构和方法，另一个用 list.

两段代码如下：

用 numpy 的：

# permutationGenerator

# Author: Xing Gu
# Date: 2021/11/23

def permutation(n):
    """For a positive integer n, returns all the permutations of n as a generator, each permutation being a list of n
    integers. """
    # Manually yield permutation(n) for n=1,2,3.

    import numpy as np

    if n == 0:
        yield np.arange(0, dtype=int)
    elif n == 1:
        yield np.arange(1,2,  dtype=int)
    elif n == 2:
        for item in np.array([[1, 2], [2, 1]], dtype=int):
            yield item
    elif n == 3:
        for item in np.array([[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]], dtype=int):
            yield item
    else:
        # Recursively yield permutation(n) for n>3, the recursion step length being 3.
        for i in range(n):
            for j in range(n):
                if i == j:
                    continue
                for k in range(n):
                    if j == k or i == k:
                        continue
                    im123 = np.array([i + 1, j + 1, k + 1])
                    # the image of 1,2,3 of the permutation sorted in ascending order
                    im123Sorted = np.sort(im123)
                    # To obtain im4plus, first acquire the permutation of n-3, and then change the values to skip the 
                    # images of 1,2,3.
                    # the image of 4,..., n of the permutation
                    im4PlusSorted = np.arange(1, n - 2) + np.concatenate((np.zeros(im123Sorted[0] - 1), \
                                                    np.ones(im123Sorted[1] - im123Sorted[0] - 1), \
                                                    np.ones(im123Sorted[2] - im123Sorted[1] - 1) * 2, \
                                                    np.ones(n - im123Sorted[2]) * 3))
                    for item in permutation(n - 3):
                        im4Plus = im4PlusSorted[item - 1]
                        yield np.concatenate((im123, im4Plus)).astype(int)


if __name__ == '__main__':
    import timeit

    counter = 0
    start = timeit.default_timer()
    for item in permutation(10):
        print(item)
        counter += 1
    stop = timeit.default_timer()
    print('Counter: ', counter)
    print('Time: ', stop - start)

不用 numpy 的：

# permutationGeneratorNieve

# Author: Xing Gu
# Date: 2021/11/23

def permutation(n):
    """For a positive integer n, returns all the permutations of n as a generator, each permutation being a list of n
    integers. """
    # Manually yield permutation(n) for n=1,2,3.
    if n == 0:
        yield []
    elif n == 1:
        yield [1]
    elif n == 2:
        for item in ([[1, 2], [2, 1]]):
            yield item
    elif n == 3:
        for item in ([1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]):
            yield item
    else:
        # Recursively yield permutation(n) for n>3, the recursion step length being 3.
        for i in range(n):
            for j in range(n):
                if i == j:
                    continue
                for k in range(n):
                    if j == k or i == k:
                        continue
                    im123 = [i + 1, j + 1, k + 1]
                    # the image of 1,2,3 of the permutation sorted in ascending order
                    im123Sorted = sorted(im123)
                    # To obtain im4plus, first acquire the permutation of n-3, and then change the values to skip the
                    # images of 1,2,3.
                    # the image of 4,..., n of the permutation
                    for item in permutation(n - 3):
                        im4Plus = []
                        for l in item:
                            if l > im123Sorted[2] - 3:
                                im4Plus.append(l + 3)
                            elif l > im123Sorted[1] - 2:
                                im4Plus.append(l + 2)
                            elif l > im123Sorted[0] - 1:
                                im4Plus.append(l + 1)
                            else:
                                im4Plus.append(l)
                        # Yield a permutation of n.
                        yield im123 + im4Plus


if __name__ == '__main__':
    import timeit

    counter = 0
    start = timeit.default_timer()
    for item in permutation(10):
        print(item)
        counter += 1
    stop = timeit.default_timer()
    print('Counter: ', counter)
    print('Time: ', stop - start)

按理说 numpy相对于python自带的数据结构优化了许多，然而用以上两段代码分别返回前十个正整数的全体置换（3628800个arraies/lists）时，在同一台设备上，前者用时488.1秒，后者29.3秒。用numpy反而慢了十几倍！

问题：（1）当 n 很大时，第一段代码比第二段是否会有更好的表现？（2）在这个任务中是否有更合理的办法使用numpy?