我需要的代码接受一个列表(最多 n=31
)并返回 n=3
的所有可能子集,而没有任何两个元素在同一子集中重复两次(想想那些每次都与新人以 3 人为一组的人):
list=[1,2,3,4,5,6,7,8,9]
返回
[1,2,3][4,5,6][7,8,9]
[1,4,7][2,3,8][3,6,9]
[1,6,8][2,4,9][3,5,7]
但不是:
[1,5,7][2,4,8][3,6,9]
因为 1 和 7 已经一起出现了(同样,3 和 9)。
我还想对 n=2
的子集执行此操作。
谢谢!!
最佳答案
这是我想出的:
from itertools import permutations, combinations, ifilter, chain
people = [1,2,3,4,5,6,7,8,9]
#get all combinations of 3 sets of 3 people
combos_combos = combinations(combinations(people,3), 3)
#filter out sets that don't contain all 9 people
valid_sets = ifilter(lambda combo:
len(set(chain.from_iterable(combo))) == 9,
combos_combos)
#a set of people that have already been paired
already_together = set()
for sets in valid_sets:
#get all (sorted) combinations of pairings in this set
pairings = list(chain.from_iterable(combinations(combo, 2) for combo in sets))
pairings = set(map(tuple, map(sorted, pairings)))
#if all of the pairings have never been paired before, we have a new one
if len(pairings.intersection(already_together)) == 0:
print sets
already_together.update(pairings)
这打印:
~$ time python test_combos.py
((1, 2, 3), (4, 5, 6), (7, 8, 9))
((1, 4, 7), (2, 5, 8), (3, 6, 9))
((1, 5, 9), (2, 6, 7), (3, 4, 8))
((1, 6, 8), (2, 4, 9), (3, 5, 7))
real 0m0.182s
user 0m0.164s
sys 0m0.012s
关于python - 如何在python中将列表拆分为没有重复元素的子集,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8133347/