python - 如何指定只允许某些第一个组合的 itertools 排列？

Question

问题:我如何指定我的 itertools.permutations 对象，以便它只包含列表中给出的一个开头的排列？ ( python 3.5)

故事:我有一个谜题，它有 36 个谜题元素，所以理论上有 4e+41 种可能性。如果我用 itertools.permutations 检查它，它将永远计算。因此，我尝试检查哪些 block 适合放在第一位，然后只寻找第二位和第一位，这是可能的。

例如 block 2 不适合放在第一位，然后 itertools.permutations(mylist,2) 不应再包含 (2,1)(2,2)(2,3) 等组合。

mylist = [0,1,2,3]     # ..,34,35  - contains all puzzle blocks 
begin  = [(1,2),(1,3)] # this is the list of possible first blocks, so itertools should only give me combinations, that begin with one of this possibillities

combs = itertools.permutations(mylist,3) # --- THIS IS THE LINE OF THE QUESTION ---

目前，我使用:

for thisposs in combs:
   if thisposs[0:2] in begin:
      checkblock(thisposs)       # check if thisposs is a combination that solves the puzzle

但这样 for 循环仍然会爆炸。我想指定 itertools 对象，这样它就没有所有的可能性，只有那些以数组/元组/列表中的内容开头的可能性:

begin = [(1,2),(1,3)]             # only one of these should be allowed in first two slots

每次我增加一个精度步骤时都会重新计算此数组，因此在优化过程中，它可能会采用如下值:

begin = [1,3,4,5,6]               # after permutations(mylist,1) - still a lot beginnings are possible
begin = [(1,6),(1,7),(5,1),(6,7)] # after permutations(mylist,2) - some combinations didn't work further
begin = [(5,1,2),(5,1,6),(5,1,7)] # after permutations(mylist,3) - the solution can for sure only begin with 5-2-???
# and so on

每次我进行一个“准确度步骤”时，我都会创建一个新的 itertools 对象

combs = itertools.permutations(mylist,n+1)

所以我的问题是:如何指定我的 itertools.permutations 对象，以便它只包含列表中给出的一个开头的排列？

Answer 1

在任何级别，您都希望有一个函数来查看每个开始序列，从可能性集中删除开始序列的元素，然后排列剩余部分。

这是一个可以做到这一点的生成器:

def find_permutations(begin_sequences, full_set):
    for begin_sequence in begin_sequences:
        remaining_set = full_set - set(begin_sequence)
        for ending in itertools.permutations(remaining_set):
            yield begin_sequence + list(ending)

如果你想用你的第一个例子来尝试这个，试试这个。 (请注意，如果你打印出来，因为你的 full_set 太大了，你可能会在那里停留一段时间。出于测试目的，你可能想将它减少到 8 之类的东西。):

full_set = set(range(1,37))
for p in find_permutations([[1], [3], [4], [5], [6]], full_set):
    print(p)

你的最后一个例子是这样的:

for p in find_permutations([[5,1,2], [5,1,6], [5,1,7]], full_set):
    print(p)