想象一个 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 秒!!)而且看起来也不是很好。我想知道是否有一种 Eloquent 方式来做到这一点?尤其是在 Python 中。
我有一些模糊的想法,但我确信有一种方法可以做到这一点,但我忽略了这一点。
编辑:3x3 只是一个例子。网格可以是任何大小,真正重要的是行组合。例如:
[A, %, C]
[D, E, %, G]
[H, I]
也是一个有效的网格。
编辑 2: 字母必须保持它们的顺序。例如 [A, %, B] != [B, %, A]
和 [B, A, %]
无效
最佳答案
首先,您必须为每一行获取所有需要的排列。然后计算所有线的叉积。
通过使用字母 [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'])
关于python - 网格置换算法 - 固定行顺序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10063717/