[Tutor] Permutations

[Carlo Bifulco]

Hi folks,

I have a small computing problem that I solved in an extremely ugly and 
ad hoc way. I am submitting it here since I am sure that there must be 
much better ways to address  it  (and I am obviously not able to find 
them).

Here is what I would like to be able to do:
 >>> permute(["a"])
[['a']]
 >>> permute(["a","b"])
[['a'], ['a', 'b'], ['b']]
 >>> permute(["a","b","c"])
[['a'], ['a', 'b'], ['a', 'c'], ['a', 'b', 'c'], ['b'], ['b', 'c'], ['c']]
 >>> permute (["a","b","c","d"])
[['a'], ['a', 'b'], ['a', 'c'], ['a', 'd'], ['a', 'b', 'c'], ['a', 'b', 
'd'], ['a', 'c', 'd'], ['a', 'b', 'c', 'd'], ['b'], ['b', 'c'], ['b', 
'd'], ['b', 'c', 'd'], ['c'], ['c', 'd'], ['d']]
 >>> permute ("a","b",...) and so on...

It's actually a practical problem, since I am analyzing all  possible 
combinations of a group of  restriction enzymes and
1) I do not care in which order they are.
2) I don't care of repeated items.
I.e. in this setting:
 >>> ["a","b"]==["b","a"]
 >>> ["a","a"]==["a"]

I appended to the bottom of this my current solution to the problem; the 
code is ugly and obviously does not scale at all; don't  bother reading 
it unless you have a lot of free time...

Thanks for your help,
Carlo

class Permutator (list):
   """
   >>> cleaner(Permutator(["a","b","None","None"])())
   [['a'], ['a', 'b'], ['b']]
   >>> cleaner(Permutator(["a","b","c","None"])())
   [['a'], ['a', 'b'], ['a', 'c'], ['a', 'b', 'c'], ['b'], ['b', 'c'], 
['c']]
   >>>
   """

   def __init__(self,listOfEnzymes):
       self.listOfEnzymes=listOfEnzymes
       self.a,self.b,self.c,self.d=self.listOfEnzymes
       self.append([])

   def add(self,item):
       for i in self:
           #print item,
           if self.equal(i,item):
               #print "EQUAL"
               return
       self.append(item)
             def combine(self):
       #XXX THESE IS AD HOCK FOR 4 ENZYMES; UGLY
       self.tempList=[[a,b,c,d] for a in self.listOfEnzymes for b in 
self.listOfEnzymes for c in self.listOfEnzymes for d in self.listOfEnzymes]

   def equal(self,x,y):
       #XXX AGAIN AD HOC
       if x.count(self.a)==y.count(self.a) and  
x.count(self.b)==y.count(self.b) and  x.count(self.c)==y.count(self.c) 
and  x.count(self.d)==y.count(self.d):
           return 1
       return 0

   def __call__(self):
       self.combine()
       for i in self.tempList:
           self.add(i)
       try:
           self.remove([])
       except ValueError:
           pass
       return self
      def cleaner(listOfPermutations):
   """
   >>> cleaner([["a"],["a"],["a","a","b"],["b","b","a"]])
   [['a'], ['a', 'b'], ['b', 'a']]
   >>>
   """
   newList=[]
   for i in listOfPermutations:
       temp=[]
       for e in i:
           if e not in temp:
               if e=="None":
                   continue
               temp.append(e)
       newList.append(temp)
   d=[]
   for i in newList:
       if i not in d:
           d.append(i)
   try:
       d.remove([])
   except ValueError:
       pass
   return d

-- 
Carlo B. Bifulco, MD
Yale University School of Medicine
EP2-608
310 Cedar Street
New Haven, CT 06520
Tel: 203 737 2818
Fax: 203 737 2922