生成前n个正整数的置换: With/without numpy
我写了两段代码，用于返回前 n 个自然数的置换全体：例如当 n = 2 时， 返回 , ； n = 3 时, 返回 , , ,,,. 数学上采用同一个原理，区别是一个用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([, ], dtype=int):
yield item
elif n == 3:
for item in np.array([, , , , , ], 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()
# 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 - 1), \
np.ones(im123Sorted - im123Sorted - 1), \
np.ones(im123Sorted - im123Sorted - 1) * 2, \
np.ones(n - im123Sorted) * 3))
for item in permutation(n - 3):
im4Plus = im4PlusSorted
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
elif n == 2:
for item in ([, ]):
yield item
elif n == 3:
for item in (, , , , , ):
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 =
# 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 - 3:
im4Plus.append(l + 3)
elif l > im123Sorted - 2:
im4Plus.append(l + 2)
elif l > im123Sorted - 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?
页:
[1]