Алгоритм перестановки сетки — фиксированный порядок строк

Представьте себе сетку 3x3:

[A, B, %]
[C, %, D]
[E, F, G]

Проценты % обозначают пустые места/позиции.

Ряды можно перемещать, как бусины на нитке, так что перестановки конфигураций для первого ряда могут быть любыми из:

[A, B, %] or [A, %, B] or [%, A, B]

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

Я пытаюсь создать все возможные сетки с учетом возможных перестановок каждой строки.

На выходе должны получиться следующие сетки:

[A, B, %]    [A, B, %]    [A, B, %]
[C, D, %]    [C, %, D]    [%, C, D]
[E, F, G]    [E, F, G]    [E, F, G]

[A, %, B]    [A, %, B]    [A, %, B]
[C, D, %]    [C, %, D]    [%, C, D]
[E, F, G]    [E, F, G]    [E, F, G]

[%, A, B]    [%, A, B]    [%, A, B]
[C, D, %]    [C, %, D]    [%, C, D]
[E, F, G]    [E, F, G]    [E, F, G]

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

Однако мой алгоритм кажется ужасно неэффективным (~ 1 с на перестановку!!) и выглядит не очень красиво. Мне было интересно, есть ли красноречивый способ сделать это? В питоне в частности.

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

EDIT: 3x3 — это просто пример. Сетка может быть любого размера, и на самом деле важны комбинации строк. Например:

[A, %, C]
[D, E, %, G]
[H, I]

также является допустимой сеткой.

EDIT 2: Буквы должны сохранять свой порядок. Например, [A, %, B] != [B, %, A] и [B, A, %] недействительны.


python algorithm permutation array-algorithms
person Pete Hamilton    schedule 08.04.2012    source источник
comment
Нужно ли это работать для сеток произвольного размера?   -  person Vaughn Cato    schedule 08.04.2012
comment
считается ли [A,B,%] != [B,A,%]?   -  person luke14free    schedule 08.04.2012
comment
Сетка будет произвольного размера, потенциально каждая строка также может иметь разную длину. 3x3 был просто примером.   -  person Pete Hamilton    schedule 08.04.2012
comment
действительно, [A,B,%] считается != [B,A,%]   -  person Pete Hamilton    schedule 08.04.2012

Ответы (4)


arrow_upward
2
arrow_downward

Сначала вы должны получить все желаемые перестановки для каждой строки. Затем вы вычисляете векторное произведение всех строк.

Перестановки строки можно просто вычислить, используя буквы [A,B,%] и изменяя начальный индекс:

import itertools
# Example: line = ['A','B','%']
def line_permutations(line):
   if '%' not in line:
       return [line]
   line.remove('%') # use copy.copy if you don't want to modify your matrix here
   return (line[:i] + ['%'] + line[i:] for i in range(len(line) + 1))

Перекрестное произведение проще всего получить с помощью itertools.product

matrix = [['A','B','%'], ['C', '%', 'D'], ['E', 'F', 'G']]
permutations = itertools.product(*[line_permutations(line) for line in matrix])
for p in permutations:
    print(p)

Это решение является оптимальным с точки зрения требований к памяти и ЦП, поскольку перестановки никогда не пересчитываются.

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

