Как получить все возможные перестановки? - PullRequest
Новая
       75

Как получить все возможные перестановки?

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

У меня есть вложенный список 

x = [['a', 'b', 'c'], ['d'], ['e', 'f', ['g', ['h', 'i']]]]

Я хочу сделать все возможные перестановки элементов в подсписках, не выходя за пределы соответствующего подсписка. Ожидаемый результат - это что-то вроде этого: 

[['c', 'b', 'a'], ['d'], ['f', 'e', ['g', ['i', 'h']]]]
[['d'], ['a', 'b', 'c'], ['f', 'e', [['h', 'i'], 'g']]]

Каждый элемент должен храниться в квадратной скобке.

Я рекомендую этот генератор: 

def swap(x):
    if isinstance(x, list):
        res = np.random.choice(x, len(x), replace = False)
        return [list(map(ff, res))]

    else:
        return x

Это дает случайные варианты ожидаемого результата, но мне нужно собрать их все. Как я мог это сделать? Должен ли я сделать: 

my_list = []
for i in range(10000): # not necessary 10000, any huge number
    my_list.append(ff(yy1))

И затем применить уникальную функцию к my_list для выбора уникальных, или есть другая опция?

Ответы [ 3 ]

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

isinstance() + itertools.permutations() - хорошее направление, просто вам нужен их продукт, и некоторое отслеживание, какая перестановка применима к какой части дерева (?) (Я размышлял над генерацией всех возможных обходовдерево): 

import itertools

def plan(part,res):
  if isinstance(part,list) and len(part)>1:
    res.append(itertools.permutations(range(len(part))))
    for elem in part:
      plan(elem,res)
  return res

def remix(part,p):
  if isinstance(part,list) and len(part)>1:
    coll=[0]*len(part)
    for i in range(len(part)-1,-1,-1):
      coll[i]=remix(part[i],p)
    mix=p.pop()
    return [coll[i] for i in mix]
  else:
    return part

def swap(t):
  plans=itertools.product(*plan(t,[]))
  for p in plans:
    yield remix(t,list(p))

for r in swap([['a', 'b', 'c'], ['d'], ['e', 'f', ['g', ['h', 'i']]]]):
  print(r)

plan() рекурсивно находит все "реальные" списки (которые имеют более одного элемента) и создает для них itertools.permutations().

swap() звонки plan(), а затем объединяет перестановки в одну составную мегапермутацию с помощью itertools.product()

remix() создает фактический объект для одного шага мегапермутации. Это немного сложно, потому что я не хотел бороться с отслеживанием древовидной позиции, вместо этого remix() работает в обратном направлении, переходя к самому последнему списку и добавляя его к самому последнему компоненту текущего плана, удаляя его из списка. .

Кажется, что это работает, хотя ваш пример немного длинный, с более простыми входами он имеет управляемый вывод: 

for r in swap([['a', ['b', 'c']], ['d'], 'e']):
  print(r)

[['a', ['b', 'c']], ['d'], 'e']
[['a', ['c', 'b']], ['d'], 'e']
[[['b', 'c'], 'a'], ['d'], 'e']
[[['c', 'b'], 'a'], ['d'], 'e']
[['a', ['b', 'c']], 'e', ['d']]
[['a', ['c', 'b']], 'e', ['d']]
[[['b', 'c'], 'a'], 'e', ['d']]
[[['c', 'b'], 'a'], 'e', ['d']]
[['d'], ['a', ['b', 'c']], 'e']
[['d'], ['a', ['c', 'b']], 'e']
[['d'], [['b', 'c'], 'a'], 'e']
[['d'], [['c', 'b'], 'a'], 'e']
[['d'], 'e', ['a', ['b', 'c']]]
[['d'], 'e', ['a', ['c', 'b']]]
[['d'], 'e', [['b', 'c'], 'a']]
[['d'], 'e', [['c', 'b'], 'a']]
['e', ['a', ['b', 'c']], ['d']]
['e', ['a', ['c', 'b']], ['d']]
['e', [['b', 'c'], 'a'], ['d']]
['e', [['c', 'b'], 'a'], ['d']]
['e', ['d'], ['a', ['b', 'c']]]
['e', ['d'], ['a', ['c', 'b']]]
['e', ['d'], [['b', 'c'], 'a']]
['e', ['d'], [['c', 'b'], 'a']]

24 перестановок, как и ожидалось

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

Не особенно pythonic, но я бы подошел к нему, найдя перестановки индексов, как показано здесь: 


from itertools import permutations
mylist= [[1], [1,2], [1,2,3]]
combinations = list(permutations([i for i in range(len(mylist))]))

print(combinations)

for item in combinations:
  print([mylist[item[i]] for i in range(len(mylist))])

Output:
[(0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), (2, 1, 0)]
[[1], [1, 2], [1, 2, 3]]
[[1], [1, 2, 3], [1, 2]]
[[1, 2], [1], [1, 2, 3]]
[[1, 2], [1, 2, 3], [1]]
[[1, 2, 3], [1], [1, 2]]
[[1, 2, 3], [1, 2], [1]]
0 голосов
/ 09 октября 2019

Рассматривали ли вы использовать itertools?

Доступны явные инструменты комбинирования и перестановки

Из документов :

itertools.permutations (iterable [, r])

Возвращать последовательные перестановки длины r элементов в итерируемом.

Если r не указан или равен None, тогда по умолчанию r соответствует длине итерируемого и генерируются все возможные перестановки полной длины.

Перестановки выводятся в лексикографическом порядке сортировки. Таким образом, если входной повторяемый элемент сортируется, кортежи перестановок будут создаваться в отсортированном порядке.

Элементы обрабатываются как уникальные в зависимости от их положения, а не от их значения. Таким образом, если входные элементы уникальны, повторных значений в каждой перестановке не будет.

itertools.combination (iterable, r)

Возвращает подпоследовательности элементов r длины из входного итерируемого элемента.

Комбинации генерируются в лексикографическом порядке сортировки. Таким образом, если входной повторяемый элемент отсортирован, комбинированные кортежи будут созданы в отсортированном порядке.

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

...