Problem with algorithm

[Charles Sanders]

mensanator at aol.com wrote:
> On Apr 12, 10:16�pm, "Jia Lu" <Roka... at gmail.com> wrote:
>> Hi all.
>> �I want to create a large list like:
>>
>> aaaa ~ zzzz
>>
>> Is there any good algorithm to do this?
> 
> Sure.
> test = '01'
> 
> for m in test:
>     for n in test:
>         for o in test:
>              for p in test:
>                 print m+n+o+p
[snip]

Forgive any silly mistakes I have made (I've been teaching
myself python for about 1 week) but there is a moderately
well known algorithm for this that extends to arbitrary
lengths of both the list of alternatives and the length
of the required output, and avoids deeply nested loops.
I know that it is no better for small and constant output
lengths, but for longer lengths or if the output length
can vary it should be better. There is a similar algorithm
if duplicates are not allowed (ie abcd ... wxyz).

My attempt at a python translation of the algorithm:

def m_from_n ( v, m ):
   """
   Print all combinations of m things from v[0] ... v[n-1],
   duplicates OK. Yields a list.
   """
   x = [0] * m
   while True:
     yield [ v[i] for i in x ]
     i = m - 1
     while i>=0 and x[i]==len(v)-1:
       x[i] = 0
       i = i - 1
     if i >= 0:
       x[i] = x[i] + 1
     else:
       return

for y in m_from_n( "xyz", 2 ):
   print ''.join(y)

xx
xy
xz
yx
yy
yz
zx
zy
zz

for y in m_from_n( [0,1], 3 ):
   print y

[0, 0, 0]
[0, 0, 1]
[0, 1, 0]
[0, 1, 1]
[1, 0, 0]
[1, 0, 1]
[1, 1, 0]
[1, 1, 1]

for y in m_from_n( "abcdefghijklmnopqrstuvwxyz", 4 ):
   print ''.join(y)

should more or less do what you want.

Charles