All possibilities to split a list into two lists

Question

I have a list with some elements and want to iterate over all possible ways to divide this list into two lists. By that I mean all combinations, so the order doesn't matter (i.e. Element 1 and 3 could be in the one list and Element 2 in the other). Currently I do it like this, where facs is my initial list:

patterns = []
for i in range(2**(len(facs)-1)):
    pattern = []
    for j in range((len(facs)-1)):
        pattern.append(i//(2**j)%2)
    patterns.append(pattern)

for pattern in patterns:
    l1 = [facs[-1]]
    l2 = []
    for i in range(len(pattern)):
        if pattern[i] == 1:
            l1.append(facs[i])
        else:
            l2.append(facs[i])

So I basically create a list of length 2^(len(facs)-1) and fill it with every possible combination of ones and zeros. I then 'overlay' every pattern with facs, except for the last element of facs which is always in l1, as I'd otherwise get every result twice, as I handle two lists the same, no matter what lists is l1 or l2.

Is there a faster and more elegant (shorter/more pythonic) way to do this?

Answer 1

itertools has product() which could be used to generate the masks and izip() which could combine the lists for easy filtering. As a bonus, since they return iterators, they don't use much memory.

from itertools import *

facs = ['one','two','three']

l1 = []
l2 = []
for pattern in product([True,False],repeat=len(facs)):
    l1.append([x[1] for x in izip(pattern,facs) if x[0]])
    l2.append([x[1] for x in izip(pattern,facs) if not x[0]])

Answer 2

Just extending @Ouroborus solution using filters and keeping the results together:

import itertools as it

# itertools recipe
def partition(pred, iterable):
    t1, t2 = it.tee(iterable)
    return it.filterfalse(pred, t1), filter(pred, t2)

>>> facs = ['one','two','three']
>>> [[[x[1] for x in f] for f in partition(lambda x: x[0], zip(pattern, facs))]
...  for pattern in product([True, False], repeat=len(facs))]
[[[], ['one', 'two', 'three']],
 [['three'], ['one', 'two']],
 [['two'], ['one', 'three']],
 [['two', 'three'], ['one']],
 [['one'], ['two', 'three']],
 [['one', 'three'], ['two']],
 [['one', 'two'], ['three']],
 [['one', 'two', 'three'], []]]