# Special case of the subset sum problem

Apr 15th, 2012
164
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #!/usr/bin/env python
2.
3. #required for GiocoScopa
4. from copy import deepcopy
5.
6. #the subset sum problem
7. #find the possible combination of integer list that sums up to a given n
8. #a brute force algorithm to find the subset sum
9. #more then 10 elements in the list get slower
10. #tested only if the list of element does not contain a repeated element
11.
12. class Node:
13.     def __init__ (self, value = None):
14.         self.card = value #holds the value
15.         self.nodes = [] #holds the nodes
16.
18.         self.nodes.append(node)
19.
20.     def get_card(self):
21.         return self.card
22.
23.     def value(self):
24.         return self.card.number
25.
26.     def __str__(self):
27.         #print the node with this format
28.         #id:0x10049f7e8 value: 5 childs: 0
29.         s = 'id:'+ str(hex(id(self))) + ' card: ' + str(self.card) + " childs: " + str(len(self.nodes))
30.         return s
31.
32.
33. class SumTree:
34.     def __init__(self, deck, target = None):
35.         self.root = Node() #first node has value 0
36.         #two option one build the entire tree which is n*n or more big
37.         #the other build the tree only until a known target
38.         if target == None: "fool you forgot the target"
39.         self.build_from_list_opt(self.root, deck, target)
40.
41.
42.
43.
44.     def build_from_list_opt(self, node, deck, target):
45.         #populate the tree
46.         for i , card in enumerate(deck.cards):
47.             if card.number <= target:
48.                 child = Node(card)
50.                 #the list is copied to an other list without the first element
51.                 #already stored in in the node child
52.                 copy_deck = deepcopy(deck)
53.                 copy_deck.cards = copy_deck.cards[i+1:]
54.                 #the list get smaller and smaller until it has no elements
55.                 #and the recursion stops
56.                 if not (len(copy_deck.cards) == 0):
57.                     self.build_from_list_opt(child, copy_deck, target)
58.
59.
60.     def find_sum_node(self, node, sum, path, r_count, res_path, target):
61.         #return the numbers (path) that composed that target
62.         #argument list:
63.         #   node: the actual node
64.         #   sum: sum until the actual node
65.         #   path: list containing the values of the nodes summing up to the actual node
66.         #   r_count: recursion count needed to reset the path
67.         #   res_path: stores the values that sums up to target
68.         #   target: given integer
69.
70.         if not r_count == 0: sum += node.value()
71.         r_count += 1
72.         path.append(node.get_card())
73.         if (sum == target):
74.             res_path.append(path[1:]) #the root is not appended in the list
75.         elif (sum > target):
76.             pass
77.         else:
78.             for child in node.nodes:
79.                 #reset the path until the switch
80.                 path = path[:r_count]
81.                 self.find_sum_node(child, sum, path, r_count, res_path, target)
82.
83.
84.
85.     def find_sum(self, target):
86.         res_path, tmp_path = [], []
87.         sum, r_count = 0, 0
88.         self.find_sum_node(self.root, sum, tmp_path, r_count, res_path, target)
89.         return res_path
90.
91.     def print_node(self,node, s, count):
92.
93.         s = "  |"*count  + str(node)+ "\n"
94.         count += 1
95.
96.         for child in node.nodes:
97.             s += self.print_node(child, s, count)
98.         return s
99.
100.     def __str__(self):
101.         return self.print_node(self.root, "", 0)