Я хочу создать лексикографический ряд чисел, чтобы для каждого числа сумма цифр была заданной константой. Это несколько похоже на «проблему суммы подмножества». Например, если я хочу сгенерировать 4-значные числа с суммой = 3, у меня есть ряд вроде:
[3 0 0 0]
[2 1 0 0]
[2 0 1 0]
[2 0 0 1]
[1 2 0 0] ... и так далее.
Мне удалось успешно сделать это на Python с помощью следующего кода:
import numpy as np
M = 4 # No. of digits
N = 3 # Target sum
a = np.zeros((1,M), int)
b = np.zeros((1,M), int)
a[0][0] = N
jj = 0
while a[jj][M-1] != N:
ii = M-2
while a[jj][ii] == 0:
ii = ii-1
kk = ii
if kk > 0:
b[0][0:kk-1] = a[jj][0:kk-1]
b[0][kk] = a[jj][kk]-1
b[0][kk+1] = N - sum(b[0][0:kk+1])
b[0][kk+2:] = 0
a = np.concatenate((a,b), axis=0)
jj += 1
for ii in range(0,len(a)):
print a[ii]
print len(a)
Я не думаю, что это очень эффективный способ (поскольку я новичок в Python). Он отлично работает для малых значений M и N (<10), но очень медленно при более высоких значениях. Я хочу использовать его для M ~ 100 и N ~ 6. Как я могу сделать свой код более эффективным или есть лучший способ его кодирования?