Welcome, guest | Sign In | My Account | Store | Cart
##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)

History

  • revision 3 (18 years ago)
  • previous revisions are not available