Если вы не заметили, endl
походит на нажатие клавиши ENTER, когда "\n"
походит на нажатие ENTER KEY + SPACE BAR.
Очень эффективный алгоритм, адаптированный из книги Йорга Арндта «Вычислительные вопросы»
(Глава 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
То же самое с массивами numpy (x = np.zeros((n,), dtype=int)
) дает хуже [1116 ] результаты - но, возможно, потому что я не знаю, как их правильно использовать
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
Мои рекомендации:
yield
, а не цикл, который объединяет глобальную переменную на каждой итерации. Обратите внимание, что никакой конкретный порядок не подразумевается.
У меня есть лучшее решение с использованием 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, этот код требует времени, чтобы пройти все комбинации, я думаю, потребуются дни, чтобы вычислить результаты.