Python：找到所有长度为 k 且总和为 n 的回文序列

Question

我试图找到所有长度为 k 且总和为 n 的回文序列。我有一个具体的例子（k=6）：

def brute(n):
J=[]
for a in range(1,n):
    for b in range(1,n):
        for c in range(1,n):
            if (a+b+c)*2==n:
                J.append((a,b,c,c,b,a))
return(J)

输出结果如下：

[(1, 1, 6, 6, 1, 1),
 (1, 2, 5, 5, 2, 1),
 (1, 3, 4, 4, 3, 1),
 (1, 4, 3, 3, 4, 1),
 (1, 5, 2, 2, 5, 1),
 (1, 6, 1, 1, 6, 1),
 (2, 1, 5, 5, 1, 2),
 (2, 2, 4, 4, 2, 2),
 (2, 3, 3, 3, 3, 2),
 (2, 4, 2, 2, 4, 2),
 (2, 5, 1, 1, 5, 2),
 (3, 1, 4, 4, 1, 3),
 (3, 2, 3, 3, 2, 3),
 (3, 3, 2, 2, 3, 3),
 (3, 4, 1, 1, 4, 3),
 (4, 1, 3, 3, 1, 4),
 (4, 2, 2, 2, 2, 4),
 (4, 3, 1, 1, 3, 4),
 (5, 1, 2, 2, 1, 5),
 (5, 2, 1, 1, 2, 5),
 (6, 1, 1, 1, 1, 6)]

问题是我不知道如何将其推广到 n 和 k 的任何值。我听说字典会有帮助。我有没有提到我是 python 的新手？ 任何帮助将不胜感激

谢谢

Answer 1

的想法是，我们简单地从0数到10**k，并将每个"integers"视为一个回文序列。我们在必要时用 0 留下了 pad。因此，对于 k==6、0 -> [0, 0, 0, 0, 0, 0]、1 -> [0, 0, 0, 0, 0, 1] 等。这枚举了所有可能的组合。如果是回文，我们还会检查它加起来是否等于 n.

下面是一些代码，（应该）为任意 n 和 k 给出正确的结果，但效率不高。我会把优化留给你（如果有必要的话），并给出一些关于如何做的提示。

代码如下：

def find_all_palindromic_sequences(n, k):
    result = []
    for i in range(10**k):
        paly = gen_palindrome(i, k, n)
        if paly is not None:
            result.append(paly)
    return result

def gen_palindrome(i, k, n):
    i_padded = str(i).zfill(k)
    i_digits = [int(digit) for digit in i_padded]
    if i_digits == i_digits[::-1] and sum(i_digits) == n:
        return i_digits

为了测试它，我们可以这样做：

for paly in find_all_palindromic_sequences(n=16, k=6):
    print(paly)

这输出：

[0, 0, 8, 8, 0, 0]
[0, 1, 7, 7, 1, 0]
[0, 2, 6, 6, 2, 0]
[0, 3, 5, 5, 3, 0]
[0, 4, 4, 4, 4, 0]
[0, 5, 3, 3, 5, 0]
[0, 6, 2, 2, 6, 0]
[0, 7, 1, 1, 7, 0]
[0, 8, 0, 0, 8, 0]
[1, 0, 7, 7, 0, 1]
[1, 1, 6, 6, 1, 1]
[1, 2, 5, 5, 2, 1]
[1, 3, 4, 4, 3, 1]
[1, 4, 3, 3, 4, 1]
[1, 5, 2, 2, 5, 1]
[1, 6, 1, 1, 6, 1]
[1, 7, 0, 0, 7, 1]
[2, 0, 6, 6, 0, 2]
[2, 1, 5, 5, 1, 2]
[2, 2, 4, 4, 2, 2]
[2, 3, 3, 3, 3, 2]
[2, 4, 2, 2, 4, 2]
[2, 5, 1, 1, 5, 2]
[2, 6, 0, 0, 6, 2]
[3, 0, 5, 5, 0, 3]
[3, 1, 4, 4, 1, 3]
[3, 2, 3, 3, 2, 3]
[3, 3, 2, 2, 3, 3]
[3, 4, 1, 1, 4, 3]
[3, 5, 0, 0, 5, 3]
[4, 0, 4, 4, 0, 4]
[4, 1, 3, 3, 1, 4]
[4, 2, 2, 2, 2, 4]
[4, 3, 1, 1, 3, 4]
[4, 4, 0, 0, 4, 4]
[5, 0, 3, 3, 0, 5]
[5, 1, 2, 2, 1, 5]
[5, 2, 1, 1, 2, 5]
[5, 3, 0, 0, 3, 5]
[6, 0, 2, 2, 0, 6]
[6, 1, 1, 1, 1, 6]
[6, 2, 0, 0, 2, 6]
[7, 0, 1, 1, 0, 7]
[7, 1, 0, 0, 1, 7]
[8, 0, 0, 0, 0, 8]

这看起来与您的结果相似，加上包含 0.

的结果

让它变得更快的想法（随着 `k` 变大，这会减慢很多）：

这是一个尴尬的并行问题，考虑multithreading/multiprocessing。
i_digits == i_digits[::-1] 的回文检查没有达到应有的效率（在内存和 CPU 方面）。开始和结束有一个指针，一个一个地遍历字符直到指针交叉会更好。
您可以对 n 的某些值进行一些条件优化。例如，如果 n 是 0，无论 k 有多大，唯一的回文将是 [0, 0, 0, ..., 0, 0]。再举一个例子，如果 n 是 8，我们显然不必生成任何包含 9 的排列。或者，如果 n 是 20，而 k 是 6，那么我们的排列中不能有 3 9。假设 n 相当小，推广这种模式将获得巨大回报。实际上，它也以另一种方式起作用。如果 n 很大，那么每个排列中的 0 和 1 的数量是有限制的。
可能有比测试每个整数更好的生成回文的方法。例如，如果我们知道整数 X 是回文序列，那么 X+1 就不是。很容易证明这一点：第一个和最后一个数字不能匹配 X+1 因为我们知道它们必须与 X 匹配。你可能能够证明 X+2 和 X+3 也不能是回文，等等。如果你能概括你必须测试的地方一个新的回文，这将是关键。数论学家可以在这方面提供更多帮助。

HTH.

Python：找到所有长度为 k 且总和为 n 的回文序列

Python: finding all pallindromic sequences of length k that sum to n

combinatorics

palindrome

python-3.x

让它变得更快的想法（随着 `k` 变大，这会减慢很多）：

Python：找到所有长度为 k 且总和为 n 的回文序列

Python: finding all pallindromic sequences of length k that sum to n

combinatorics

palindrome

python-3.x

让它变得更快的想法（随着 k 变大，这会减慢很多）：

让它变得更快的想法（随着 `k` 变大，这会减慢很多）：