使用Python中定义的元素值尽可能快地生成排列

Question

尝试生成排列,可以与生成器一起使用或生成列表列表(但我可能需要大量内存？)在Internet和SO上查看,但找不到我为每个元素定义值的版本.

顺便说一下它会有多少种排列？

8个元素,每个值从1到15

这是我的代码,但也许有更好,更快的方法来生成它:

任何提示表示赞赏!

import time
from tqdm import tqdm
def permutations(iterable, r=None):
    # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC
    # permutations(range(3)) --> 012 021 102 120 201 210
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    if r > n:
        return
    indices = range(n)
    cycles = range(n, n-r, -1)
    yield tuple(pool[i] for i in indices[:r])
    while n:
        for i in reversed(range(r)):
            cycles[i] -= 1
            if cycles[i] == 0:
                indices[i:] = indices[i+1:] + indices[i:i+1]
                cycles[i] = n - i
            else:
                j = cycles[i]
                indices[i], indices[-j] = indices[-j], indices[i]
                yield tuple(pool[i] for i in indices[:r])
                break
        else:
            return

plist = []

for item in tqdm(permutations('123456789ABCDEF',8)):
  plist.append(item)


len(plist)

Answer 1

您刚刚复制了itertools.permutations()文档中的代码.这明确指出它大致相当,因为它只是帮助你理解它是什么itertools.permutations().该代码不适用于生产设置.

使用itertools.permutations()自己.该itertools模块旨在实现最高效率.该模块使用C语言编写,并始终优于纯Python实现.

您也在浪费迭代来将值附加到列表中; 每个.append()表达式都需要属性查找和方法调用.您可以plist通过调用list()以下内容构建单个表达式:

plist = list(permutations('123456789ABCDEF', 8))

但是,您真的不想执行该调用,因为这将花费大量时间将所有可能的排列作为单独的对象生成,并且为此分配内存需要花费时间并且会降低您的计算机速度.

用k计算n的k-个子数量!/(n - k)!),n = 15且k = 8,即15!/(15 - 8)!,结果只有25多亿,259_459_200.在一个需要大约30GB内存的64位操作系统上(列表对象为2GB,元组为27G,共享15个1位数字符串的字节数).

如果你真的想要处理这些排列,我只需循环生成器并直接使用每个结果.你仍然需要迭代25亿次,所以它仍然会花费很多时间,但至少你不会尝试将其全部保存在内存中.

或者,始终寻找其他方法来解决您的问题.生成所有可能的排列将产生非常多的可能性.您之前的问题得到了一个答案,指出对于特定问题而言,搜索200kb的可能候选人的数据比针对每个可能的8个排列的8次搜索更有效率.有2.59亿个排列有更大的机会从另一个方向处理您的问题可能会使您的问题空间可管理.