python - 鉴于两个项目不能在同一个列表中，如何获得列表的所有组合？

Question

我目前正在尝试查找数字列表的所有可能集合，其中集合中的两个或多个元素不能在同一集合中。

例如，我有一个原始列表 [1, 2, 3, 4, 5, 6] 和一个集合列表 [{1,2}, {3,4}]，这意味着 1 和 2不能在同一组 3 和 4 不能在同一组。

给定这两个输入，程序的结果应该是:

{1, 6, 3, 5}
{1, 6, 4, 5}
{2, 6, 3, 5}
{2, 6, 4, 5}

最终输出中的顺序无关紧要。

编辑:我重写了实现(这次没有递归)。现在我收到一条错误消息，提示我无法从列表中删除某些内容，因为它不存在...

def schedules(overlaps, complete):
print(complete)
final = complete.copy()
print(final)
for sch in complete:
    print(sch)
    for over in overlaps:
        if (over[0] in sch) and (over[1] in sch):
            print("This is an overlap!!!")
            final.remove(sch)
return final

这是上面代码的错误和输出:

[(1, 2, 3, 4), (1, 2, 3, 5), (1, 2, 3, 6), (1, 2, 4, 5), (1, 2, 4, 
6), (1, 2, 5, 6), (1, 3, 4, 5), (1, 3, 4, 6), (1, 3, 5, 6), (1, 4, 
5, 6), (2, 3, 4, 5), (2, 3, 4, 6), (2, 3, 5, 6), (2, 4, 5, 6), (3, 
4, 5, 6)]

[(1, 2, 3, 4), (1, 2, 3, 5), (1, 2, 3, 6), (1, 2, 4, 5), (1, 2, 4, 
6), (1, 2, 5, 6), (1, 3, 4, 5), (1, 3, 4, 6), (1, 3, 5, 6), (1, 4, 
5, 6), (2, 3, 4, 5), (2, 3, 4, 6), (2, 3, 5, 6), (2, 4, 5, 6), (3, 
4, 5, 6)]
(1, 2, 3, 4)
This is an overlap!!!
This is an overlap!!!
Traceback (most recent call last):
  File "schedule.py", line 24, in <module>
    result = schedules(overlaps, list(comb))
  File "schedule.py", line 19, in schedules
    final.remove(sch)
ValueError: list.remove(x): x not in list    

编辑:在 final.remove(sch) 周围添加一个 try，except block 删除了错误，但正如下面评论中所指出的，如果重叠集中有两个以上的元素，则此代码将不起作用。例如:如果重叠现在是 [{1,2}, {3,4,5}] 输出应该是:

{1,6,3}
{1,6,5}
{1,6,4}
{1,6,5}
{2,6,3}
{2,6,5}
{2,6,4}
{2,6,5}

Answer 1

建议:

• 从重叠列表开始，每组仅使用一个元素创建所有排列。
• 将初始列表中未出现在重叠部分的元素添加到每个结果列表中。

在 python 中，这基本上归结为 2 行，适用于任意数量的任意长度的集合:

from itertools import product

init_list =  [1, 2, 3, 4, 5, 6]
overlaps = [{1,2}, {3,4}]

# the 2 lines:
rest = tuple(el for el in init_list if not any(el in ol for ol in overlaps))
[unique + rest for unique in product(*overlaps) if all(u in init_list for u in unique)]

Out[7]: [(1, 3, 5, 6), (1, 4, 5, 6), (2, 3, 5, 6), (2, 4, 5, 6)]