亚里士多德数拼图解释

P：S：我从元线程了解到代码解释也可以在堆栈溢出时询问。亚里士多德数拼图解释

我想从this网站了解亚里士多德数字拼图的求解器。我明白了一点，直到当我们用高斯消元法排减，发现如下：

a = 76 - j - k - n - 2o - p - r - s 
b = j + n + o 
c = -38 + k + o + p + r + s 
d = j + k + o 
e = -38 + k + n + o + p + r 
f = 38 - j - k - n - o - p 
g = 38 - k - o - r 
h = -38 + n + o + p + r + s 
i = 38 - j - k - n - o - r 
l = 38 - p - s 
m = 38 - n - o - p 
q = 38 - r - s

代码的作者接着说：

现在，走规模7的每个排列从{1 ，2，...，19}，将其分配给独立变量，生成相关变量并根据约束进行测试，直到找到解决方案。

我真的不理解这个概念。特别是在this C文件，我不理解以下两个功能：

bool next_permutation(void) 
{ 
    for (int x = 6; x >= 0; x--) { 
     indices[x]++; 

     if (indices[x] == 19) { 
      if (!x) { 
       return false; 
      } 
      moveback(x, 18); 
      indices[x] = x; 
      continue; 
     } 

     swap(x, indices[x]); 
     break; 
    } 

    j = elem[0]; 
    k = elem[1]; 
    n = elem[2]; 
    o = elem[3]; 
    p = elem[4]; 
    r = elem[5]; 
    s = elem[6]; 

    return true; 
} 



// adds values to set 
// returns true if value successfully added; false otherwise 
bool add(int value) 
{ 
    if (value > 19 || value < 1) { 
     return false; 
    } 

    int bit = 1 << value; 
    if (set & bit) { 
     return false; 
    } 

    set |= bit; 
    return true; 
}

我将十分感谢，如果有人能帮助我理解这个求解。请注意，作者使用python脚本来减少行数。

来源

2017-09-16 Kalia Dona

第二个函数add，使用一个bitset来检查值是否已经在集合中。 'bit = 1 << value'将该值编码为一个二进制集合（位置1的1，位置2的2，位置3的3等）。如果值在集合中，set＆bit返回true，在这种情况下，该值不会被添加（即已经存在 - >返回false），否则将其添加到集合中（使用OR操作'| = ） – MrE

另一个函数只是将索引洗牌以获得一个集合，旋转7个值，当达到结尾时交换和推回值。 – MrE

我认为Gaussian elimination只是一种方法，通过将一个方程代入其他方程以消除不必要的变量来减少一组方程。例如，你可以拿第一的19点式的，把它变成了一个等式：

a = 38 - b - c

然后替代品进入其他18这将消除和减少你的方程18.然后重复，直到你不能再消除。

这是一个很好的问题，它给了我一个尝试SymPy包的借口。

下面是一些在SymPy中创建方程的代码，然后使用SymPy的solve函数来减少方程。

from sympy import symbols, solve 
from sympy.parsing.sympy_parser import parse_expr 

# Number of unknowns 
n = 19 

variable_names = [chr(c + 97) for c in range(19)] 

# Create SymPy variables 
variables = symbols(variable_names) 

print("\n{} unknowns:".format(len(variables))) 
print(variables) 

# These strings define the equations to be solved 
hexagon_rows = [ 
    'abc', 
    'defg', 
    'hijkl', 
    'mnop', 
    'qrs', 
    'cgl', 
    'bfkp', 
    'aejos', 
    'dinr', 
    'hmq', 
    'lps', 
    'gkor', 
    'cfjnq', 
    'beim', 
    'adh' 
] 

def make_expression(chars, rhs=0): 
    return parse_expr('+'.join(list(chars)) + '-' + str(rhs)) 

expressions = [] 
for chars in hexagon_rows: 
    expressions.append(make_expression(chars, 38)) 

print("\n{} equations to solve:".format(len(expressions))) 

for expr in expressions: 
    print("{} = 0".format(expr)) 

# Try to solve the equations 
# (They can't be solved but SymPy reduces them down) 
reduced_expressions = solve(expressions) 

print("\nReduced to {} equations:".format(len(reduced_expressions))) 
for var, expr in reduced_expressions.items(): 
    print("{} = {}".format(var, expr))

输出：

19 unknowns: 
[a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s] 

15 equations to solve: 
a + b + c - 38 = 0 
d + e + f + g - 38 = 0 
h + i + j + k + l - 38 = 0 
m + n + o + p - 38 = 0 
q + r + s - 38 = 0 
c + g + l - 38 = 0 
b + f + k + p - 38 = 0 
a + e + j + o + s - 38 = 0 
d + i + n + r - 38 = 0 
h + m + q - 38 = 0 
l + p + s - 38 = 0 
g + k + o + r - 38 = 0 
c + f + j + n + q - 38 = 0 
b + e + i + m - 38 = 0 
a + d + h - 38 = 0 

Reduced to 12 equations: 
j = b - n - o 
k = e - n - o - p - r + 38 
l = -p - s + 38 
i = -b - e + n + o + p 
c = e - n + s 
f = -b - e + n + o + r 
g = -e + n + p 
q = -r - s + 38 
m = -n - o - p + 38 
h = n + o + p + r + s - 38 
d = b + e - 2*n - o - p - r + 38 
a = -b - e + n - s + 38

希望有所帮助。至少第一部分！

来源

2017-09-16 20:45:12 Bill

亚里士多德数拼图解释

回答

相关问题