我试图找到长度为 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 新手? 任何帮助将不胜感激
谢谢
最佳答案
我们的想法是,我们简单地从 0
计数到 10**k
,并将这些“整数”中的每一个视为回文序列。我们在必要时留下 0
。因此,对于 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
变大时,这会减慢很多):
这是一个令人尴尬的并行问题,请考虑多线程/多处理。
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-3.x - python : finding all pallindromic sequences of length k that sum to n,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/53524411/