>我目前正在尝试找到数字列表中所有可能的数字集合，其中集合中的两个或多个元素不能在同一集合中。
例如，我有一个原始列表 [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(周围的块删除了错误，但如下面的注释中所述，如果重叠集中有两个以上的元素，则此代码将不起作用。例如：如果重叠现在是 [{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}
建议：
- 从重叠列表开始，并为每个集合仅使用一个元素创建所有排列。
- 将初始列表中未出现在重叠中的元素添加到每个结果列表中。
在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)]
这应该适用于任意数量的任意长度的集合，一次只从列表中删除每个集合的 1 个元素。下面的两个版本产生相同的结果，第二个版本使用单个列表理解，虽然简洁，但有点难以阅读。
首先，它过滤集列表，以仅获取作为原始列表子集的集。然后，它使用itertools.product从每个集合中使用 1 个元素派生所有组合，然后为每个结果从原始列表中删除这些元素。
from itertools import product
l = [1, 2, 3, 4, 5, 6]
test_sets = [{1, 2}, {3, 4}]
result = []
subsets = [u for t in test_sets for u in combinations(t, 2) if set(u).issubset(set(l))]
for s in set(product(*subsets)) if len(test_sets) > 1 else subsets:
result.append({r for r in l if r not in s})
print(result)
结果
[{2, 4, 5, 6}, {2, 3, 5, 6}, {1, 4, 5, 6}, {1, 3, 5, 6}]
这段代码有效：
def schedules(overlaps, complete):
final = complete.copy()
for sch in complete:
for over in overlaps:
if (over[0] in sch) and (over[1] in sch):
try:
final.remove(sch)
except:
continue
return final
上面问题中的错误是由于我试图删除第一个列表两次引起的，因为它有两个重叠。我试了一下，除了阻止通过它。
我想知道是否有更好或更"pythonic"的方法可以做到这一点。如果您有任何改进，请告诉我！
这应该可以解决问题：
from itertools import combinations # to fill the rest of the sequence
# define a recursive function
# it begins to fill the sequences with the mutually exclusive sets
# but also tries to skip them
# it tries to construct only valid combinations
# so it should also perform for larger sets of numbers
def create_sequences(start_sequence, to_length, all_numbers, mutual_exclusive_sets, collect_sequences_in=None):
# leave it up to the user if he want's to pass a list
# if not just create one but for recursive calls just
# reuse the list to avoid garbage collection
result= collect_sequences_in if collect_sequences_in is not None else list()
curr_len= len(start_sequence)
if curr_len == to_length:
# well this is just for safety
result.append(start_sequence)
return result
# create a working copy, so we can remove one item
# (one set of elements which are mutually exclusive)
# so we can pass it to the next recursion if needed
# without spoiling anything
mutual_exclusive_sets= list(mutual_exclusive_sets)
if len(mutual_exclusive_sets) > 0:
# there are mutually exclusive sets left, so grab
# one, during this method call we will just work
# with that set, adding 0 or one elements to the
# sequence and leaving the rest up to a subsequent
# call (if adding one element doesn't complete
# the sequence)
mutual_exclusive_set= mutual_exclusive_sets.pop()
for value in mutual_exclusive_set:
if value in start_sequence:
# that may not be (should only happen if mual_exculsive_sets overlap)
return result
# ok so now call the function with the same sequence
# after removing the one set (this is the case in which
# we don't take any value from the set --> in your example
# that wouldn't be necessary since it will not produce
# a complete sequence and skip this anyways ;-)
create_sequences(list(start_sequence), to_length, all_numbers, mutual_exclusive_sets, collect_sequences_in=result)
# now the case that we take exactly one element from the set
# and add it to the sequence
for value in mutual_exclusive_set:
work_sequence= start_sequence + [value]
if len(work_sequence) == to_length:
result.append(work_sequence)
else:
create_sequences(work_sequence, to_length, all_numbers, mutual_exclusive_sets, collect_sequences_in=result)
elif to_length - curr_len <= len(all_numbers):
# no mutual exclusive sets left, so now add from all_numbers
for tup in combinations(all_numbers, to_length - curr_len):
result.append(start_sequence + list(tup))
else:
# we would have to fill the sequence with items of all_numbers
# but there are no sufficient elements, so skip this step and
# leave result as it is (this was a dead-end --> like if we
# chose to skip one of the mutually exclusive sets in your example
# data --> but e.g. if you run the same with to_length=3 it is relevant)
pass
return result
对于以下设置：
all_numbers= [1, 2, 3, 4, 5, 6]
mutual_exclusive= [{1, 2}, {3, 4}]
all_numbers_tmp= list(all_numbers)
for me in mutual_exclusive:
for n in me:
all_numbers_tmp.remove(n)
create_sequences([], 4, all_numbers_tmp, mutual_exclusive)
它返回：
Out[27]: [[3, 1, 5, 6], [3, 2, 5, 6], [4, 1, 5, 6], [4, 2, 5, 6]]
这是一种更简单的方法，可以使用模块中的combinations以及all和any函数获得所需的输出itertools：
from itertools import combinations
def get_combs(ranges, forbidden, r):
for comb in combinations(ranges, r):
if not any(all(k in comb for k in elm) for elm in forbidden):
yield set(comb)
ranges = range(1, 7)
forbidden = [{1, 2}, {3, 4}]
r = 4
combs = list(get_combs(ranges, forbidden, r))
print(combs)
输出：
[{1, 3, 5, 6}, {1, 4, 5, 6}, {2, 3, 5, 6}, {2, 4, 5, 6}]
您可以将递归与生成器一起使用。此解决方案首先查找所需长度的所有组合，然后根据匹配set进行筛选：
data, d1 = [1, 2, 3, 4, 5, 6], [{1,2}, {3,4}]
l = len([i for b in d1 for i in b])
def _filter(_d):
return all(len(_d&c) < 2 for c in d1)
def combo(d, c = []):
if len(c) == l:
yield c
else:
for i in filter(lambda x:x not in c, d):
yield from combo(d, c+[i])
r = [i for i in combo(data) if _filter(set(i))]
输出：
[[1, 3, 5, 6], [1, 3, 6, 5], [1, 4, 5, 6], [1, 4, 6, 5], [1, 5, 3, 6], [1, 5, 4, 6], [1, 5, 6, 3], [1, 5, 6, 4], [1, 6, 3, 5], [1, 6, 4, 5], [1, 6, 5, 3], [1, 6, 5, 4], [2, 3, 5, 6], [2, 3, 6, 5], [2, 4, 5, 6], [2, 4, 6, 5], [2, 5, 3, 6], [2, 5, 4, 6], [2, 5, 6, 3], [2, 5, 6, 4], [2, 6, 3, 5], [2, 6, 4, 5], [2, 6, 5, 3], [2, 6, 5, 4], [3, 1, 5, 6], [3, 1, 6, 5], [3, 2, 5, 6], [3, 2, 6, 5], [3, 5, 1, 6], [3, 5, 2, 6], [3, 5, 6, 1], [3, 5, 6, 2], [3, 6, 1, 5], [3, 6, 2, 5], [3, 6, 5, 1], [3, 6, 5, 2], [4, 1, 5, 6], [4, 1, 6, 5], [4, 2, 5, 6], [4, 2, 6, 5], [4, 5, 1, 6], [4, 5, 2, 6], [4, 5, 6, 1], [4, 5, 6, 2], [4, 6, 1, 5], [4, 6, 2, 5], [4, 6, 5, 1], [4, 6, 5, 2], [5, 1, 3, 6], [5, 1, 4, 6], [5, 1, 6, 3], [5, 1, 6, 4], [5, 2, 3, 6], [5, 2, 4, 6], [5, 2, 6, 3], [5, 2, 6, 4], [5, 3, 1, 6], [5, 3, 2, 6], [5, 3, 6, 1], [5, 3, 6, 2], [5, 4, 1, 6], [5, 4, 2, 6], [5, 4, 6, 1], [5, 4, 6, 2], [5, 6, 1, 3], [5, 6, 1, 4], [5, 6, 2, 3], [5, 6, 2, 4], [5, 6, 3, 1], [5, 6, 3, 2], [5, 6, 4, 1], [5, 6, 4, 2], [6, 1, 3, 5], [6, 1, 4, 5], [6, 1, 5, 3], [6, 1, 5, 4], [6, 2, 3, 5], [6, 2, 4, 5], [6, 2, 5, 3], [6, 2, 5, 4], [6, 3, 1, 5], [6, 3, 2, 5], [6, 3, 5, 1], [6, 3, 5, 2], [6, 4, 1, 5], [6, 4, 2, 5], [6, 4, 5, 1], [6, 4, 5, 2], [6, 5, 1, 3], [6, 5, 1, 4], [6, 5, 2, 3], [6, 5, 2, 4], [6, 5, 3, 1], [6, 5, 3, 2], [6, 5, 4, 1], [6, 5, 4, 2]]