subset permutations

[Jay Parlar]

On Dec 8, 2005, at 5:29 PM, dgspambot at gmail.com wrote:
>
> Hello all,
>  
> I'm a beginner with programming. Trying to teach myself with that  
> excellent rat book. Unfortunately I just can't seem to figure out a  
> simple problem that has come up at my work (biology lab):
> let's say I have a list  
> ['A','C','D','E','F','G','H','I','K','L','M','N','P','Q','R','S','T','V 
> ','W','Y'] . I need to generate permutations of this list. I have  
> found plenty of code on the web to generate ALL possible permutations.  
> What I need are all possible 4-letter permutations. I cannot seem to  
> figure out how to modify Mike Davie's permutation generator  
> http://www.bigbold.com/snippets/posts/show/753 to acheive this. Any  
> help would be appreciated.
>  

Well, it depends what you're asking for (an example would have helped).

For instance, say you have the list ['A','B',C','D'], and you want all  
possible TWO letter permutations. Do you want the result to be:

AB, AC, AD, BC, BD, CD

Or, do you want AB,BA,AC,CA,AD,DA,BC,CB,BD,DB,CD,DB ?

Here's a rough solution that gives you either. The first argument is  
the list of letters, the second is how many letters you want in the  
permutation, and the third is "choose", which defaults to True, meaning  
it gives my first output. Set it to False for the second output:

def perm(l,n, choose=True):
     if n > 0:
         s = set(l)
         for char in l:
             s.remove(char)
             for combo in perm(s, n-1):
                 final = str(char) + str(combo)
                 yield final
                 if not choose:
                     yield "".join(reversed(final))
      else:
          yield ""

This code assumes you're using Python 2.4 (if you're using 2.3, then  
you'll have to change the line s = set(l) to s = sets.Set(l), and do an  
'import sets' at the top of the module).

Also, this function returns an iterable, not a list, so if you want a  
straight list out of it, pass it to list(), ie.

list( perm(   
['A','C','D','E','F','G','H','I','K','L','M','N','P','Q','R','S','T','V' 
,'W','Y'], 4) )

or, if you want my second output case:

list ( perm(   
['A','C','D','E','F','G','H','I','K','L','M','N','P','Q','R','S','T','V' 
,'W','Y'], 4, choose=False))


Please note that I put this together in about five minutes, so don't  
blame me if it horribly dies and causes your computer to blow up.

Anyone have any better solutions?

Jay P.