# gives all possible integer vectors between two endpoints, inclusively. For example:
# IntVectorRange([0,0,2], [1,1,3]) yields:
# [0, 0, 2]
# [1, 0, 2]
# [0, 1, 2]
# [1, 1, 2]
# [0, 0, 3]
# [1, 0, 3]
# [0, 1, 3]
# [1, 1, 3]
# if only one argument is given to __init__, then the range goes from [0,0,...,0] to the vector given
class IntVectorRange(object):
def __init__(self,start,end=None):
if end is None:
end=start
start=[0] * len(end)
self.start=start
self.end=end
self.size = len(start)
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
r = [0] * self.size
for i in xrange(self.size):
r[i] = index % self.delta[i] + self.start[i]
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 __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)
This can be used to build a simple combinatorial optimizer:
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)