时间戳

首页 > 解决方案 > itertools.permutations 是否有模式

python - itertools.permutations 是否有模式

问题描述

当我迭代 itertools.permutations 时，我想知道特定数字组合会出现在哪些索引处，而不是慢慢地迭代整个事物。

例如：

当我有一个等于 foo 的列表时list(itertools.permutations(range(10)))，我想知道在哪些索引处第一个字符将是零，而第十七个字符将是三。一个简单的方法是检查每个组合，看看它是否符合我的要求。

n = 10
foo = list(itertools.permutations(range(n)))
solutions = []

for i, permutation in foo:
    if permutation[0] == 0 and permutation[16] == 3:
        solutions.append(i)

但是，随着 n 变大，这会变得非常慢，并且内存效率非常低。

有没有我可以使用的模式，而不是创建一个长列表，我可以简单地说，如果(a*i+b)%c == 0那时我知道它会适合我的模式。

编辑：实际上我将有许多条件，其中一些还涉及两个以上的职位，因此我希望通过结合这些条件，我可以将可能性的数量限制在可行的程度。此外，100 可能有点大，我预计 n 不会大于 20。

标签： pythonitertools

解决方案

您需要在非固定元素的排列与注册了固定单元格的相应排列之间进行映射。例如，如果您计算 list 上[0, 1, 2, 3, 4]的排列并要求值 1 表示零单元格，值 2 表示第三个单元格，则排列(0, 4, 3)将映射到(1, 0, 4, 2, 3). 我知道，元组对这种情况并不友好，因为它们是不可变的，但列表的insert方法在这里非常有用。这就是为什么我将它们转换为列表，然后再转换回元组。

import itertools

def item_padding(item, cells):
    #returns padding of item, e.g. (0, 4, 3) -> (1, 0, 4, 2, 3)
    listed_item = list(item)
    for idx in sorted(cells):
        listed_item.insert(idx, cells[idx])
    return tuple(listed_item)

array = range(5)
cells = {0:1, 3:2} #indexes and their fixed values
remaining_items = set(list(array)) - set(list(cells.values()))
print(list(map(lambda x: item_padding(x, cells), itertools.permutations(remaining_items))))

输出：

[(1, 0, 3, 2, 4), (1, 0, 4, 2, 3), (1, 3, 0, 2, 4), (1, 3, 4, 2, 0), (1, 4, 0, 2, 3), (1, 4, 3, 2, 0)]

总而言之，列表转换和迭代一样慢。尽管如此，我认为这个算法在概念上是一个很好的例子，它揭示了这里可以做什么。numpy如果您确实需要优化它，请改用它。

更新：

如果array是range(12)（使用 3628800 排列），它在我的笔记本电脑上工作 6 秒。它是返回未填充元组的三倍。

推荐阅读