Find 2^n -2 Combinations Of Elements In A List

I have the following list: list1 = ['g1','g2','g3','g4'] I want to find 2^n-2 combinations where n is the total number of items in the list. For n = 4 the result should be 2^4 -2

Solution 1:

Here's a functional approach using itertools

import itertools as iter

list1 = ['g1', 'g2', 'g3', 'g4']
combinations = [iter.combinations(list1, n) for n in range(1, len(list1))]
flat_combinations = iter.chain.from_iterable(combinations)
result = map(lambda x: [list(x), list(set(list1) - set(x))], flat_combinations)
# [[['g1'], ['g4', 'g3', 'g2']], [['g2'], ['g4', 'g3', 'g1']], [['g3'], ['g4', 'g2', 'g1']],...
len(result)
# 14

Solution 2:

itertools.combinations(iterable, r)

Return r length subsequences of elements from the input iterable. Combinations are emitted in lexicographic sort order. So, if the input iterable is sorted, the combination tuples will be produced in sorted order.

from itertools import combinations
list1 = ['g1','g2','g3','g4']
for n in range(1,len(list1)):
    for i in combinations(list1,n):
        print(set(i), set(list1) - set(i))

out:

{'g1'} {'g2', 'g3', 'g4'}
{'g2'} {'g1', 'g3', 'g4'}
{'g3'} {'g1', 'g2', 'g4'}
{'g4'} {'g1', 'g2', 'g3'}
{'g1', 'g2'} {'g3', 'g4'}
{'g1', 'g3'} {'g2', 'g4'}
{'g1', 'g4'} {'g2', 'g3'}
{'g2', 'g3'} {'g1', 'g4'}
{'g2', 'g4'} {'g1', 'g3'}
{'g3', 'g4'} {'g1', 'g2'}
{'g1', 'g2', 'g3'} {'g4'}
{'g1', 'g2', 'g4'} {'g3'}
{'g1', 'g3', 'g4'} {'g2'}
{'g2', 'g3', 'g4'} {'g1'}

you can try this

Solution 3:

I like the solution from the Chinese coder (I guess). Here's my own solution:

import itertools


def flatten(*z):
    return z


list1 = ['g1','g2','g3','g4']

sublists = []
for i in range(1, len(list1)):
    sublists.extend(itertools.combinations(list1, i))

pairs = []
for a, b in itertools.product(sublists, sublists):
    if len(a) + len(b) == len(list1) and \
    len(set(flatten(*a, *b))) == len(list1):
        pairs.append((a, b))

print(pairs, len(pairs))