CODEWITHSUNDEEP
pythoncombinations
Joe Emmens
Joe Emmens

Reputation: 147

Group a list of N elements into sub-groups of two or one

I have a list of n numbers, e.g. [1, 2, 3, 4] and I want to write some code in python which finds all possible combinations where the numbers are grouped into either 2s or 1s and all n elements are present.

For example with the n=4 case the solution will be,

[(0, 1, 2, 3), ((0, 1), 2, 3), ((0, 2), 1, 3), ((0, 3), 2, 1),
 ((1, 2), 0, 3), ((1, 3), 0, 2), ((2, 3), 0, 1), ((0, 1), (2, 3)),
 ((0, 2), (1, 3)), ((0, 3), (1, 2))]

To give an intuitive explanation, I am looking for all combinations of four people where they are either in a pair or working alone.

I have tried the following mixture of combinations but I cannot see a clear method of continuing from here,

pairs = list(combinations([0, 1, 2, 3], 2))
groups = list(combinations(pairs, 2))

unique = []
for p in groups:
    if len(set([i for sub in p for i in sub])) == 4:
        unique.append(p)

unique + pairs
>> [((0, 1), (2, 3)),
    ((0, 2), (1, 3)),
    ((0, 3), (1, 2)),
    (0, 1),
    (0, 2),
    (0, 3),
    (1, 2),
    (1, 3),
    (2, 3)]

If I could fill in each entry so that all four numbers were present by inserting them as individuals (not in pairs) this would give my solution.

I don't need to do this for very large lists so I am not overly concerned with running time (I say this as I am aware that my current method can get out of hand quickly with large n).

Any help would be great!

Thanks

Upvotes: 0

Views: 1092

Answers (2)

Joffan
Joffan

Reputation: 1480

This was interestingly tricky. I used the combinations function to pull out each even subset and then wrote a recursive pairing process to make all possible pairings in those even subsets.

from itertools import combinations

def make_pairs(source, pairs=None, used=None):
    if pairs is None: # entry level
        sin = 0
        results = []
        pairs = []
        used = [False] * len(source)
    else:
        sin = 1
        while used[sin]:
            sin +=1
    used[sin] = True
    for dex in range(sin + 1, len(source)):
        if not used[dex]:
            pairs.append( (source[sin], source[dex]))
            if len(pairs)*2 == len(source):
                yield tuple(pairs)
            else:
                used[dex] = True
                yield from make_pairs(source, pairs, used)
                used[dex] = False
            pairs.pop()
    used[sin]=False


def make_ones_and_twos(source):
    yield tuple(source) # all singles case
    inpair = 2
    while inpair <= len(source):
        for paired in combinations(source,inpair): # choose elements going in pairs
            singles = tuple(sorted(set(source)-set(paired))) # others are singleton
            # partition paired into actual pairs
            for pairing in make_pairs(paired):
                yield (pairing+singles)
        inpair += 2

# sample run       
elements = ['a','c','g','t','u']

print(*make_ones_and_twos(elements),sep='\n')

giving output

('a', 'c', 'g', 't', 'u')
(('a', 'c'), 'g', 't', 'u')
(('a', 'g'), 'c', 't', 'u')
(('a', 't'), 'c', 'g', 'u')
(('a', 'u'), 'c', 'g', 't')
(('c', 'g'), 'a', 't', 'u')
(('c', 't'), 'a', 'g', 'u')
(('c', 'u'), 'a', 'g', 't')
(('g', 't'), 'a', 'c', 'u')
(('g', 'u'), 'a', 'c', 't')
(('t', 'u'), 'a', 'c', 'g')
(('a', 'c'), ('g', 't'), 'u')
(('a', 'g'), ('c', 't'), 'u')
(('a', 't'), ('c', 'g'), 'u')
(('a', 'c'), ('g', 'u'), 't')
(('a', 'g'), ('c', 'u'), 't')
(('a', 'u'), ('c', 'g'), 't')
(('a', 'c'), ('t', 'u'), 'g')
(('a', 't'), ('c', 'u'), 'g')
(('a', 'u'), ('c', 't'), 'g')
(('a', 'g'), ('t', 'u'), 'c')
(('a', 't'), ('g', 'u'), 'c')
(('a', 'u'), ('g', 't'), 'c')
(('c', 'g'), ('t', 'u'), 'a')
(('c', 't'), ('g', 'u'), 'a')
(('c', 'u'), ('g', 't'), 'a')

Upvotes: 3

Matteo Zanoni
Matteo Zanoni

Reputation: 4142

This may do it:

from itertools import combinations

elements = [0, 1, 2, 3]

pairs = list(combinations(elements, 2))
groups = list(combinations(pairs, 2))

unique = []
for p in groups:
    if len(set([i for sub in p for i in sub])) == 4:
        unique.append(p)

pairs_with_singles = []
for pair in pairs:
    missing = set(elements) - set(pair)
    pairs_with_singles.append((pair, *missing))

print(unique + pairs_with_singles + [tuple(elements)])

Upvotes: 1

Related Questions