生成前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 的：

1. # permutationGenerator
   
2. 
   
3. # Author: Xing Gu
   
4. # Date: 2021/11/23
   
5. 
   
6. def permutation(n):
   
7.     """For a positive integer n, returns all the permutations of n as a generator, each permutation being a list of n
   
8.     integers. """
   
9.     # Manually yield permutation(n) for n=1,2,3.
   
10. 
    
11.     import numpy as np
    
12. 
    
13.     if n == 0:
    
14.         yield np.arange(0, dtype=int)
    
15.     elif n == 1:
    
16.         yield np.arange(1,2,  dtype=int)
    
17.     elif n == 2:
    
18.         for item in np.array([[1, 2], [2, 1]], dtype=int):
    
19.             yield item
    
20.     elif n == 3:
    
21.         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):
    
22.             yield item
    
23.     else:
    
24.         # Recursively yield permutation(n) for n>3, the recursion step length being 3.
    
25.         for i in range(n):
    
26.             for j in range(n):
    
27.                 if i == j:
    
28.                     continue
    
29.                 for k in range(n):
    
30.                     if j == k or i == k:
    
31.                         continue
    
32.                     im123 = np.array([i + 1, j + 1, k + 1])
    
33.                     # the image of 1,2,3 of the permutation sorted in ascending order
    
34.                     im123Sorted = np.sort(im123)
    
35.                     # To obtain im4plus, first acquire the permutation of n-3, and then change the values to skip the
    
36.                     # images of 1,2,3.
    
37.                     # the image of 4,..., n of the permutation
    
38.                     im4PlusSorted = np.arange(1, n - 2) + np.concatenate((np.zeros(im123Sorted[0] - 1), \
    
39.                                                     np.ones(im123Sorted[1] - im123Sorted[0] - 1), \
    
40.                                                     np.ones(im123Sorted[2] - im123Sorted[1] - 1) * 2, \
    
41.                                                     np.ones(n - im123Sorted[2]) * 3))
    
42.                     for item in permutation(n - 3):
    
43.                         im4Plus = im4PlusSorted[item - 1]
    
44.                         yield np.concatenate((im123, im4Plus)).astype(int)
    
45. 
    
46. 
    
47. if __name__ == '__main__':
    
48.     import timeit
    
49. 
    
50.     counter = 0
    
51.     start = timeit.default_timer()
    
52.     for item in permutation(10):
    
53.         print(item)
    
54.         counter += 1
    
55.     stop = timeit.default_timer()
    
56.     print('Counter: ', counter)
    
57.     print('Time: ', stop - start)
    

复制代码

不用 numpy 的：

1. # permutationGeneratorNieve
   
2. 
   
3. # Author: Xing Gu
   
4. # Date: 2021/11/23
   
5. 
   
6. def permutation(n):
   
7.     """For a positive integer n, returns all the permutations of n as a generator, each permutation being a list of n
   
8.     integers. """
   
9.     # Manually yield permutation(n) for n=1,2,3.
   
10.     if n == 0:
    
11.         yield []
    
12.     elif n == 1:
    
13.         yield [1]
    
14.     elif n == 2:
    
15.         for item in ([[1, 2], [2, 1]]):
    
16.             yield item
    
17.     elif n == 3:
    
18.         for item in ([1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]):
    
19.             yield item
    
20.     else:
    
21.         # Recursively yield permutation(n) for n>3, the recursion step length being 3.
    
22.         for i in range(n):
    
23.             for j in range(n):
    
24.                 if i == j:
    
25.                     continue
    
26.                 for k in range(n):
    
27.                     if j == k or i == k:
    
28.                         continue
    
29.                     im123 = [i + 1, j + 1, k + 1]
    
30.                     # the image of 1,2,3 of the permutation sorted in ascending order
    
31.                     im123Sorted = sorted(im123)
    
32.                     # To obtain im4plus, first acquire the permutation of n-3, and then change the values to skip the
    
33.                     # images of 1,2,3.
    
34.                     # the image of 4,..., n of the permutation
    
35.                     for item in permutation(n - 3):
    
36.                         im4Plus = []
    
37.                         for l in item:
    
38.                             if l > im123Sorted[2] - 3:
    
39.                                 im4Plus.append(l + 3)
    
40.                             elif l > im123Sorted[1] - 2:
    
41.                                 im4Plus.append(l + 2)
    
42.                             elif l > im123Sorted[0] - 1:
    
43.                                 im4Plus.append(l + 1)
    
44.                             else:
    
45.                                 im4Plus.append(l)
    
46.                         # Yield a permutation of n.
    
47.                         yield im123 + im4Plus
    
48. 
    
49. 
    
50. if __name__ == '__main__':
    
51.     import timeit
    
52. 
    
53.     counter = 0
    
54.     start = timeit.default_timer()
    
55.     for item in permutation(10):
    
56.         print(item)
    
57.         counter += 1
    
58.     stop = timeit.default_timer()
    
59.     print('Counter: ', counter)
    
60.     print('Time: ', stop - start)

复制代码

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

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