Grid Permutation Algorithm - Fixed Row Order

Question

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

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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