Tập hợp con số đệ quy trong Python

Question

Tôi sẽ rất vui khi được trợ giúp.

Tôi có vấn đề sau đây:

tôi cung cấp một danh sách các số seq và một số mục tiêu và tôi cần phải viết 2 điều:

1. Một giải pháp đệ quy mà trả True nếu có là tổng của một dãy số bằng số mục tiêu và False nếu không. dụ:

   subset_sum([-1,1,5,4],0) # True 
   subset_sum([-1,1,5,4],-3) # False 
   

2. Thứ hai, tôi cần phải viết một giải pháp sử dụng những gì tôi đã viết trong các giải pháp trước nhưng bây giờ với memoization sử dụng một cuốn từ điển, trong đó các phím là các bộ: (len(seq),target)

Đối số 1 đây là những gì tôi đã cho đến nay:

def subset_sum(seq, target): 
    if target == 0: 
     return True 
    if seq[0] == target: 
     return True 
    if len(seq) > 1: 
     return subset_sum(seq[1:],target-seq[0]) or subset_sum(seq[1:],target) 
    return False 

Không chắc tôi có nó đúng vì vậy nếu tôi có thể nhận được một số đầu vào, tôi sẽ biết ơn.

Đối số 2:

def subset_sum_mem(seq, target, mem=None): 
    if not mem: 
     mem = {} 
    key=(len(seq),target) 
    if key not in mem: 
     if target == 0 or seq[0]==target: 
      mem[key] = True 
     if len(seq)>1: 
      mem[key] = subset_sum_mem(seq[1:],target-seq[0],mem) or subset_sum_mem(seq[1:],target,mem) 
     mem[key] = False 

    return mem[key] 

tôi không thể có được memoization để cho tôi câu trả lời đúng vì vậy tôi muốn được vui đối với một số hướng dẫn ở đây.

Cảm ơn bất kỳ ai sẵn sàng trợ giúp!

Answer 1

tôi có mã sửa đổi này:

def subset_sum(seq, target): 
    left, right = seq[0], seq[1:] 
    return target in (0, left) or \ 
     (bool(right) and (subset_sum(right, target - left) or subset_sum(right, target))) 

def subset_sum_mem(seq, target, mem=None): 
    mem = mem or {} 
    key = (len(seq), target) 
    if key not in mem: 
     left, right = seq[0], seq[1:] 
     mem[key] = target in (0, left) or \ 
      (bool(right) and (subset_sum_mem(right, target - left, mem) or subset_sum_mem(right, target, mem))) 
    return mem[key] 

Bạn có thể cung cấp một số trường hợp thử nghiệm này không làm việc cho?

Answer 2

Đây là cách tôi muốn viết subset_sum:

def subset_sum(seq, target): 
    if target == 0: 
     return True 

    for i in range(len(seq)): 
     if subset_sum(seq[:i] + seq[i+1:], target - seq[i]): 
      return True 
    return False 

Nó làm việc trên một vài ví dụ:

>>> subset_sum([-1,1,5,4], 0)) 
True 
>>> subset_sum([-1,1,5,4], 10) 
True 
>>> subset_sum([-1,1,5,4], 4) 
True 
>>> subset_sum([-1,1,5,4], -3) 
False 
>>> subset_sum([-1,1,5,4], -4) 
False 

Thành thật mà nói tôi sẽ không biết làm thế nào để memoize nó.

Chỉnh sửa cũ: Tôi đã xóa giải pháp với any() vì sau một số thử nghiệm, tôi phát hiện ra là chậm hơn!

Cập nhật: Chỉ cần ra khỏi tò mò bạn cũng có thể sử dụng itertools.combinations:

from itertools import combinations 

def com_subset_sum(seq, target): 
    if target == 0 or target in seq: 
     return True 

    for r in range(2, len(seq)): 
     for subset in combinations(seq, r): 
      if sum(subset) == target: 
       return True 
    return False 

Điều này có thể làm tốt hơn mà phương pháp lập trình năng động trong một số trường hợp nhưng trong những người khác nó sẽ treo (nó nào tốt hơn thì đệ quy tiếp cận).

Answer 3

Chỉ cần để tham khảo, đây là một giải pháp sử dụng lập trình năng động:

def positive_negative_sums(seq): 
    P, N = 0, 0 
    for e in seq: 
     if e >= 0: 
      P += e 
     else: 
      N += e 
    return P, N 

def subset_sum(seq, s=0): 
    P, N = positive_negative_sums(seq) 
    if not seq or s < N or s > P: 
     return False 
    n, m = len(seq), P - N + 1 
    table = [[False] * m for x in xrange(n)] 
    table[0][seq[0]] = True 
    for i in xrange(1, n): 
     for j in xrange(N, P+1): 
      table[i][j] = seq[i] == j or table[i-1][j] or table[i-1][j-seq[i]] 
    return table[n-1][s]