How to get all combinations of "sub" lists from a list

Question

So if I start with something like:

x = [a, b, c]
y = [[a], [b], [c], [a,b], [b,c]]

How can I get all of the combinations in which I can make x from elements in y? Something like:

y = [ [[a, b], c], [[b,c], a], [a, b, c]

I have looked into itertools and list comprehension, but still struggling. All elements from original list need to be present in each item of resulting list.

Could you describe your expected result a little more fully/generally? At the moment it looks like you're trying to get something halfway between the partitions and the power set. — Patrick Haugh, Sep 21 '18 at 22:50
To follow on @PatrickHaugh I'm surprised you don't have `[a, b], [b, c], [a, c]` too — Cory Kramer, Sep 21 '18 at 22:51
What would the output be if there are more than three elements? Would you create multiple sublists? i.e `x = [a, b, c, d]; [[[a, b], [c, d]], [[a, b, c], d]]`? — Ajax1234, Sep 21 '18 at 22:55
Something like this for the output of 4 elements: `[ [a,b,c,d], [[a,b],c,d], [a,[b,c],d], [a,b,[c,d]], [[a,c],b,d]], [[a,d],b,c]], ... [[a,b,c],d], [a,[b,c,d]], [b,[a,c,d]]...]` — whla, Sep 21 '18 at 23:03

score 0 · Answer 1 · answered Sep 21 '18 at 23:05

How to get a combination for every item in a list?

Loop over the list, and loop over the list again inside that loop:

x = [a, b, c]
y = []
for i in x:
    for j in x:
        y.append([i, j])

Note that the exact output you asked for is not "a combination for every item in a list" - in fact there does not seem to be consistency in your exact output which means neither this nor anything from a standard library is going to help you, but this should give you a starting point.

score 0 · Answer 2 · answered Sep 22 '18 at 00:21

You can use a recursive function with a generator:

def full_length(d):
  return sum(1 if not isinstance(i, list) else full_length(i) for i in d)

def semi_combos(d, current=[]):
   if len(current) == len(x) - 1:
     yield current
   else:
     for i in d:
       if len(set(current+[i])) == len(current)+1:
         yield from semi_combos(d, current+[i])

def remainder_combos(d, _target, current = []):
  if full_length(current)+len(_target) == len(x):
    yield [_target, *current]
  for i in d:
    if i not in _target and i not in current:
      yield from remainder_combos(d, _target, current+[i])


for x in [['a', 'b', 'c'], ['a', 'b', 'c', 'd']]:
  print([b for i in semi_combos(x) for b in list(remainder_combos(x, i))])

Output:

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

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

It doesn't seem like either of your outputs match? – G_M Sep 22 '18 at 01:30 — G_M, Sep 22 '18 at 01:30

score 0 · Accepted Answer · answered Sep 25 '18 at 17:03

This is now assuming you have a list of valid combinations that can be used. Using a recursive function I was able to get the desired output.

Note: I have done 0 optimization

import numpy


def build_combo(current_set, all_combos):
    global count, req_options
    for each in all_combos:
        if all(len(numpy.intersect1d(each, x)) == 0 for x in current_set):
            inner_set = current_set.copy()
            inner_set.append(each)
            flat = []
            for x in inner_set:
                flat.extend(x)
            if all(x in flat for x in req_options):
                built_combos.append(inner_set)
            else:
                build_combo(inner_set, all_combos)


req_options = ['a', 'b', 'c', 'd', 'e', 'f', 'g']

all_combos = [['a'], ['b'], ['c'], ['d'], ['e'], ['f'], ['g'],
              ['a', 'b'], ['c', 'd'], ['a', 'f'], ['f', 'g'],
              ['a', 'c', 'd'], ['g', 'f', 'e', 'b']]

built_combos = []
build_combo([], all_combos)

option_sets = set()
for combo in built_combos:
    newset = set()
    for element in combo:
        newset.add(frozenset(element))
    option_sets.add(frozenset(newset))

for option_set in option_sets:
    combo_str = ''
    for option in option_set:
        combo_str += '[{}]'.format('+'.join(option))
    print(combo_str)

Output (added '+' signs to printed output for easier reading):

[e][g][c+d][b][f+a]
[a][c][d][f+e+g+b]
[f+g][e][c][d][a+b]
[f+g][e][c+d][a][b]
[f][e][c][g][a][b][d]
[c+a+d][f][e][g][b]
[b][e][f+g][c+a+d]
[f][e][g][c+d][a+b]
[f+g][e][a+b][c+d]
[f][e][g][c+d][a][b]
[e][c][g][b][f+a][d]
[f+g][e][c][a][b][d]
[f][e][c][g][d][a+b]
[a][f+e+g+b][c+d]
[c+a+d][f+e+g+b]

How to get all combinations of "sub" lists from a list

3 Answers3