Advertisement
Pella86

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!
Python 3.00 KB | None | 0 0
  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.    
  17.     def add_node(self, node):
  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)
  49.                 node.add_node(child) #add the node to the parent
  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)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement