Grid Permutation Algorithm - Fixed Row Order
-
30-05-2021 - |
Pregunta
Imagine a 3x3 grid:
[A, B, %]
[C, %, D]
[E, F, G]
The percentages %
stand for empty spaces/positions.
The rows can be moved like beads on a string, such that the permutations for the configurations for the first row could be any one of:
[A, B, %] or [A, %, B] or [%, A, B]
Similarly for the second row. The third row contains no empty slots and so cannot change.
I am trying to produce all possible grids, given the possible permutations of each row.
The output should produce the following grids:
[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]
I have tried a method of looking through each row and shifting the space left and right, then generating new grids off that and recursing. I keep all grids in a set and ensure I only produce positions which haven't already been examined to prevent infinite recursion.
However, my algorithm seems to be horrendously inefficient (~1s per permutation!!) and doesn't look very nice either. I was wondering if there was an eloquent way of doing this? In python in particular.
I have some vague ideas but I'm sure there is a way of doing this which is short and simple which I'm overlooking.
EDIT: 3x3 is just an example. Grid could be of any size and it's really the row combinations which matter. For example:
[A, %, C]
[D, E, %, G]
[H, I]
is also a valid grid.
EDIT 2: The letters must maintain their order. For example [A, %, B] != [B, %, A]
and [B, A, %]
isn't valid
Solución
First you have to get all desired permutations for each line. Then you calculate the cross product of all lines.
The permutations of a line can be simple calculated by having the letters [A,B,%] and varying the starting index:
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))
The cross product is easiest to achieve using 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)
This solution is optimal in memory and CPU requirements, because permutations are never recomputed.
Example output:
(['%', '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'])
Otros consejos
Define a function called cycle
>>> def cycle(lst):
while True:
lst=lst[1:]+lst[0:1] if '%' in lst else lst
yield lst
- Given an iterator, this will generate and return a cyclic left shift.
- Now you have to pass each of the rows in the grid to the cycle generator for the total iteration matching the length of the row
- Now use itertools.product to find all combinations of the generated row cyclic combinations.
- In case there is no empty slot, no cycle permutation is generated
The final result is as follows
>>> 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
For your Grid, this will generate
['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']
===============
A naive implementation:
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
gives:
(['%', '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'])
Here it is. Note that on one side this approach is less clean, but it allows you to compute the permutations of # len(matrix[0])-1 only once and use them as templates for the output.
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']]