CODEWITHSUNDEEP
python
Kevin Ramirez Zavalza
Kevin Ramirez Zavalza

Reputation: 1785

python how to generate combinations from a list of lists

I hope you can help me, I want to generate combinations from the following list of lists (to work as a nxn matrix):

   A = [[1, 2, 3],
         [4, 5, 6],
         [7, 8, 9]]

But I need that if e.g I take the first number of the first list, then as a matrix operation, remove the other elements of the column and the row of the selected element and then generate the possible combinations

For example, I choose the 1 on the first list, then the only possible combinations to generate are: (1,5,9) and (1,8,6) because the elimination the row and column.

I'm trying to build a recursive function to achieve that by removing column and row the problem is that I'm not sure about how to build the list with the combinations.

This is that I have so far:

list = []

def combinations(matrix):
    matrix_rows = len(matrix)
    if matrix_rows == 0:
        # Base case
        return matrix
    else:
        # Recursive case
        # Always select first row
        seq = []
        for index, a in enumerate(matrix[0]):
            E = a
            seq.append(E)
            # Remove i from row of index element a
            new_matrix = remove_row(matrix, 0)
            # Remove j from column index of element a
            new_matrix = remove_column(new_matrix, index)
            # Call again with new matrix
            combinations(new_matrix)
        list.append(seq)
    return list

def remove_row(original_matrix, element_row_index):
    new_matrix = []
    if (len(original_matrix)) >= element_row_index:
        new_matrix = original_matrix[:] 
        new_matrix.remove(original_matrix[element_row_index])
    return new_matrix

def remove_column(matrix, index):
    return [(x[0:index] + x[index + 1:]) for x in matrix]

With A matrix from above I'll expect to have: 

A = [[1, 2, 3],
             [4, 5, 6],
             [7, 8, 9]]

print("Result: ", combinations(A))

Result: [[1,5,9], [1,6,8], [2,4,9], [2,6,7], [3,4,8], [3,5,7]]

Anyone can help me? Or give me a suggestion for a better approach

Added: An 4x4 example:

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

Results: [1,6,11,16], [1,6,12,15],[1,7,10,16], [1,7,12,14], [1,8,10, 15], [1,8,11, 14], ....

Upvotes: 1

Views: 426

Answers (1)

ShlomiF
ShlomiF

Reputation: 2905

I think this can be done simply and with no recursion at all.
Basically, you want to choose all the possible permutations of range(n) on the rows (or columns) while going through the columns (or rows respectively) in order.
Here's one easy solution: 

from itertools import permutations
import numpy as np

n = 3
x = np.arange(n ** 2).reshape((n, n)) + 1  # so as to fit in with your example
perms = permutations(range(n))
combinations = [list(x[range(n), p]) for p in perms]
print(combinations)
>> [[1, 5, 9], [1, 6, 8], [2, 4, 9], [2, 6, 7], [3, 4, 8], [3, 5, 7]]

If, however, you're not using numpy-compatible stuff, but rather a list-of-lists, here's a small tweak on the above that works just as well:

x = [[1, 'A'], [2, 'B']]  # a "small" case so it's easy to follow
n = len(x)
index_list = range(n)
perms = permutations(index_list)
combinations = [[x[i][p[i]] for i in index_list] for p in perms]
print(combinations)
>> [[1, 'B'], ['A', 2]]

The above assumes you're still using "square" data. Meaning that the length of each inner list is the same length as the outer list containing them.

Hope that helps and that it does what you meant. If not please comment and I'll correct whatever's needed. I'll leave turning this into a function to the reader ;-)
Good luck!

Upvotes: 4

Related Questions