[Tutor] combinations

[Bob Gailer]

At 12:42 PM 5/10/2003 +0200, Andreas Zwinkau wrote:

>I wrote a program to print out all kominbations of a given string
>123:
>1 2 3
>1 3 2
>2 1 3
>2 3 1
>3 1 2
>3 2 1

These are permutations not combinations.

>I had to write a function to check wether a number is in the current
>possibility yet
>def partof(needle, heystack):
>         """ is needle in heystack? """
>         for x in heystack:
>                 if needle == x:
>                         return 1
>         return 0
>
>First i tried to do it this way
>         if neddle in heystack:
>1. This would be short but is not possible, is it??
>
>Another problem was the recursion
>         for current in range(len(full)): # try all combinations
>                 if not partof(current, yet):
>                         yet.append(current) # add ne possible element
>                         yet = kombies(yet, full)[0:-1]
>         return yet
>First i tried this
>                         yet.append(current)
>                         kombies(yet, full) #kombies returns nothing
>                         yet = yet[0:-1] #kick the last element to try another
>But this did not work.
>2. Python never got back to the first stage of the recursion. why?
>
>attached is the full program as it works

Try this version: it actually generates each permutation; there's no need 
to check for duplicates:

#!/usr/bin/python
import sys
def tree(txt, indices=None, result=None):
   if not result:
     n = len(txt)
     indices = range(n)
     result = ['']*n
   else:
     n = len(indices)
   if n:
     for i in range(n):
       indices2 = indices[:]
       j = indices2.pop(i)
       result[n-1] = txt[j]
       tree(txt, indices2, result)
   else:
     print ''.join(result)

if __name__ == "__main__":
   tree(sys.argv[1])


Bob Gailer
bgailer@alum.rpi.edu
303 442 2625