使用itertools从某一点开始连续排列

Question

我有一个大的排列集，我想运行和运行。

from itertools import permutations
perms = permutations([0,1,2,3,4,5,6,7,8,9,10,11,12,13,15,16], 6)

我正在使用一个简单的next调用来降低内存使用。

combination = perm.next()
processing = True
while processing:
try:
# using combination in code then end by calling next
# do_work(combination)   
combination = perm.next()  
except:
print(combination) # (0,1,2,3,4,23)
processing = False

所有这些都可以正常工作。但我注意到，如果我停止它，我必须从头再来。有没有办法让我从上一个点继续跑下去?

例如:

(0,1,2,3,4,23)

下一项工作在哪里:

(0,1,2,3,4,24)

?

更新:许多伟大的解决方案!谢谢大家

Answer 1

您可以定义一个类来管理排列并像列表一样运行:

from math import factorial
from collections.abc import Sequence
class Permutations(Sequence):

def __init__(self,data,samples=None):
self._data    = data
self._samples = samples
self._size    = 0
self._lenData = 0
def __len__(self):
if self._lenData  != len(self._data):
self._lenData  = len(self._data)
samples        = min(self._lenData,self._samples or self._lenData)
self.size      = factorial(self._lenData)//factorial(self._lenData-samples)
return self.size

def __getitem__(self,index):
if isinstance(index,slice):
return map(self.__getitem__,range(len(self))[index])
scale     = len(self)
remaining = list(self._data)
result    = []
for p in range(min(self._lenData,self._samples or self._lenData)):
scale //= (len(self._data)-p)
i,index = divmod(index,max(1,scale))
result.append(remaining.pop(i))
return tuple(result)

类除了使用几个整数来管理大小变化外，不使用额外的存储空间。它甚至支持对引用列表的动态更改。

使用例子:

L = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,15,16]
P = Permutations(L,6)
len(P)   # 5765760
P[6]     # (0, 1, 2, 3, 4, 11)
for perm in P[6:16]: print(perm)
(0, 1, 2, 3, 4, 11)
(0, 1, 2, 3, 4, 12)
(0, 1, 2, 3, 4, 13)
(0, 1, 2, 3, 4, 15)
(0, 1, 2, 3, 4, 16)
(0, 1, 2, 3, 5, 4)
(0, 1, 2, 3, 5, 6)
(0, 1, 2, 3, 5, 7)
(0, 1, 2, 3, 5, 8)
(0, 1, 2, 3, 5, 9)
for perm in P[-3:]: print(perm)
(16, 15, 13, 12, 11, 8)
(16, 15, 13, 12, 11, 9)
(16, 15, 13, 12, 11, 10)

在你离开的地方，你可以存储索引或排列。因为类的行为类似于列表，所以可以使用bisect模块从已知的排列中获得下一个索引:

from bisect import bisect_right
lastPermute = P[123]              # (0, 1, 2, 3, 16, 6)
i = bisect_right(P,lastPermute)
print(i)                          # 124

您甚至可以使用它来获得随机排列，而不必在列表中生成它们:

random.choice(P)
(9, 7, 10, 5, 2, 4)    
random.sample(P,3)
[(15, 0, 13, 8, 10, 9), (9, 13, 3, 4, 8, 10), (1, 12, 0, 3, 6, 9)]

Answer 2

您可以将其pickle到文件中并重新加载以继续下一次运行。

开始使用:

>>> from itertools import permutations, islice
>>> perms = permutations([0,1,2,3,4,5,6,7,8,9,10,11,12,13,15,16], 6)
>>> *islice(perms, 3),
((0, 1, 2, 3, 4, 5), (0, 1, 2, 3, 4, 6), (0, 1, 2, 3, 4, 7))

保存状态以供以后使用(实际上会保存到一个文件中):

>>> import pickle
>>> pickled = pickle.dumps(perms)
>>> type(pickled), len(pickled)
(<class 'bytes'>, 135)

恢复并继续:

>>> restored = pickle.loads(pickled)
>>> *islice(restored, 3),
((0, 1, 2, 3, 4, 8), (0, 1, 2, 3, 4, 9), (0, 1, 2, 3, 4, 10))