How to get multiple combinations of multiple lists in python (Multiple n Choose K or nCr)

Question

I have been looking on google and stack overflow for a few hours and I am sure there is an answer for what this is mathematically or perhaps it is just what the calculation is, which would be (nCr * nCr * nCr etc.,) combinations of multiple groups.

However, to phrase what I am trying to do in Python: I am trying to find all combinations of a list of multiple lists and iterate through all those combinations.(I have been struggling with how to phrase it, see below for a visual)

I have figured out if I want to pick one item from each list, total of 4 items, print all 4 item combinations.

This code I have works for that first part:

a = [[1,2,3,4,5],[6,7,8,9],[10,11,12,13,14],[15,16,17,18,19]]

r=[[]]
for x in a:
    t = []
    for y in x:
        for i in r:
            t.append(i+[y])
    r = t

print (r)

Output:

[[1, 6, 10, 15], 
[2, 6, 10, 15], 
[3, 6, 10, 15], 
[4, 6, 10, 15], 
[5, 6, 10, 15],...

Which is exactly what I am trying to do, I want to select an item from these 4 lists and see all combinations, which this does. Great!

However, I want to scale this and I cannot figure out how, for example, pick 2 items from each list, and display all combinations.

So for this code to output something like this instead:

Output:

[[[1, 2],[7,9],[10,14],[15,19]] , 
[[1, 3],[7,9],[10,14],[15,19]] , 
[[1, 4],[7,9],[10,14],[15,19]]....

What modifications to my python code above to do I need to make, to get this output.

Let me know if you need additional information, the question is just hard to phrase without sounding redundant.

Answer 1

The factorial increase in this problem might cause some memory problems even for small lists. That's being said, here is my approach to this problem:

• Let list a = [a_1, a_2, ..., a_p]. Each element (a_i) is also a list. I will take the k combinations of each element in a and call it Z
• Z = [C(a_1,k), C(a_2,k), ..., C(a_p, k)]
• Then Z[C(a_1,k)[0], C(a_2,k)[0], ..., C(a_3,k)[0]] will give me the first combination of the combinations.
• I will iterate over combinations of combinations until no combinations left.

Here is an example:

• a = [[1,2,3], [4,5,6]] and k=2 (choose k)
• Z = [[(1, 2), (1, 3), (2, 3)], [(4, 5), (4, 6), (5, 6)]]
• Then the first combination of combinations will be [(1,2), (4,5)]
• Second combination of combinations will be [(1,2), (4,6)]
• I will iterate over all 9 combination of combinations.

Here is the class for the python:

class Comb_k:
    def __init__(self, a, k):
        self.Z = [list(combinations(i, k)) for i in a] # k combinations of each list inside a
        self.ns = [len(i)-1 for i in self.Z] # length of the each combination in Z
        self.p = len(a) # length of a
        self.pos = self.p*[0] # I will keep track of which combination in each will be returned
        self.pos[-1] = -1 # I will increase the combination index for each return
        
    def __iter__(self):
        return self
    
    def __next__(self):
        Z = self.Z
        p = self.p        
        self.pos = self.next_i()
        return [z[c] for z,c in zip(Z, self.pos)]      
            
    def next_i(self):
        '''
        This will iterate the next combination
        '''
        pos = self.pos
        ns = self.ns
        p = self.p
        for i in range(p-1, -1, -1):
            c = pos[i]
            n = ns[i]    
            if c == n:
                pos[i] = 0
            else:
                pos[i] += 1
                return pos
        raise GeneratorExit('End of the Combinations')

a = [[1,2,3], [4,5,6]]
comb_k = Comb_k(a, k = 2)
[next(comb_k) for _ in range(9)] # (3 choose 2)x(3 choose 2) = 9

This will return the following list:

[[(1, 2), (4, 5)],
 [(1, 2), (4, 6)],
 [(1, 2), (5, 6)],
 [(1, 3), (4, 5)],
 [(1, 3), (4, 6)],
 [(1, 3), (5, 6)],
 [(2, 3), (4, 5)],
 [(2, 3), (4, 6)],
 [(2, 3), (5, 6)]]

For convenience, the class is a generator, so it is not returning the all combinations at once.