Комбинации с записями, уникальными в строке и столбце

Question

Используя Python 3, мне нужно вернуть список возможных комбинаций элементов матрицы, в которых ни один элемент в комбинации не разделяет строку или столбец с любым другим элементом матрицы в комбинации.

Например, [[А, В, С], [D, Е, F] [G, Н, I]]

возвращается:
A, E, I
А, F, H
в, D, I
в, F, G
с, Е, G
с, D, Н

Я не могу показаться, чтобы выяснить эффективный способ сделать это ,

Я надеялся, что это может быть достигнуто, если не сказать, производя ВСЕ комбинации, а затем проверяя, соответствуют ли элементы в каждой комбинации уникальному правилу строки и столбца.

Если у кого есть какие-либо указатели, это было бы замечательно.

Answer 1

Я бы атаковал это рекурсивной рутиной.

If only one element in matrix, return it. 
Else 
    for each element in first row 
    choose the element (call it E) 
    call self with that row & column deleted from matrix (list comprehension) 
    for each sequence in returned list: 
     prepend E to the sequence. 

return the list of sequences 

Answer 2

def combMatrix(m): 

     # index each letter with row and colum 
     ll = [[ (y, x.index(y),l.index(x)) for y in x] for x in m] 

     # flatten list 
     flattened = [val for sublist in ll for val in sublist] 

     # no need for deepcopy, it just me first time using it 
     from copy import deepcopy 
     lst2 = deepcopy(flattened) 

     lall = [] 
     temp = [] 
     srowt = set() 
     scolt = set() 
     pospath = [] 

     # loop from one copy of the list over the other indexed list of tuples 
     for el in lst2: 

      row = el[1] 
      col = el[2] 
      for t in flattened: 
       rowt = t[1] 
       colt = t[2] 

       # if row index and column index are different 
       if row != rowt and col != colt: 
        # and if for this tuple row index and column index is not in the visisited 
        # append that tuple, it is a good candidate 
        if rowt not in srowt and colt not in scolt: 
         temp.append(t[0]) 
         srowt.add(rowt) 
         scolt.add(colt) 
        else: 
         # here we append onother candidate to a list of possible path 
         pospath.append(t[0]) 


      temp.append(el[0]) 
      temp = sorted(temp) 
      pospath.append(el[0]) 
      pospath = sorted(pospath) 

      if temp not in lall: 
       lall.append(temp) 
      if pospath not in lall: 
       lall.append(pospath) 

      temp = [] 
      srowt = set() 
      scolt = set() 
      pospath = [] 



     for c, el in enumerate(lall): 
      print(" {} {}".format(c, el)) 


l = [['A','B','C'], 
    ['D','E','F'], 
    ['G','H','I']] 

combMatrix(l) 

ВЫХОД

0 [ 'А', 'Е', 'I']

1 [ 'А', 'F', 'Н']

2 [ 'В', 'D', 'I']

3 [ 'B' 'F' 'G']

4 [ 'C', 'D', 'H']

5 [ 'C', 'E', 'G']