перестановки списков-подсписков различной глубины, сохраняя их раздельными на Python - PullRequest
Новая
       12

перестановки списков-подсписков различной глубины, сохраняя их раздельными на Python

1 голос
/ 04 октября 2019

Мне нужно сделать перестановки подсписков различной глубины и хранить их отдельно на Python. Например: 

Input: x = [[a,b],[d],[e, [g,h]]

Output:  
[['a', 'b'], ['d'], ['e', ['g', 'h']]]
[['a', 'b'], ['d'], [['g', 'h'], 'e']]
[['b', 'a'], ['d'], ['e', ['g', 'h']]]
[['b', 'a'], ['d'], [['g', 'h'], 'e']]
[['a', 'b'], ['d'], ['e', ['h', 'g']]]
[['a', 'b'], ['d'], [['h', 'g'], 'e']]
[['b', 'a'], ['d'], ['e', ['h', 'g']]]

Так что мне нужно перебрать все подсписки в подсписках в подсписках и т. Д.

Я пробовал это, но он перебирает подсписки первого уровня ине переставляет ['g', 'h'] часть: 

def product_perms(x):
    perms = [list(map(list,permutations(i))) for i in x]
    for x in product(*perms):
        print(list(x))

Большое спасибо.

1 Ответ

2 голосов
/ 04 октября 2019

Вы можете использовать рекурсию с генератором: 

from collections import Counter
x = [['a','b','c'],['d'],['e','f',['g','h','i']]] 
def can_add(a, b):
    '''checks that the frequency of types in b is <= frequency of types in a'''
    c, d = Counter(map(type, a)), Counter(map(type, b))
    return all(c[k] >= j for k, j in d.items()) and all(isinstance(i, list) or i in a for i in b)

def combo(d, c = []):
   '''main recursive procedure'''
   def _combo(new_d, c = []):
      '''find combinations for individual list'''
      if len(c) == 2:
         yield c
      else:
         for i in filter(lambda x:x not in c, new_d):
            if isinstance(i, list):
               for k in combo(i):
                  if can_add(new_d, c+[k]):
                     yield from _combo(new_d, c+[k])
            else:
                if can_add(new_d, c+[i]):
                  yield from _combo(new_d, c+[i])
   if all(isinstance(i, list) for i in d):
      if len(d) == 1:
         if len(d[0]) == 1:
            yield d
         else:
            yield from map(lambda x:[x], _combo(d[0]))
      else:
         _r = list(combo(d[1:]))
         for i in ([d[0]] if len(d[0]) == 1 else _combo(d[0])):
           if _r:
             for b in _r:
               yield [i, *b]
           else:
              yield i
   elif d:
      yield from _combo(d)

_, *result = combo(x)

Пример вывода: 

[[['a', 'b'], ['d'], ['e', ['g', 'h']]], 
 [['a', 'b'], ['d'], ['e', ['g', 'i']]], 
 [['a', 'b'], ['d'], ['e', ['h', 'g']]], 
 [['a', 'b'], ['d'], ['e', ['h', 'i']]], 
 [['a', 'b'], ['d'], ['e', ['i', 'g']]], 
 [['a', 'b'], ['d'], ['e', ['i', 'h']]], 
 ....
...