Somma sottoinsieme ricorsiva in Python

Question

Sarò felice di ricevere aiuto.

Ho il seguente problema:

sto dato un elenco di numeri seq e di un numero di destinazione e ho bisogno di scrivere 2 cose:

1. Una soluzione ricorsiva che ritorna True se ci è una somma di una sottosequenza uguale al numero di destinazione e False in caso contrario. esempio:

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

2. In secondo luogo, ho bisogno di scrivere una soluzione che utilizza quello che ho scritto nel precedente soluzione ma ora con Memoizzazione che utilizza un dizionario in cui le chiavi sono tuple: (len(seq),target)

per il numero 1 questo è quello che ho avuto modo finora:

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 

Non sono sicuro che ho capito bene, quindi se potessi ricevere un contributo, te ne sarei grato.

Per il numero 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] 

non riesco a ottenere il Memoizzazione di darmi la risposta corretta in modo da sarei contento per alcune indicazioni qui.

Grazie per chiunque sia disposto ad aiutare!

Answer 1

ho questo codice modificato:

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] 

Potete fornire alcuni casi di test questo non funziona per?

Answer 2

Questo è il modo che avrei scritto il 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 

Ha funzionato su un paio di esempi:

>>> 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 

Per essere onesti non saprei come Memoize esso.

Vecchio Modifica: Ho rimosso la soluzione con any() perché dopo alcuni test ho scoperto che per essere più lento!

Update: Solo per curiosità si potrebbe anche usare 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 

Questo può fare di meglio che l'approccio di programmazione dinamica, in alcuni casi, ma in altri si bloccherà (è comunque meglio allora il ricorsiva approccio).

Answer 3

Solo per riferimento, ecco una soluzione con programmazione dinamica:

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]