网格排列算法 - 固定行顺序

Question

想象一个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秒！！），而且看起来也不太好。我想知道是否有一种优雅的方法来做到这一点？特别是在Python中。

我有一些模糊的想法，但我肯定会忽略一种简短而简单的方法来完成这个任务。

编辑：3x3只是一个示例。网格可以是任何大小，实际上是行组合很重要。例如：

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

也是有效的网格。

编辑2：字母必须保持它们的顺序。例如[A，％，B]！= [B，％，A]和[B，A，％]无效

- Pete Hamilton

---

这需要适用于任意大小的网格吗？ - Vaughn Cato

["A","B","%] 被认为与 ["B","A","%"] 不相等吗？ - luke14free

网格的大小将是任意的，每一行的长度也可能不同。3x3只是一个例子。 - Pete Hamilton

事实上，["A","B","%] 被认为与 ["B","A","%"] 不相等。 - Pete Hamilton

Answer 1

首先，您需要获取每行所需的所有排列。然后计算所有行的叉积。

可以通过拥有字母[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)

这个解决方案在内存和CPU要求上都是最优的，因为排列不会被重新计算。

示例输出：

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

- j13r

---

我可能没有正确理解你的意思，但仅仅改变起始索引并不能得到所有的排列组合。尽管它可以得到所需的解决方案。 - NeXuS

你能在生成器内使用带参数的return语句吗？ - Abhijit

@NeXuS：请看原帖“行可以像串珠一样移动”；我会进行调整以使其更加清晰。 - j13r

A和B应该始终按照相同的顺序。这个算法会遵守吗？您之前写的是“['B', '%', 'A']”，这会改变顺序吗？ - Pete Hamilton

这看起来很有前途，我会在我的实现中试用它，并看看它与其他解决方案相比如何。 - Pete Hamilton

Answer 2

定义一个名为 cycle 的函数。

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

- Abhijit

Answer 3

一个天真的实现：

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

- mshsayem

---

追溯（Traceback）最近的一次调用： File "sandbox.py", line 2, in <module> ['C', '%', 'D'] TypeError: 列表索引必须是整数，而不是元组。 - luke14free

忘记在 g 内部放置逗号 :p - mshsayem

Answer 4

就是这样。需要注意的是，这种方法在某些方面不够简洁，但它允许你只计算一次 # 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']]

- luke14free

---

如果网格的大小更大，比如100*100怎么办？我认为OP只是举了一个3X3网格作为例子。 - Abhijit

我通常发布文章只是为了让人们理解推理过程。然后，如果他们能够实现自己真正需要的东西（并且如果他们能够理解它），那将会更好。不管怎样，这很简单。 - luke14free

这个输出是准确的，也是我需要的，但我不确定它是否可扩展。我将编辑问题，以明确3x3只是一个例子。 - Pete Hamilton

最后... 哈哈! 它被缩放了。 :P - luke14free

@PeterHamilton，你能否使用大矩阵（>15x15）对此算法进行基准测试？ - luke14free