Αναδρομική εύρεση υποσυνόλου

[45thjohn]

Έχω ένα πίνακα με αριθμούς και θέλω να βρω με αναδρομικό τρόπο όλα τα δυνατά υποσύνολα του που ισούνται με έναν άλλο αριθμό S.

Πχ.

Έχω τον πίνακα Table[1,2,3,4]

 και S=6 

Θέλω έναν αναδρομικό τρόπο που να μου εμφανίζει τα υποσύνολα χ1[1,2,3]

χ2[2,4]

 

Έχει κανείς καμία ιδέα?

Ευχαριστώ εκ των προτέρων!

 

 

 

[DeltaLover]

Ο καλυτερος τροπος για να λυσεις το προβλημα αυτο στηριζεται σε Site: Dynamic Programming .

 

Ξεκινα απο την κατανoηση του Site: Knapsack problem . Αυτο που ζητας ειναι μια παραλλαγη του...

[albNik]

 F({1,2,3,4})=  {1,2,3,4} + F{1,2,3}) + F{1,2,4}) + F{1,3,4})+  F{2,3,4})= ....

Αν καποιο συνολο εχει αθροισμα <S δεν κοιτας τα υποσυνολα του

[DeltaLover]

Εδω σου εγραψα ενα προγραμματακι που λυνει το προβλημα σου (οχι ομως με τον βελτιστο τροπο!).  Βλεπεις πως να το βελτιωσεις μηπως?

#!/usr/bin/python
# save this as test2.py
'''
Finds all the subsets of an integer array having a specific sum...  

To test from the command line:
python test2.py -v
'''

class SubsetFinder(object):
    '''
    >>> from test2 import SubsetFinder
    >>> sf=SubsetFinder()
    >>> sf([1,2,3,4], 6)
    [1, 2, 3]
    [2, 4]
    '''
    def __call__(self, list_of_numbers, desired_total):
        self.desired_total = desired_total
        self.stack = []
        return self.process_subset(list_of_numbers, 0, len(list_of_numbers))

    def process_subset(self, data, from_index, to_index):
        if sum(self.stack) == self.desired_total:
            print self.stack
        for current in range(from_index, to_index):
            if (sum(self.stack) + data[current] <= self.desired_total):
                self.stack.append(data[current])
                self.process_subset(data, current + 1, to_index)
                self.stack.pop()

if __name__ == '__main__':
    import doctest
    doctest.testmod()