python get groups of combinations that each member

问题:

I'm trying to get groups of permutations/combinations (r=2) that each member appear only once

I used python 'combinations' package to have the combinations.

For example: the members are: a,b,c,d. The combinations are: [a,b],[a,c],[a,d],[b,c],[b,d]...

My desired output is: [ {[a,b],[c,d]},{[a,c],[b,d]},{[a,d],[b,c]}...]

I would like to know what is the terminology for that case and if there is already implementation for that.

Thanks.

回答1:

Here's a way to do it:

from itertools import combinations, chain
l = ['a','b','c','d']
c = list(combinations(l,2))
[set(i) for i in list(combinations(c,2)) if (len(set(l) & set(chain(*i))) == len(l))]
[{('a', 'b'), ('c', 'd')}, {('a', 'c'), ('b', 'd')}, {('a', 'd'), ('b', 'c')}]

Explanation

You can use itertools.combinations twice, in order to get all the 2 tuple combinations from:

list(combinations(l,2))
[('a', 'b'), ('a', 'c'), ('a', 'd'), ('b', 'c'), ('b', 'd'), ('c', 'd')]

And select only those whose set of elements intersect with that of the original list, len(set(l) & set(chain(*i))) == len(l)) for every possible combination.

回答2:

You can find the permutations up to r and then filter the results:

def combinations(d, d1, r, _c = [], _start=[]):
  if len([i for b in _c for i in b]) == len(d1):
    yield _c
  else:
    for i in d:
       if i not in _start:
         if len(_start+[i]) < r:
           yield from combinations(d, d1, r, _c, _start=_start+[i])
         else:
           _d = sorted(_start+[i])
           yield from combinations([i for i in d if i not in _d], d1,r,  _c+[_d], [])

data = ['a', 'b', 'c', 'd']
_r = list(combinations(data, data, 2))
new_d = [a for i, a in enumerate(_r) if a not in _r[:i]]

Output:

[[['a', 'b'], ['c', 'd']], [['a', 'c'], ['b', 'd']], [['a', 'd'], ['b', 'c']], [['b', 'c'], ['a', 'd']], [['b', 'd'], ['a', 'c']], [['c', 'd'], ['a', 'b']]]