파이썬 3에서 반복 프로세스를 큰 크기로 확장하는 방법

Question

동전을 n 번 던지면 (n = 10), 2^10 = 1024 개의 가능한 결과가 있습니다. I는 N = 10 개의 모든 가능한 결과를 얻기 위해

lst = [list(i) for i in itertools.product([0, 1], repeat=n)] 

사용하고 난 경화의 동일한면의 최대 연속 시퀀스로서 정의되는 기 (m)의 숫자를 찾을. 예를 들어, HHHTTHTTHT,이 결과에 대한 그룹의 수는 (HHH) (TT) (H) (TT) (H) (T) 인 6입니다. 나는 투기 된 동전의 각각의 대응하는 조합에 대한 그룹 (m)의 수를 알아 내기 위해

group=[len([len(list(grp)) for k, grp in groupby(x)]) for x in lst] 

을 사용했다. 마지막으로, 그러나 이러한 가능한 조합 그룹의 수가 6 (m)보다 큰 경우의 수

Group6=len(list(filter(lambda x:x>m,group))) 

를 얻을 때 토스 증가 수, 예를 들면, (N = 200, m = 110) 또는 (n = 500, m = 260). 파이썬에서 위와 같은 코드를 사용했지만 시간이 많이 걸렸습니다. 파이썬의 메모리 크기를 초과했다고 생각합니다. 누군가가 n과 m이 상당히 큰 경우이 문제를 해결하는 방법을 찾아 내도록 도와 줄 수 있습니까? 가능한 모든 토스를 통해 감사

Answer 1

순회 확실히 큰 N 작동하지 않을 (여기 N는 것 같아요 (20)에서 이미 큰). 어떤 조합은 combinatorics을 사용하여 효율적으로 계산할 수 있습니다.

먼저 간단한 예를 들어 봅시다. 네 개의 토스를위한 최소 두 개의 그룹 : 두 개의 더 많은 그룹을 생성하는 토스 수를 계산하려는 경우.

두 그룹 :

1112 
1122 
1222 

세 그룹 :

1123 
1223 
1233 

네 그룹 :

1234 

몇 가지 가능성 (우리는 1, 2 같은 그룹 등 수)있다

우리는 그룹 G1의 값을 알고 있습니다. G2에 대한 것이고 G2에 대한 것이 G3과 다른 것입니다. 이것은 우리가 첫 번째 그룹을 을 결정하는 경우, 우리는 모든 그룹에 대한 값을 deterimed 것을 의미 두 값 (머리 및 꼬리)가

G1 != G2 != G3 != ... != Gn 

이후 : 그래서 주장한다. G1이 머리이면 모든 짝수 그룹은 꼬리이며 모든 홀수 그룹은 머리입니다.

위의 모든 조합에 대해 정확히 두 개의 구성이 있음을 의미합니다. 즉, n=4,m=1의 경우에는 2 × 7 = 14 개의 구성이 있습니다. (질문에 프로그램을 실행하면 얻을 수있는 것과 정확히 일치합니다.)

지금 우리는 여전히 얼굴을 가지고있는 유일한 문제는 우리가이 슈퍼 구성을 계산하려고하는 방법 입니다.

당신은 1와 그룹의 증가와 0와 같은 그룹을 표기하기 : 우리는 내가 표기를 업그레이드 라고 부르는 도입하여이 작업을 수행 할 수 있습니다.

이제 1223은 0101이됩니다. 두 번째 및 네 번째 색인에서 그룹을 업그레이드합니다. 1234은 0111입니다. 어떻게 도움이됩니까? 사실 k 그룹의 경우 개를 조합하면 k-1 번으로의 조합 수를 개로 계산하면됩니다. 이것은 조합 수 (k-1 nCr n-1)를 의미합니다. n 문자열의 길이 (또는 총 토스 수)는 k 그룹 수 *입니다. 이제 (k-1 nCr n)은 (n-1)!/((k-1)! * (n-k)!)로 정의됩니다. ! 계승. 나는 nCrhere에서 계산하는 방법 빌린 :

def ncr(n, r): 
    r = min(r, n-r) 
    if r == 0: return 1 
    return reduce(op.mul,range(n-r+1,n+1))//reduce(op.mul,range(1,r+1)) 

을 줄이기으로 가져올 functools에서 연산 로

수입 연산자를 그리고 이제 마지막 단계는 모든 k에 대한 조합 (2 배)의 수를 계산 아니라 m부터 n까지입니다. 그래서 :

def group_num(n,m): 
    total = 0 
    for i in range(m+1,n+1): 
     total += ncr(n-1,i-1) 
    return 2*total 

또는 한 줄에 퍼팅 :

def group_num(n,m): 
    return 2*sum(ncr(n-1,i-1) for i in range(m+1,n+1)) 

을 이제 우리는 우리의 코드를 테스트 할 수 있습니다

(첫 번째 두) 예상 번호입니다

>>> group_num(4,1) 
14 
>>> group_num(10,6) 
260 
>>> group_num(200,110) 
125409844583698900384745448848066934911164089598228258053888 
>>> group_num(500,260) 
606609270097725645141493459934317664675833205307408583743573981944035656294544972476175251556943050783856517254296239386495518290119646417132819099088 

. 보시다시피 총량이 엄청나게 늘어남에 따라이 방법으로 한 번에 하나씩 토스 수를 계산하는 가장 빠른 알고리즘조차도 쉽게 결과를 얻을 수 있습니다 (결과는 1 초 이내에 계산되었습니다).

ncr 함수는 O (n)으로 계산할 수 있지만 (예 : 계승에 대한 메모를 사용하여 향상시킬 수도 있습니다). 따라서 group_num 함수는 O ((n-m) × n)에 계산됩니다 (메모 최적화가 없음). 따라서 지수 적 행동을 완전히 상쇄시킨다.