Идея состоит в том, что мы просто считаем от 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] не так эффективна, как могла бы (как с точки зрения памяти, так и процессора).Наличие указателя в начале и в конце и обход символов по одному до пересечения указателей будет лучше.
Есть некоторые условные оптимизации, которые можно выполнить для определенных значений 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.