Forum libero

> > > def subsets(aset, n):
> > >     if len(aset) < n: return []
> > >     if n == 0: return [set()]
> > >     r = []
> > >     remaining_set = set(aset)
> > >     for element in aset:
> > >         remaining_set.remove(element)
> > >         for subset in subsets(remaining_set,
> > n-1):
> > >             subset.add(element)
> > >             r.append(subset)
> > >     return r
> > > 
> > > import sys
> > > if __name__ == '__main__':
> > >     size = int(sys.argv[1])+1
> > >     r = []
> > >     for n in range (0, size):
> > >         r.append(subsets(set(range(1, size)),
> > n))
> > > 

> 23:13 @suoranciata sarru: dammi una mano
> 23:13 @suoranciata dato un array di interi
> 23:13 @suoranciata metti 1,2,3,4,5
> 23:13 @suoranciata come faccio a trovare tutti i
> possibili
> subsets
> 23:14 @sarru con una enumerazione esaustiva
> ricorsiva
> 23:14 @sarru per esempio
> 23:14 @suoranciata anche con "i buchi" eh
> 23:14 @suoranciata 1,2,4 è un subsets per come mi
> serve
> 23:14 @sarru si`
> 23:15 @suoranciata ah prendo 1, e lo accoppio ai
> subset di
> 2-5
> 23:15 @suoranciata non mi è chiaro
> 23:16 @sarru diciamo che subsets(inputset, n) e`
> l'insieme vuoto se n == 0 oppure per ogni
> elemento x in inputset devi restituire tutti i
> subset restituiti da subsets(inputset\{x}, n-1)
> con l'elemento x
> attaccato
> 23:16 @sarru quello che vuoi te e` l'unione di
> tutti i subsets(inputset, n) con n = 0 ..
> len(inputset)
> 23:17 @suoranciata mumble
> 23:17 @sarru come mai lo vuoi sapere?
> 23:17 @suoranciata non mi è chiaro come
> implementarlo
> 23:18 @suoranciata giocavo a greplin programming
> challenge, è l'ultima
> domanda
> ...
> 00:37 @suoranciata ho un input di 21 numeri, non
> posso credere che la soluzione necessiti di così
> tanto
> 00:38 @suoranciata in genere i giochini di
> project euler se ci mettevi più di 4-5 secondi
> eri sulla strada
> sbagliata
> 00:38 @suoranciata questo immagino sia simile
> 00:40 @suoranciata il numero di subset + l'array
> stesso è pari a 2^n -
> 1
> 00:40 @suoranciata prevedendo le dimensioni forse
> ne ricavo
> qualcosa
> 00:59 @sarru suoranciata passera` la notte a
> lottare contro un algoritmo
> esponenziale
> 01:00 @suoranciata ho buone probabilità di vincere
> 01:00 @sarru lol
> 01:00 @sarru certo
> --- Log closed Fri Oct 08 00:11:44 2010
> 

> input_vector = [3, 4, 9, 14, 15, 19, 28, 37, 47,
> 50, 54, 56, 59, 61, 70, 73, 78, 81, 92, 95, 97,
> 99]
> 
> maximum = max(input_vector)
> 
> result = 0
> 
> def suoranciata(sum, start):
>     print "called with sum:", sum
>     if sum > maximum: return
>     for i in range(start, len(input_vector)):
>         if input_vector[i] == sum:
>             print "incrementing result ",
> selection, " + ",
> input_vector[i]
>             global result
>             result += 1
>         print "selected:", input_vector[i]
>         suoranciata(sum + input_vector[i], i+1)
>     print "returning"
> 
> suoranciata(0, 0)
> print len(input_vector), result
>