How to split a list into subsets without duplicate elements in python

Question

I need code that takes a list (up to n=31 ) and returns all possible subsets of n=3 without two repeating elements in the same subset twice (think of people who join groups of 3 with new people every time):

 list=[1,2,3,4,5,6,7,8,9] 

and returns

 [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] 

but not:

 [1,5,7][2,4,8][3,6,9] 

because 1 and 7 appeared together (similarly, 3 and 9).

I would also like to do this for n=2 subsets. Thanks!

Answer 1

Try the following:

 from itertools import permutations lst = list(range(1, 10)) n = 3 triplets = list(permutations(lst, n)) triplets = [set(x) for x in triplets] def array_unique(seq): checked = [] for x in seq: if x not in checked: checked.append(x) return checked triplets = array_unique(triplets) result = [] m = n * 3 for x in triplets: for y in triplets: for z in triplets: if len(x.union(y.union(z))) == m: result += [[x, y, z]] def groups(sets, i): result = [sets[i]] for x in sets: flag = True for y in result: for r in x: for p in y: if len(r.intersection(p)) >= 2: flag = False break else: continue if flag == False: break if flag == True: result.append(x) return result for i in range(len(result)): print('%d:' % (i + 1)) for x in groups(result, i): print(x) 

Output for n = 10: http://pastebin.com/Vm54HRq3

Answer 2

Here is what I came up with:

 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) 

Fingerprints:

 ~$ 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 

Answer 3

Here is my attempt at a fairly general solution to your problem.

 from itertools import combinations n = 3 l = range(1, 10) def f(l, n, used, top): if len(l) == n: if all(set(x) not in used for x in combinations(l, 2)): yield [l] else: for group in combinations(l, n): if any(set(x) in used for x in combinations(group, 2)): continue for rest in f([i for i in l if i not in group], n, used, False): config = [list(group)] + rest if top: # Running at top level, this is a valid # configuration. Update used list. for c in config: used.extend(set(x) for x in combinations(c, 2)) yield config break for i in f(l, n, [], True): print i 

However, it is very slow for high values ​​of n , too slow for n=31 . I don’t have time right now to try to improve speed, but I can try later. Suggestions are welcome!