(['%', 'A', 'B'], ['%', 'C', 'D'], ['E', 'F', 'G'])
(['%', 'A', 'B'], ['C', '%', 'D'], ['E', 'F', 'G'])
(['%', 'A', 'B'], ['C', 'D', '%'], ['E', 'F', 'G'])
(['A', '%', 'B'], ['%', 'C', 'D'], ['E', 'F', 'G'])
(['A', '%', 'B'], ['C', '%', 'D'], ['E', 'F', 'G'])
(['A', '%', 'B'], ['C', 'D', '%'], ['E', 'F', 'G'])
(['A', 'B', '%'], ['%', 'C', 'D'], ['E', 'F', 'G'])
(['A', 'B', '%'], ['C', '%', 'D'], ['E', 'F', 'G'])
(['A', 'B', '%'], ['C', 'D', '%'], ['E', 'F', 'G'])
person j13r    schedule 08.04.2012
comment
Возможно, я вас не правильно понял, но простое изменение начального индекса не даст всех перестановок. Хотя это дало бы желаемое решение. - person NeXuS; 08.04.2012
comment
Можете ли вы использовать оператор возврата с аргументами внутри генератора? - person Abhijit; 08.04.2012
comment
@NeXuS: см. ОП. Ряды можно перемещать, как бусины на нитке; Я адаптирую это, чтобы было понятнее. - person j13r; 08.04.2012
comment
@Abhijit Abhijit, это не генератор, пока вы не достигнете выхода. - person j13r; 08.04.2012
comment
@j13r: ты уверен? Проверьте результат выполнения этого в Python 3. - person Abhijit; 08.04.2012
comment
@j13r: Это была единственная причина, по которой мне пришлось писать свой генератор (см. мой ответ) особым образом :-) - person Abhijit; 08.04.2012
comment
A и B всегда должны быть в одном и том же порядке. Подчинится ли этому алгоритм? Выше вы написали ['B', '%', 'A'] который переключает порядок...? - person Pete Hamilton; 08.04.2012
comment
Это выглядит многообещающе, я опробую его в своей реализации и посмотрю, как оно сравнивается с другими решениями здесь. - person Pete Hamilton; 08.04.2012

arrow_upward
1
arrow_downward

Определите функцию, называемую циклом

>>> def cycle(lst):
    while True:
        lst=lst[1:]+lst[0:1] if '%' in lst else lst
        yield lst
  • Учитывая итератор, это сгенерирует и вернет циклический сдвиг влево.
  • Теперь вам нужно передать каждую из строк в сетке генератору циклов для полной итерации, соответствующей длине строки.
  • Теперь используйте itertools.product, чтобы найти все комбинации сгенерированных циклических комбинаций строк.
  • В случае, если нет пустого слота, перестановка цикла не генерируется.

Окончательный результат выглядит следующим образом

>>> for g in list(itertools.product(*[[x for (x,y) in zip(cycle(row),
           range(0,len(row) if '%' in row else 1))] for row in grid])):
    for r in g:
        print r
    print "="*10

Для вашей сетки это сгенерирует

['B', '%', 'A']
['%', 'D', 'C']
['E', 'F', 'G']
===============
['B', '%', 'A']
['D', 'C', '%']
['E', 'F', 'G']
===============
['B', '%', 'A']
['C', '%', 'D']
['E', 'F', 'G']
===============
['%', 'A', 'B']
['%', 'D', 'C']
['E', 'F', 'G']
===============
['%', 'A', 'B']
['D', 'C', '%']
['E', 'F', 'G']
===============
['%', 'A', 'B']
['C', '%', 'D']
['E', 'F', 'G']
===============
['A', 'B', '%']
['%', 'D', 'C']
['E', 'F', 'G']
===============
['A', 'B', '%']
['D', 'C', '%']
['E', 'F', 'G']
===============
['A', 'B', '%']
['C', '%', 'D']
['E', 'F', 'G']
===============
person Abhijit    schedule 08.04.2012

arrow_upward
0
arrow_downward

Наивная реализация:

g=[['A', 'B', '%'],
['C', '%', 'D'],
['E', 'F', 'G']]

from collections import deque
from itertools import product

def rotations(it):
    d = deque(it,len(it))
    for i in xrange(len(it)):
         d.rotate(1)
         yield list(d)

for i in product(*[rotations(x) if '%' in x else [x] for x in g]):
    print i

дает:

