python - 亚里士多德数谜解说

Question

P:S:我从this中学到了也可以在 Stack Overflow 上询问代码解释的元线程。

我正在尝试从 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

然后代码的作者继续:

Now, take each permutation of size 7 from {1, 2, ..., 19}, assign it to the independent variables, generate the dependent ones and test against the constraints until finding solutions.

这个概念我是真的不懂。特别是关于 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 脚本进行行减少。

Answer 1

我认为Gaussian elimination只是一种通过将一个方程代入其他方程以消除不必要的变量来减少一组方程的方法。例如，您可以将 19 个方程式中的第一个方程式转化为 a 的方程式:

a = 38 - b - c

然后将其代入其他 18。这将消去 a 并将你的方程式减少到 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

希望对您有所帮助。至少第一部分!