##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 <nsets> sets.
The returned function has the signature
F(set0, set1, ..., set<nsets>)
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)