(['%', 'A', 'B'], ['D', 'C', '%'], ['E', 'F', 'G'])
(['%', 'A', 'B'], ['%', 'D', 'C'], ['E', 'F', 'G'])
(['%', 'A', 'B'], ['C', '%', 'D'], ['E', 'F', 'G'])
(['B', '%', 'A'], ['D', 'C', '%'], ['E', 'F', 'G'])
(['B', '%', 'A'], ['%', 'D', 'C'], ['E', 'F', 'G'])
(['B', '%', 'A'], ['C', '%', 'D'], ['E', 'F', 'G'])
(['A', 'B', '%'], ['D', 'C', '%'], ['E', 'F', 'G'])
(['A', 'B', '%'], ['%', 'D', 'C'], ['E', 'F', 'G'])
(['A', 'B', '%'], ['C', '%', 'D'], ['E', 'F', 'G'])
person mshsayem    schedule 08.04.2012
comment
Трассировка (последний последний вызов): файл sandbox.py, строка 2, в ‹module› ['C', '%', 'D'] TypeError: индексы списка должны быть целыми числами, а не кортежем - person luke14free; 08.04.2012
comment
Забыл расставить запятые внутри g :p - person mshsayem; 08.04.2012

arrow_upward
0
arrow_downward

Вот. Обратите внимание, что с одной стороны этот подход менее четкий, но он позволяет вычислить перестановки # len(matrix[0])-1 только один раз и использовать их в качестве шаблонов для вывода.

from itertools import permutations,product

def charPermutation(matrix):
    permutation_list=list(permutations(["%%"]+["%s"]*(len(matrix[0])-1))) #Compute once, use infinitely
    perms={i:[] for i in range(len(matrix))}
    for it,line in enumerate(matrix):
        chars=list(set(line)-set(["%"]))
        if sorted(line)==sorted(chars):
            perms[it]+=["".join([str(i) for i in line])]
        else:
            for p in permutation_list:
                perms[it]+=["".join(["".join(p) % tuple(chars)])]
        perms[it]=list(set(perms[it]))
    return product(*[[list(k) for k in i] for i in perms.values()]) 

g=[
   ["A", "B", "%"],
   ["C", "%", "D"],
   ["E", "F", "G"]]

for x in charPermutation(g):
    print [i for i in x]

[['A', '%', 'B'], ['C', 'D', '%'], ['E', 'F', 'G']]
[['A', '%', 'B'], ['%', 'C', 'D'], ['E', 'F', 'G']]
[['A', '%', 'B'], ['C', '%', 'D'], ['E', 'F', 'G']]
[['%', 'A', 'B'], ['C', 'D', '%'], ['E', 'F', 'G']]
[['%', 'A', 'B'], ['%', 'C', 'D'], ['E', 'F', 'G']]
[['%', 'A', 'B'], ['C', '%', 'D'], ['E', 'F', 'G']]
[['A', 'B', '%'], ['C', 'D', '%'], ['E', 'F', 'G']]
[['A', 'B', '%'], ['%', 'C', 'D'], ['E', 'F', 'G']]
[['A', 'B', '%'], ['C', '%', 'D'], ['E', 'F', 'G']]
person luke14free    schedule 08.04.2012
comment
Что делать, если сетка большего размера, скажем, 100*100? Я думаю, что OP просто привел в качестве примера сетку 3X3. - person Abhijit; 08.04.2012
comment
Обычно я пишу только для того, чтобы люди поняли, в чем причина. Тогда лучше, если они смогут реализовать то, что им действительно нужно (и если они смогут это понять). Во всяком случае, это банально. - person luke14free; 08.04.2012
comment
Этот вывод точен и мне нужен, но я не уверен, что его можно масштабировать. Я отредактирую вопрос, чтобы было ясно, что 3x3 был просто примером. - person Pete Hamilton; 08.04.2012
comment
И в конце концов.. пых! Он масштабируется. :П - person luke14free; 08.04.2012
comment
@PeterHamilton Можете ли вы выполнить тест этого алгоритма с большой матрицей (> 15x15)? - person luke14free; 08.04.2012