Permutation over a list with selected elements

[Anton Vredegoor]

weidongtom at gmail.com wrote:

> Given a list of elements that are either a character or a character
> follows by a number, e.g.
> 
> ['a', 'b', 'c1', 'd', 'e1', 'f', 'c2', 'x', 'e2']
> 
> find all the permutations that are given by switching the positions of
> the elements that:
>  (1) begins with the same letter, and
>  (2) follows by a number.
> 
> With the above list, some possible permutations are:
> 
> ['a', 'b', 'c2', 'd', 'e1', 'f', 'c1', 'x', 'e2']
> ['a', 'b', 'c1', 'd', 'e2', 'f', 'c2', 'x', 'e1']
> ['a', 'b', 'c2', 'd', 'e2', 'f', 'c1', 'x', 'e1']

Another idea, untested. Also I am not sure whether sequences types are 
supposed to be returning functions ...

A.

from operator import mul
from collections import defaultdict

class Swapper:
     """
         Given a set of indices this class returns functions
         which will swap elements in a list *in place*.
         Each function corresponds to a permutation of the
         set of indices.
     """

     def __init__(self,L):
         self.L = L
         self.n = reduce(mul,range(2,len(L)+1),1) #faculty

     def __getitem__(self,i):
         L = self.L
         if not -1<i<self.n:
             raise IndexError
         def func(R):
             Q = perm([R[j] for j in L],i)
             for j,x in zip(L,Q):
                 R[j] = x
         return func

def perm(L,m):
     #permutation m of list L
     res = []
     T = L[::-1]
     for i in range(len(L),0,-1):
         res.append(T.pop(m%i))
         m /= i
     return res[::-1]

def cross(args):
     #Raymond Hettinger's cross product function from ASPN
     ans = [[]]
     for arg in args:
         ans = [x+[y] for x in ans for y in arg]
     return ans

def find_sets_of_indices_to_permute(L):
     set_by_letter = defaultdict(list)
     for i, elem in enumerate(L):
         if len(elem)>1:
             set_by_letter[elem[0]].append(i)
     return set_by_letter.values()

def test():
     L =  ['a', 'b', 'c1', 'd', 'e1', 'f', 'c2', 'x', 'e2']
     I = find_sets_of_indices_to_permute(L) #Alex Martelli's function
     M = map(Swapper,I)
     for F in cross(M):
         # conserve the original list because
         #the functions modify a list in place
         R = list(L)
         # apply each permutation function one by one,
         # each is acting on a different set of indices
         for fn in F:
             fn(R)
         print R

if __name__=='__main__':
     test()