Grid Permutation Algorithm - Fest Row Bestellen

Question

Stellen Sie sich ein 3x3:

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

Die Prozent % für leere Räume/Positionen stehen.

Die Reihen kann wie Perlen auf einer Schnur bewegt werden, so daß die Permutationen für die Konfigurationen für die erste Zeile einer der sein könnten:

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

ähnliche Weise für die zweite Reihe. Die dritte Zeile enthält keine leeren Slots und kann daher nicht geändert werden.

Ich versuche, alle möglichen Gitter zu produzieren, gegeben die möglichen Permutationen jeder Reihe.

Der Ausgang sollte die folgenden Rastern erzeugen:

[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] 

habe ich versucht, ein Verfahren zur Herstellung durch jede Reihe der Suche und Verschieben der Raum links und rechts, dann neue Netze und ausgeschaltet, dass recursing erzeugen. Ich behalte alle Gitter in einem Satz und stelle sicher, dass ich nur Positionen erzeuge, die noch nicht untersucht wurden, um eine unendliche Rekursion zu verhindern.

Allerdings scheint mein Algorithmus horrend ineffizient zu sein (~ 1s pro Permutation !!) und sieht auch nicht sehr gut aus. Ich habe mich gefragt, ob es einen beredten Weg gab, dies zu tun? In Python insbesondere.

Ich habe einige vage Ideen, aber ich bin mir sicher, dass es eine Möglichkeit gibt, dies zu tun, die kurz und einfach ist, die ich übersehe.

EDIT: 3x3 ist nur ein Beispiel. Gitter könnte jede Größe haben und es sind wirklich die Reihenkombinationen, die wichtig sind. Zum Beispiel:

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

ist auch ein gültiges Raster.

EDIT 2: Die Buchstaben müssen ihre Reihenfolge beibehalten. Zum Beispiel [A, %, B] != [B, %, A] und [B, A, %] ist nicht gültig

Answer 1

Zuerst müssen Sie alle gewünschten Permutationen für jede Zeile erhalten. Dann berechnen Sie das Kreuzprodukt aller Linien.

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)) 

Das Kreuzprodukt ist am einfachsten itertools.product

zu erreichen unter Verwendung von:

Die Permutationen einer Linie kann, indem die Buchstaben [A, B,%] und Variation der Ausgangsindex berechnet einfach

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

Diese Lösung ist hinsichtlich der Speicher- und CPU-Anforderungen optimal, da Permutationen nie neu berechnet werden.

Beispiel Ausgang:

(['%', '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']) 

Answer 2

definieren eine Funktion aufgerufen Zyklus

>>> def cycle(lst): 
    while True: 
     lst=lst[1:]+lst[0:1] if '%' in lst else lst 
     yield lst 

• ein Iterator Gegeben ist, wird diese generieren und eine zyklische Linksverschiebung zurück.
• Nun muss man jede der Reihen in dem Gitter zu dem Zyklus Generator für die Gesamt Iterationsdurchgang die Länge der Reihe
• Nun itertools.product passend verwenden, um alle Kombinationen der erzeugten Reihe zyklischen Kombinationen zu finden.
• Falls es keine leeren Slot, wird kein Zyklus Permutation

Das Endergebnis erzeugt als

>>> 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 

Für Ihre Grid folgt, wird diese

['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'] 
=============== 

Answer 3

A erzeugen naive Implementierung:

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 

gibt:

(['%', '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']) 

Answer 4

Hier ist es. Beachten Sie, dass dieser Ansatz auf der einen Seite weniger sauber ist, aber Sie können die Permutationen von # len (matrix [0]) - 1 nur einmal berechnen und als Vorlage für die Ausgabe verwenden.

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']]