Python: Creating possible sublists from 2 lists where the order is not changed

I am having 2 lists and I need to create different sublists where the order shouldn't be used again ( refer to example for clarity)

list1= [ a, b, c, d]
list2= [A, B, C, D]

I need all possible sublists like

[a, B,C,D], [ a,b, C, D], [A,B,c,d], [a,b,c,D] ... there are 2 pow 4 = 16 solutions [looking for 2 pow N solutio开发者_JAVA百科n]

Thank you in advance

---

list1 = ['a', 'b', 'c', 'd']
list2 = ['A', 'B', 'C', 'D']

for i in xrange(2**len(list1)):
    output = []
    for j in xrange(0, len(list1)):
        bit = i & (1 << j)
        if bit == 0:
            output.append(list1[j])
        else:
            output.append(list2[j])
    print output

---

I have a feeling it can be done better, but this works, at least:

from itertools import product
a = "abcd"
A = "ABCD"
print [[a[y] if x[y] else A[y] for y in range(len(x))] \
    for x in product(range(2), repeat=4)]

EDIT: An alternative way:

lists = ["abcd", "ABCD"]
print [[lists[y][i] for i, y in enumerate(x)] \
    for x in product(range(2), repeat=4)]

EDIT 2: A generic solution for any number of lists:

def sublist(*lists):
    if not len(set(len(x) for x in lists)) == 1:
        raise ValueError("Lists must all be the same length")
    length = len(lists[0])
    return [[lists[y][i] for i, y in enumerate(x)] \
        for x in product(range(len(lists)), repeat=length)]

print sublist("ab", "AB", "12")
# [['a', 'b'], ['a', 'B'], ['a', '2'], ['A', 'b'], ['A', 'B'], ['A', '2'], ['1', 'b'], ['1', 'B'], ['1', '2']]

---

recursion is your friend:

def sublists(l1, l2):
    if not l1:
        return [l1]
    sl = sublists(l1[1:], l2[1:])
    return [l1[:1] + l for l in sl] + [l2[:1] + l for l in sl]

Or, if you like generators:

def subgen(l1, l2):
    if not l1:
        yield l1
        return
    for sl in subgen(l1[1:], l2[1:]):
        yield l1[:1] + sl
        yield l2[:1] + sl

---

import itertools
[[(y if selector else x) for (selector, x, y) in zip(lidxs, list1, list2)]  
 for lidxs in itertools.product([0, 1], repeat=4)]

[['a', 'b', 'c', 'd'],
 ['a', 'b', 'c', 'D'],
 ['a', 'b', 'C', 'd'],
 ...
 ['A', 'B', 'c', 'D'],
 ['A', 'B', 'C', 'd'],
 ['A', 'B', 'C', 'D']]

Also:

[[[list1, list2][lidx][i] for (i, lidx) in enumerate(lidxs)] 
 for lidxs in itertools.product([0, 1], repeat=4)]]

Replace [...] for (...) to get a lazy generator. If you prefer the (slightly) more verbose yield instead of one-liners, it can be easily converted. For example the second example, generalized:

def generate_sublists(*lsts):
    for lidxs in itertools.product(range(len(lsts)), repeat=len(lsts[0])):
        yield [lsts[lidx][i] for (i, lidx) in enumerate(lidxs)]

---

from itertools import imap, product

a = "abcd"
A = "ABCD"

print [[[a,A][i][j] for j,i in each] for each in imap(enumerate, product((0, 1), repeat=4))]

[edit]

But this is better, IMO:

from itertools import izip, product

a = 'abcd'
A = 'ABCD'

choices = zip(a, A)

print [[c[i] for c, i in izip(choices, p)] for p in product((0, 1), repeat=4)]

Also this works:

from functools import partial
from itertools import product

a = 'abcd'
A = 'ABCD'

mapped = partial(map, tuple.__getitem__, zip(a, A))
print [mapped(p) for p in product((0, 1), repeat=4)]