특정 숫자의 합계 수를 반환하는 함수

Question

목록 번호를 추가하여 특정 숫자에 도달하는 방법의 수를 반환하는 함수를 작성해야합니다. 예를 들어 내가 쓴

print(p([3,5,8,9,11,12,20], 20)) 
should return:5 

코드는 다음과 같습니다

def pow(lis): 
    power = [[]] 
    for lst in lis: 
     for po in power: 
      power = power + [list(po)+[lst]] 
    return power 

def p(lst, n): 
    counter1 = 0 
    counter2 = 0 
    power_list = pow(lst) 
    print(power_list) 
    for p in power_list: 
     for j in p: 
      counter1 += j 
     if counter1 == n: 
      counter2 += 1 
      counter1 == 0 
     else: 
      counter1 == 0 
    return counter2 

pow()는 수 n에 도달 할 수있는 방법의 수를 반환해야 목록의 부분 집합의 모든 및 p을 반환하는 함수입니다. 나는 계속 0의 출력을 얻었고 나는 왜 그런지 이해하지 못한다. 나는 당신의 의견을 듣고 싶습니다. 미리 감사드립니다.

Answer 1

추가를 최소화하는 카운터가있는 원 패스 솔루션입니다.

def one_pass_sum(L,target): 
    sums = [0] 
    cnt = 0 
    for x in L: 
     for y in sums[:]: 
      z = x+y 
      if z <= target : 
       sums.append(z) 
       if z == target : cnt += 1 
    return cnt 

이 방법 n=len(L) 경우, 모든 금액을 계산하여 n/2 * 2^n에 대한보다 2^n 추가합니다.

는

편집 :

보다 효율적인 솔루션, 그건 그냥 방법을 계산합니다. 아이디어는 을 만드는 k 방법이있는 경우에, x가 생길 때까지 k 더 많은 방법이 있다는 것을 보는 것입니다.

def enhanced_sum_with_lists(L,target): 
    cnt=[1]+[0]*target # 1 way to make 0 
    for x in L: 
     for z in range(target,x-1,-1): # [target, ..., x+1, x] 
      cnt[z] += cnt[z-x] 
    return cnt[target] 

그러나 순서가 중요 : z은 좋은 카운트 (PM 2Ring 덕분에) 가지고, 여기 자손 고려되어야한다.

큰 목록의 경우 매우 빠릅니다 (n*target 개 추가). 예를 들어

:

>>> enhanced_sum_with_lists(range(1,100),2500) 
875274644371694133420180815 

61 MS에서 얻어진다. 첫 번째 방법으로 우주의 나이를 계산할 것입니다.

Answer 2

코드에 두 가지 오타가 있습니다. counter1 == 0은 부울이며 아무 것도 재설정하지 않습니다.

이 버전은 작동합니다 :

def p(lst, n): 
    counter2 = 0 
    power_list = pow(lst)  
    for p in power_list: 
     counter1 = 0 #reset the counter for every new subset 
     for j in p: 
      counter1 += j 
     if counter1 == n: 
      counter2 += 1 
    return counter2 

Answer 3

from itertools import chain, combinations 

def powerset_generator(i): 
    for subset in chain.from_iterable(combinations(i, r) for r in range(len(i)+1)): 
     yield set(subset) 

def count_sum(s, cnt): 
    return sum(1 for i in powerset_generator(s) if sum(k for k in i) == cnt) 

print(count_sum(set([3,5,8,9,11,12,20]), 20)) 

Answer 4

tobias_k으로하고 Faibbus 언급, 당신은 오타가 있습니다 counter1 == 0 대신 counter1 = 0의 두 곳에서. counter1 == 0은 True 또는 False의 부울 객체를 생성하지만 해당 표현식의 결과를 지정하지 않으므로 결과가 버려집니다. SyntaxError을 발생시키지 않습니다. 할당되지 않은 표현식은 합법적 인 Python입니다.

John Coleman과 B. M.이 언급했듯이 전체 powerset을 만든 다음 각 하위 집합이 올바른 합계를 가지는지 테스트하는 것은 효율적이지 않습니다. 이 방법은 입력 시퀀스가 ​​작 으면 적당하지만 크기가 적당한 시퀀스의 경우에는 매우 느립니다. 생성기를 사용하지 않고 서브 세트가 포함 된 목록을 실제로 생성하고 서브 세트를 테스트하면 곧 실행됩니다 RAM에서.

B.의 첫 번째 솔루션은 목표 합계보다 큰 하위 집합을 생성하지 않기 때문에 매우 효율적입니다. (B. M.이 그 dict 기반 솔루션으로 무엇을하고 있는지 잘 모르겠습니다 ...).

하지만 합계 목록을 정렬하여이 접근법을 향상시킬 수 있습니다. 그렇게하면 합이 너무 높다는 것을 감지하자마자 for 루프에서 벗어날 수 있습니다. 사실 for 루프의 각 반복에서 sums 목록을 정렬해야하지만 다행스럽게도 Python의 TimSort는 매우 효율적이며 정렬 된 하위 시퀀스가 ​​포함 된 목록 정렬을 처리하도록 최적화되어 있으므로이 응용 프로그램에 이상적입니다.

def subset_sums(seq, goal): 
    sums = [0] 
    for x in seq: 
     subgoal = goal - x 
     temp = [] 
     for y in sums: 
      if y > subgoal: 
       break 
      temp.append(y + x) 
     sums.extend(temp) 
     sums.sort() 
    return sum(1 for y in sums if y == goal) 

# test 

lst = [3, 5, 8, 9, 11, 12, 20] 
total = 20 
print(subset_sums(lst, total)) 

lst = range(1, 41) 
total = 70 
print(subset_sums(lst, total)) 

lst = range(1, 41)total = 70과 함께 출력

5 
28188 

이 코드는 약 3 배 빠른 B.M.보다 버전을 나열합니다.