Рекурсия для целочисленного разбиения с использованием чисел только один раз в Python медленная - PullRequest
Новая
       3

Рекурсия для целочисленного разбиения с использованием чисел только один раз в Python медленная

0 голосов
/ 28 марта 2020

Я пытаюсь рассчитать количество возможных комбинаций для суммирования, используя каждое число только один раз в Python 2.7.

Например, для 7 это будет 6 + 1, 5 + 2, 4 + 3, 4 + 2 + 1 -> 4 возможных комбинации

Мне удалось сделать это рекурсивным функция, которая делает математику правильно 

import time

counter_list = []

def start(n):
    tic=time.time()
    recursive_step(range(1, n), n)
    toc=time.time()
    print(toc - tic)
    return len(counter_list)

def recursive_step(numbers, target, summe=0):

    if summe == target:
        counter_list.append(1)
    if summe >= target:
        return

    for i in xrange(len(numbers)):
        n = numbers[i]
        remaining = numbers[i+1:]
        recursive_step(remaining, target, summe + n)

if __name__ == "__main__":
    print(start(7))

К сожалению, она становится очень медленной, когда цифры становятся больше. Ниже приведены некоторые цифры, которые я измерил на своей машине. 

~~~ 40 ~~~
time in seconds:        0.0789999961853
possible combinations:  1112
~~~ 50 ~~~
time in seconds:        0.40299987793
possible combinations:  3657
~~~ 60 ~~~
time in seconds:        1.51200008392
possible combinations:  10879
~~~ 70 ~~~
time in seconds:        5.41400003433
possible combinations:  29926
~~~ 80 ~~~
time in seconds:        18.388999939
possible combinations:  77311
~~~ 90 ~~~
time in seconds:        54.5920000076
possible combinations:  189585

Я изучил принципы динамического программирования c. Но я не мог заставить его работать над этой проблемой. Любой совет о том, как я могу улучшить этот сценарий, был бы очень признателен

1 Ответ

2 голосов
/ 28 марта 2020

Ссылка на эту последовательность: http://oeis.org/A000009

Вы можете представить себе проблему разбиения n на отдельные части как проблему замены монет с (одиночными) монетами значений 1 к п. (Или на единицу меньше этого, поскольку кажется, что вы запрещаете раздел n как единственное число n).

Решения можно рассчитывать, адаптируя стандартную динамику обмена монет c программное решение. 

def Q(n):
    A = [1] + [0] * n
    for i in range(1, n+1):
        for j in range(n, i-1, -1):
            A[j] += A[j-i]
    return A[n] - 1

print(Q(500))

Вы можете понять эту программу, заметив, что после k итераций внешнего l oop, A[i] содержит количество способов разбиения i с различными элементами от 1..k. И что число способов разбиения i с элементами, отличными от 1..k+1, представляет собой количество способов разбиения i с элементами, отличными от 1..k, плюс число способов разбиения i-k-1 с элементами из 1..k.

Это выполняется за O (n ^ 2) времени, но это быстро для небольших случаев (например: здесь 500 разделов, на моей машине 0,033 с).

...