파이썬 파티셔닝 기능 최적화가 필요합니다

project euler exercise (#78)에 대해 연구하면서 번호 분할을 위해 멱급수를 만들 수 있음을 알게되었습니다. 이 시리즈에서 계수라는 용어를 확장하여 사용하면 특정 숫자를 분할하는 방법의 수를 얻을 수 있습니다. 거기에서파이썬 파티셔닝 기능 최적화가 필요합니다

, 나는이 작은 기능을 만들었습니다

## I've included two arguments, 'lim' for the number you wish to partition and 'ways' a list of numbers you can use to partition that number 'lim'. ## 

def stack(lim,ways): 

    ## create a list of length of 'lim' filled with 0's. ## 
    posi = [0] * (lim + 1) 

    ## allow the posi[0] to be 1 ## 
    posi[0] = 1 

    ## double loop -- with the amount of 'ways'. ## 
    for i in ways: 
     for k in range(i, lim + 1): 
      posi[k] += posi[k - i] 

    ## return the 'lim' numbered from the list which will be the 'lim' coefficient. ## 
    return posi[lim] 

>>> stack(100,[1,5,10,25,50,100]) 
>>> 293 
>>> stack(100,range(1,100)) 
>>> 190569291 
>>> stack(10000,range(1,10000)) 
>>> 36167251325636293988820471890953695495016030339315650422081868605887952568754066420592310556052906916435143L

이이 운동을하지로, 상대적으로 작은 파티션에서 잘 작동하지만. 재귀 또는 더 빠른 알고리즘을 사용하여이를 가속화 할 수있는 방법이 있습니까? 오각형의 숫자를 사용하는 것이 파티션을 돕는 방법이기도 한 곳을 읽었습니다. 그것이 1000000

업데이트로 나누어 경우

는 지금은이 문제에 실제 수를 반환하지만, 확인 할 필요가 없습니다 : 나는 pentagonal number theorem를 사용하여 끝났다. 나는 Craig Citro가 게시 한 Hardy-Ramanujan asymptotic 공식을 사용하려고 시도 할 것입니다.

출처

2012-07-30 tijko

해당 함수에 대한 입력 예제를 제공 할 수 있으며 출력 될 수 있습니까? 빠른 케이스와 '너무 긴 케이스'둘 다요? –

@JoshSmeaton 확실한 것. – tijko

나는 최근에이 사실을 개인적으로 확인하지는 않았지만 "가장 빠른 파티션 알고리즘"이라는 제목은 Sage에서 구현 된 것으로 보입니다. the docs에 언급 된 내용을 보거나 더 나은 내용을 보려면 the source code으로 건너 뜁니다. 이 숫자를 계산하는 방법에 대한 토론을 원하면이 구현을위한 original thread이 매우 흥미 롭습니다. source file for the implementation itself은 코드에 대한 유용한 주석으로 시작합니다.

출처

2012-07-30 05:11:57

그 몇 가지 멋진 링크입니다, 그들은 매우 도움이되는 자원 감사 것입니다. 나는 오해 했음에 틀림 없다, 나는 Hardy-Ramanujan Asymptotic 공식이이 목적을 위해 정확하거나 심지어 정확하다고 생각하지 않았다. 근사치 만 줄 수 있다고 생각했습니다. 나는 [this] (http://en.wikipedia.org/wiki/Partition_%28number_theory%29#Partition_function_formulas)를 사용하여 내 자신의 함수를 작성할 수 있는지 알아볼 것입니다. – tijko

파이썬 파티셔닝 기능 최적화가 필요합니다

답변

관련 문제