组合和排列问题

Question

我有一个列表，比方说[(1,1,1),(0,0,0),(0,0,0)]，我想生成q个长度列表中n个元素的所有排列，并舍弃等效项。我的意思是：

输入

[1,1,1,0,0,0,0,0,0] 

输出

[[(1,1,1),(0,0,0),(0,0,0)], <----- keep this
[(1,1,0),(1,0,0),(0,0,0)], <----- keep this
[(1,1,0),(0,1,0),(0,0,0)], <----- disgard this
[(1,1,0),(0,0,1),(0,0,0)], <----- disgard this
[(1,1,0),(0,0,0),(1,0,0)], <----- keep this
...
...
...
...
[(0,0,0),(1,0,0),(1,0,1)], <----- keep this
[(0,0,0),(1,0,0),(0,1,1)], <----- disgard this
[(0,0,0),(0,1,0),(1,0,1)], <----- disgard this
[(0,0,0),(0,1,0),(0,1,1)], <----- disgard this
[(0,0,0),(0,0,1),(1,0,1)], <----- disgard this
[(0,0,0),(0,0,1),(0,1,1)], <----- disgard this
[(0,0,0),(0,0,0),(1,1,1)]] <----- keep this

这是一个非常简单的任务，其中一些嵌套用于cicle，而sum用于函数，但是我无法找到一种使用ipertools实现此目的的方法。有什么建议吗？

谢谢。

Answer 1

这是如何获得排列的方法：

from itertools import permutations 
permut = permutations([1,1,1,0,0,0,0,0,0]) 

for i in list(permut): 
    print(i)

如果只想删除所有重复项，则可以使用sumpy：

from sympy.utilities.iterables import multiset_permutations
list(multiset_permutations([1,1,1,0,0,0,0,0,0]))

[如果需要其他东西，请随时提问。

Answer 2

似乎您想列出从项目清单中执行3次丢弃的所有可能方法，每项包括3张卡片。我建议您对选择进行更好的映射，例如用[3, 2, 0]代替[(0,0,0),(1,0,0),(1,0,1)]，其中[3, 2, 0]表示每个丢弃物列表的起始索引。这种情况可以说明如下：

• [[1,1,1,0,0,0,0,0,0]，取出从index=3开始的项目
• [[1,1,1,0,0,0]，取出从index=2->]开始的项目>
• [[1,1,0]，取出从index=0->]开始的项目>
• []

解决方案的下一步是考虑所有可能的索引选择如何。很明显：

• 第一个索引不超过6（因为列表有9个项目，]，>
• 第二个索引不超过3（因为列表包含6个项目）
• 第三个索引为0（因为列表有0个项目）

通常，我建议生成所有可能的选择并为每个选择手动丢弃：

from itertools import product
d = [1,1,1,0,0,0,0,0,0]
n = 3
starting_indices = [range(len(d)-(n-1)-n*m) for m in range(len(d)//n)]
choices = []
for idx_sequence in product(*starting_indices):
    current_d = d.copy()
    current_choice = []
    for id in idx_sequence:
        current_choice.append(current_d[id: id+n])
        del current_d[id: id+n]
    choices.append(current_choice)
print(choices)
注意：
某些选择可能会重复
更新：

如果将以下行添加到脚本中，则可以消除重复的选择：

choices = set([tuple(tuple(m) for m in n) for n in choices]) #if you need to remove duplicates
choices = [list(list(m) for m in n) for n in choices] #if you need to set type back
输出：
[[0, 0, 0], [1, 1, 1], [0, 0, 0]]
[[0, 0, 0], [1, 0, 0], [1, 1, 0]]
[[0, 0, 0], [1, 1, 0], [1, 0, 0]]
[[0, 0, 0], [0, 0, 0], [1, 1, 1]]
[[1, 1, 1], [0, 0, 0], [0, 0, 0]]
[[1, 0, 0], [0, 0, 0], [1, 1, 0]]
[[1, 0, 0], [1, 1, 0], [0, 0, 0]]
[[1, 1, 0], [1, 0, 0], [0, 0, 0]]
[[1, 0, 0], [1, 0, 0], [1, 0, 0]]
[[1, 1, 0], [0, 0, 0], [1, 0, 0]]