Генерация лексикографических рядов эффективно в Python

Question

Я хочу сгенерировать лексикографический ряд чисел так, чтобы для каждого числа сумма цифр была заданной константой.Это несколько похоже на «проблему подмножества суммы»Например, если я хочу сгенерировать 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. Как я могу сделать свой код более эффективным или есть лучший способ его кодирования? </p>

Answer 1

Очень эффективный алгоритм, адаптированный из книги Йорга Арндта "Вычислительные вопросы"
(Глава 7.2 Co-lexicographic order for compositions into exactly k parts)

n = 4
k = 3

x = [0] * n
x[0] = k

while True:
    print(x)
    v = x[-1]
    if (k==v ):
        break
    x[-1] = 0
    j = -2
    while (0==x[j]):
        j -= 1
    x[j] -= 1
    x[j+1] = 1 + v

[3, 0, 0, 0]
[2, 1, 0, 0]
[2, 0, 1, 0]
[2, 0, 0, 1]
[1, 2, 0, 0]
[1, 1, 1, 0]
[1, 1, 0, 1]
[1, 0, 2, 0]
[1, 0, 1, 1]
[1, 0, 0, 2]
[0, 3, 0, 0]
[0, 2, 1, 0]
[0, 2, 0, 1]
[0, 1, 2, 0]
[0, 1, 1, 1]
[0, 1, 0, 2]
[0, 0, 3, 0]
[0, 0, 2, 1]
[0, 0, 1, 2]
[0, 0, 0, 3]

Количество композиций и время в секундах для простого Python (возможно, массивы с большими числами быстрее)для n = 100 и k = 2,3,4,5 (2,8 ГГц Cel-1840)

2  5050 0.040000200271606445
3  171700 0.9900014400482178
4  4421275 20.02204465866089
5  91962520 372.03577995300293
I expect time  2 hours for 100/6 generation

То же самое с массивами numy (x = np.zeros((n,), dtype=int)) дает хуже результаты -но, возможно, из-за того, что я не знаю, как их правильно использовать

2  5050 0.07999992370605469
3  171700 2.390003204345703
4  4421275 54.74532389640808

Собственный код (это Delphi, компиляторы C / C ++ могут оптимизировать лучше) генерирует 100/6 за 21 секунду

3  171700  0.012
4  4421275  0.125
5  91962520  1.544
6  1609344100 20.748

Невозможно заснуть, пока не будут выполнены все измерения:)

MSVS VC ++: 18 секунд !(Оптимизация O2)

5  91962520 1.466
6  1609344100 18.283

Итак, 100 миллионов вариантов в секунду.Много времени тратится на проверку пустых ячеек (потому что коэффициент заполнения мал).Скорость, описанная Арндтом, достигается при более высоких коэффициентах k / n и составляет около 300-500 миллионов вариантов в секунду:

n=25, k=15 25140840660 60.981  400 millions per second

Answer 2

Мои рекомендации:

1. Перепишите его как генератор, используя yield, а не цикл, который объединяет глобальную переменную на каждой итерации.
2. Сохраняйте промежуточную сумму вместовычисление суммы некоторого подмножества представления массива числа.
3. Работа с одним экземпляром представления рабочего числа вместо объединения его копии с временной переменной на каждой итерации.

Обратите внимание, что особый порядок не подразумевается.

Answer 3

У меня есть лучшее решение с использованием itertools следующим образом,

from itertools import product
n = 4 #number of elements
s = 3 #sum of elements
r = []
for x in range(n):
    r.append(x)
result = [p for p in product(r, repeat=n) if sum(p) == s]
print(len(result))
print(result)

Я говорю, что это лучше, потому что это заняло 0,1 секунды в моей системе, в то время как ваш код с numpy занял 0,2 секунды.

Но поскольку n = 100 и s = 6, этот код требует времени для прохождения всех комбинаций, я думаю, что для вычисления результатов понадобятся дни.