给定一个数字列表，找到所有矩阵，使每一列和每一行的总和为264 [英] Given a list of numbers, find all matrices such that each column and row sum up to 264
问题描述
假设我有16个数字的清单.使用这16个数字，我可以创建不同的4x4矩阵.我想找到所有4x4矩阵，其中列表中的每个元素都使用一次，并且每行和每个列的总和等于264.
Let's say I have a list of 16 numbers. With these 16 numbers I can create different 4x4 matrices. I'd like to find all 4x4 matrices where each element in the list is used once, and where the sum of each row and each colum is equal to 264.
首先，我发现列表中所有元素的总和为264
First I find all combination of elements within the list that sum up to 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.我将它们视为我的行.然后，我想对行进行所有排列，因为加法是可交换的.
result becomes a list where each element is a list with 4 elements, where the sum of the 4 elements = 264. I think of these as my rows. Then I'd like to take all permutations of my rows, since addition is commutative.
for i in range(0, len(result)):
candidates.append(list(itertools.permutations(result[i])))
现在给定我所有可能的行，总和为264.我想选择4行的所有组合，以使每一列的总和为264.
Now given all my possible rows where the sum is 264. I'd like to choose all combinations of 4 rows, such that every column's sum is 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行的所有组合，需要大量时间和计算机功能.
Is there a faster/better way? The last part, finding all combinations of 4 rows, takes a lot of time and computer power.
推荐答案
这是一种约束满意度问题;共有16个变量，每个变量都具有相同的域，关于它们的和有8个约束，并且一个约束要求它们都应具有与该域不同的值.
This is a kind of constraint satisfaction problem; there are sixteen variables each with the same domain, eight constraints about their sums, and one constraint that they should all have different values from the domain.
潜在的解决方案数量很多，因此任何算法生成更大的候选集，然后检查哪些候选对象是真正的解决方案，在很大程度上可能会导致效率低下，因为真正的解决方案所占的比例可能非常低您的候选人. 回溯搜索通常更好，因为它允许部分候选人在违反任何约束条件时被拒绝. ，从而可能消除了许多完整的候选人，而不必首先生成所有候选人.
There are potentially a large number of solutions, so any algorithm which generates a bigger set of candidates and then checks which candidates really are solutions is probably inefficient by a large factor, since the true solutions are likely to be a very low proportion of your candidates. A backtracking search is generally better, since it allows partial candidates to be rejected when they violate any constraint, potentially eliminating many complete candidates without having to generate them all in the first place.
您可以使用现有的约束求解器，例如 python-constraint，而不是编写自己的回溯搜索算法.库.这是一个示例:
Rather than write your own backtracking search algorithm, you can use an existing constraint-solver such as the python-constraint library. Here's an example:
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个.
That's the first ten solutions. The problem.getSolutions() method returns a list containing all of them, but this takes quite a bit of time to run (about 2 minutes on my machine) because there are 6,912 of them to find.
一个问题是，每个解决方案都有许多对称的对应方案；您可以置换行，置换列并进行转置.可以通过添加更多约束来消除对称性，这样您就可以从每个对称性类中获得一个解决方案.这使搜索更加可行:
One issue is that each solution has many symmetrical counterparts; you can permute the rows, and permute the columns, and take the transpose. It is possible to eliminate symmetries by adding more constraints, so that you just get one solution from each symmetry class. This makes the search more feasible:
# 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个解.
This breaks all symmetries, so now it returns 6,912 / (4! * 4! * 2) = 6 solutions in about 0.2 seconds.
这篇关于给定一个数字列表，找到所有矩阵，使每一列和每一行的总和为264的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
