Differences

This shows you the differences between two versions of the page.

--- python:intvectorrange [2010/05/27 08:43] – tkbletsc
+++ python:intvectorrange [2012/09/25 13:04] (current) – tkbletsc
@@ Line 10: / Line 10: @@
 #   [0, 1, 3]
 #   [1, 1, 3]
-class IntVectorRange:
+# if only one argument is given to __init__, then the range goes from [0,0,...,0] to the vector given
-	def __init__(self,start,end=None):
+class IntVectorRange(object):
-		if end is None:
+    def __init__(self,start,end=None):
-			end=start
+        if end is None:
-			start=[0] * len(end)
+            end=start
+            start=[0] * len(end)
-		self.start=start
-		self.end=end
+        self.start=start
-		self.size = len(start)
+        self.end=end
-		self.delta = [end[i]-start[i]+1  for  i in xrange(self.size)]
+        self.size = len(start)
-		self.len = reduce(lambda x,y: x*y, self.delta, 1)
+        self.delta = [end[i]-start[i]+1  for  i in xrange(self.size)]
+        self.len = reduce(lambda x,y: x*y, self.delta, 1)
-	def __getitem__(self,index):
-		if index >= self.len: raise IndexError
+    def __getitem__(self,index):
-		r = [0] * self.size
+        if index >= self.len: raise IndexError
-		for i in xrange(self.size):
+        r = [0] * self.size
-			r[i] = index % self.delta[i] + self.start[i]
+        for i in xrange(self.size):
-			index /= self.delta[i]
+            r[i] = index % self.delta[i] + self.start[i]
-		return r
+            index /= self.delta[i]
+        return r
+    def __len__(self): return self.len
+# Provides a list with all possible subsets of the given list
+# (based on a binary IntVectorRange object)
+#
+# Example: AllSubsets(['alpha','beta','gamma']) yields:
+#   []
+#   ['alpha']
+#   ['beta']
+#   ['alpha', 'beta']
+#   ['gamma']
+#   ['alpha', 'gamma']
+#   ['beta', 'gamma']
+#   ['alpha', 'beta', 'gamma']
+class AllSubsets:
+    def __init__(self,items):
+        self.vector_range = IntVectorRange([1] * len(items))
+        self.items = items
+    def __getitem__(self,index):
+        v = self.vector_range[index]
+        return [self.items[i] for i in xrange(len(v)) if v[i]]
+    def __len__(self): return len(self.vector_range)
+# for academic purposes only, here's the same class based on inheritence instead of composition
+class AllSubsets2(IntVectorRange):
+	def __init__(self,items):
+		super(AllCombinations2,self).__init__([1] * len(items))
+		self.items = items
-	def __len__(self): return self.len
+	def __getitem__(self,index):
+		v = super(AllCombinations2,self).__getitem__(index)
+		return [self.items[i] for i in xrange(len(v)) if v[i]]
+# Provides a list with all possible "choices" of the sublists of the input list
+#
+# Example: AllCombinations(["abc","123"]) yields:
+#   ['a', '1']
+#   ['b', '1']
+#   ['c', '1']
+#   ['a', '2']
+#   ['b', '2']
+#   ['c', '2']
+#   ['a', '3']
+#   ['b', '3']
+#   ['c', '3']
+class AllCombinations:
+    def __init__(self,choices):
+        self.vector_range = IntVectorRange([len(choice)-1 for choice in choices])
+        self.choices = choices
+    def __getitem__(self,index):
+        c_indices = self.vector_range[index]
+        return [self.choices[i][c_indices[i]] for i in xrange(len(self.choices))]
+    def __len__(self): return len(self.vector_range)
 </code>
+This can be used to build a simple combinatorial optimizer:
+<code=python>
+import operator
+# Optimize the return value of the given function func(), comparing return values with the is_this_better() function (which defaults to greater-than).
+# All parameters must be named parameters, and come after all other arguments. Options:
+# - Print out the latest best answer if print_on_better is True
+# - If return_choices_only is True, then the best_inputs part of the return will only have the choices, not the fixed values
+# Returns the tuple: (best_inputs,best_value)
+#
+# Example:
+#   def f(x,y,z): return x**2+x+5-y**3+z
+#   print optimize(f, x=Choice(range(-3,5)), y=Choice(range(-3,5)), z=2)
+#
+# This finds the best x and y to maximize f(x,y,z) with the given choices, with z fixed at 2.
+class Choice(list): pass
+def optimize(func, is_this_better=operator.gt, print_on_better=False, return_choices_only=False, **vargs):
+    choices = {}
+    fixed_values = {}
+    for k,v in vargs.items():
+        if isinstance(v,Choice): choices[k] = v
+        else:                    fixed_values[k] = v
+    c_keys = choices.keys()
+    c_value_choices = [choices[k] for k in c_keys]
+    best_value = None
+    best_inputs = None
+    for c_values in AllCombinations(c_value_choices):
+        chosen = dict((k,c_values[i]) for i,k in enumerate(c_keys))
+        all_values = chosen.copy()
+        all_values.update(fixed_values)
+        value = func(**all_values)
+        if best_value is None or is_this_better(value,best_value):
+            best_inputs = chosen if return_choices_only else all_values
+            best_value = value
+            if print_on_better: print best_inputs,best_value
+    return (best_inputs,best_value)
+</code>