Olb*_*a12 7 python matrix combinatorics constraint-programming python-3.x
假设我有一个包含 16 个数字的列表。有了这 16 个数字，我可以创建不同的 4x4 矩阵。我想找到所有 4x4 矩阵，其中列表中的每个元素都使用一次，并且每行和每列的总和等于 264。
首先，我找到列表中元素的所有组合，总和为 264
numbers = [11, 16, 18, 19, 61, 66, 68, 69, 81, 86, 88, 89, 91, 96, 98, 99]
candidates = []
result = [x for x in itertools.combinations(numbers, 4) if sum(x) == 264]
result成为一个列表，其中每个元素都是一个包含 4 个元素的列表，其中 4 个元素的总和 = 264。我认为这些是我的行。然后我想对我的行进行所有排列，因为加法是可交换的。
for i in range(0, len(result)):
candidates.append(list(itertools.permutations(result[i])))
现在给出总和为 264 的所有可能行。我想选择 4 行的所有组合，以便每列的总和为 264。
test = []
for i in range(0, len(candidates)):
test = test + candidates[i]
result2 = [x for x in itertools.combinations(test, 4) if list(map(add, x[0], list(map(add, x[1], list( map(add, x[2], x[3])))))) == [264, 264, 264, 264]]
有没有更快/更好的方法？最后一部分，查找 4 行的所有组合，需要大量时间和计算机能力。
这是一种约束满足问题；有 16 个变量，每个变量都具有相同的域，八个关于它们和的约束，以及一个约束，它们都应该具有与域不同的值。
可能有大量的解决方案，因此任何生成更大的候选集然后检查哪些候选真正是解决方案的算法在很大程度上可能是低效的，因为真正的解决方案可能是您的候选解决方案的一小部分. 一个回溯搜索通常是更好的，因为它允许部分考生时，他们违反任何约束被拒绝，潜在地消除了很多完整的候选人，而无需生成它们都摆在首位。
您可以使用现有的约束求解器，例如python-constraint 库，而不是编写自己的回溯搜索算法。下面是一个例子：
numbers = [11, 16, 18, 19, 61, 66, 68, 69, 81, 86, 88, 89, 91, 96, 98, 99]
target = 264
from constraint import *
problem = Problem()
problem.addVariables(range(16), numbers)
for i in range(4):
# column i
v = [ i + 4*j for j in range(4) ]
problem.addConstraint(ExactSumConstraint(target), v)
# row i
v = [ 4*i + j for j in range(4) ]
problem.addConstraint(ExactSumConstraint(target), v)
problem.addConstraint(AllDifferentConstraint())
例子：
>>> problem.getSolution()
{0: 99, 1: 88, 2: 66, 3: 11, 4: 16, 5: 61, 6: 89, 7: 98, 8: 81, 9: 96, 10: 18, 11: 69, 12: 68, 13: 19, 14: 91, 15: 86}
>>> import itertools
>>> for s in itertools.islice(problem.getSolutionIter(), 10):
... print(s)
...
{0: 99, 1: 68, 2: 81, 3: 16, 4: 66, 5: 91, 6: 18, 7: 89, 8: 88, 9: 19, 10: 96, 11: 61, 12: 11, 13: 86, 14: 69, 15: 98}
{0: 99, 1: 68, 2: 81, 3: 16, 4: 66, 5: 91, 6: 18, 7: 89, 8: 11, 9: 86, 10: 69, 11: 98, 12: 88, 13: 19, 14: 96, 15: 61}
{0: 99, 1: 68, 2: 81, 3: 16, 4: 18, 5: 89, 6: 66, 7: 91, 8: 86, 9: 11, 10: 98, 11: 69, 12: 61, 13: 96, 14: 19, 15: 88}
{0: 99, 1: 68, 2: 81, 3: 16, 4: 18, 5: 89, 6: 66, 7: 91, 8: 61, 9: 96, 10: 19, 11: 88, 12: 86, 13: 11, 14: 98, 15: 69}
{0: 99, 1: 68, 2: 81, 3: 16, 4: 11, 5: 86, 6: 69, 7: 98, 8: 66, 9: 91, 10: 18, 11: 89, 12: 88, 13: 19, 14: 96, 15: 61}
{0: 99, 1: 68, 2: 81, 3: 16, 4: 11, 5: 86, 6: 69, 7: 98, 8: 88, 9: 19, 10: 96, 11: 61, 12: 66, 13: 91, 14: 18, 15: 89}
{0: 99, 1: 68, 2: 81, 3: 16, 4: 61, 5: 96, 6: 19, 7: 88, 8: 18, 9: 89, 10: 66, 11: 91, 12: 86, 13: 11, 14: 98, 15: 69}
{0: 99, 1: 68, 2: 81, 3: 16, 4: 61, 5: 96, 6: 19, 7: 88, 8: 86, 9: 11, 10: 98, 11: 69, 12: 18, 13: 89, 14: 66, 15: 91}
{0: 99, 1: 68, 2: 81, 3: 16, 4: 88, 5: 19, 6: 96, 7: 61, 8: 11, 9: 86, 10: 69, 11: 98, 12: 66, 13: 91, 14: 18, 15: 89}
{0: 99, 1: 68, 2: 81, 3: 16, 4: 88, 5: 19, 6: 96, 7: 61, 8: 66, 9: 91, 10: 18, 11: 89, 12: 11, 13: 86, 14: 69, 15: 98}
这是前十个解决方案。该problem.getSolutions()方法返回一个包含所有这些的列表，但这需要相当多的时间来运行（在我的机器上大约需要 2 分钟），因为要找到 6,912 个。
一个问题是每个解都有许多对称的对应物；您可以排列行，排列列，并进行转置。可以通过添加更多约束来消除对称性，这样您就可以从每个对称类中获得一个解决方案。这使得搜索更可行：
# permute rows/cols so that lowest element is in top-left corner
m = min(numbers)
problem.addConstraint(InSetConstraint([m]), [0])
from operator import lt as less_than
for i in range(3):
# permute columns so first row is in order
problem.addConstraint(less_than, [i, i+1])
# permute rows so first column is in order
problem.addConstraint(less_than, [4*i, 4*i + 4])
# break transpose symmetry by requiring grid[0,1] < grid[1,0]
problem.addConstraint(less_than, [1, 4])
这打破了所有的对称性，所以现在它在大约 0.2 秒内返回 6,912 / (4! * 4! * 2) = 6 个解。