##from __future__ import generators # for Python 2.2 ###################################################################### ## ## public interface ## ###################################################################### # SetElemCombinations.py def ByNestedComprehnsionAlogrithm(*sets): """Returns a list of all element combinations from the given sets. A combination is represented as a tuple, with the first tuple element coming from the first set, the second tuple element coming from the second set and so on. A set may be any iterable to which the not operator is applicable. """ g = [] for set in sets: if not set: return [] if g: g = [ i + (j,) for i in g for j in set ] else: g = [(j,) for j in set] return g def ByRecursiveGeneratorAlrgorithm(*sets): """Returns a generator that yields one tuple per element combination. A set may be any iterable to which the not operator is applicable. """ if not sets: return def calc(sets): head, tail = sets[0], sets[1:] if not tail: for e in head: yield (e,) else: for e in head: for t in calc(tail): yield (e,) + t return calc(sets) def ByDynamicallyGeneratedCode(*sets): if not sets: return [] F = MakeListComprehensionFunction ('F', len(sets)) return F(*sets) def MakeListComprehensionFunction (name, nsets): """Returns a function applicable to exactly sets. The returned function has the signature F(set0, set1, ..., set) and returns a list of all element combinations as tuples. A set may be any iterable object. """ if nsets <= 0: source = 'def %s(): return []\n' % name else: constructs = [ ('set%d'%i, 'e%d'%i, 'for e%d in set%d'%(i,i)) for i in range(nsets) ] a, e, f = map(None, *constructs) ##e.reverse() # <- reverse ordering of tuple elements if needed source = 'def %s%s:\n return [%s %s]\n' % \ (name, _tuplestr(a), _tuplestr(e), ' '.join(f)) scope = {} exec source in scope return scope[name] def _tuplestr(t): if not t: return '()' return '(' + ','.join(t) + ',)' ###################################################################### ## ## demo ## ###################################################################### ListOfCombinations = ByDynamicallyGeneratedCode GenerateCombinations = ByRecursiveGeneratorAlrgorithm if __name__ == '__main__': print print 'All possible 3-bit binary numbers:' all = ListOfCombinations(*[(0,1)]*3) print '\t', ', '.join([ ''.join(map(str, digits)) for digits in all ]) numbers = [ reduce(lambda n, d: n << 1 | d, digits, 0) for digits in all ] print '\t', ', '.join(map(str, numbers)) print 'Some controverse statements:' all = ListOfCombinations( ('python', 'ruby'), ('is cool', 'is ok', 'sucks') ) for each in all: print '\t', ' '.join(each).capitalize() # When you need several combinations from N (possibly different) sets # increase speed by obtaining a function for N sets ... print 'Several combinations from 2 sets:' F = MakeListComprehensionFunction('F', 2) print '\t', F( (1,2,3), (10,20) ) print '\t', F( '+-', 'x' ) # When you need to iterate through lots of combinations, # save memory using a generator ... print 'Some binary operations:' G = GenerateCombinations( 'ab', '+-*/', 'x' ) for each in G: print '\t', ' '.join(each) print 'Some binary operations calculated by ByNestedComprehnsionAlogrithm:' G = ByNestedComprehnsionAlogrithm( 'ab', '+-*/', 'x' ) for each in G: print '\t', ' '.join(each)