Permutation over a list with selected elements

[weidongtom at gmail.com]

On Jun 20, 12:37 pm, a... at mac.com (Alex Martelli) wrote:
> weidong... at gmail.com <weidong... at gmail.com> wrote:
> > Hi,
>
> > I have been working at this problem, and I think I need apermutation
> > algorithm that does
> > the following:
>
> > 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']
>
> > Can anyone help me out? Thanks in advance.
>
> I would proceed in 2 steps:
> 1. find all the sets of indices that are to be permuted
> 2. produce all the permutations given said sets
>
> Now (1) is pretty easy:
>
> import collections
>
> def find_sets_of_indices_to_permute(L):
>     set_by_letter = collections.defaultdict(list)
>     for i, elem in enumerate(L):
>         if len(elem)>1:
>             set_by_letter[elem[0]].append(i)
>     return set_by_letter.values()
>
> For (2), it looks like we need 2 sub-steps:
>
> 2.1.  do all permutations of a list given ONE set of indices to permute
> 2.2.  apply the function sub (2.1) to all the sets of indices to permute
>
> let's do 2.1 the lazy way, i.e., recursively:
>
> def all_permutations_given_indices(L, indices):
>     yield L
>     if len(indices) < 2:
>         return
>     x = indices.pop()
>     pivot = L[x]
>     for y in indices:
>         L[x] = L[y]
>         L[y] = pivot
>         for permut in all_permutations_given_indices(L, indices):
>             yield permut
>         L[y] = L[x]
>     L[x] = pivot
>     indices.append(x)
>
> This suggests doing 2.2 recursively as well:
>
> def all_permutations_with_constraints(L, constraints):
>     if len(constraints) == 1:
>         for p in all_permutations_given_indices(L, constraints[0]):
>             yield L
>         return
>     indices = constraints.pop()
>     for p in all_permutations_given_indices(L, indices):
>         for pp in all_permutations_with_constraints(p, constraints):
>             yield pp
>     constraints.append(indices)
>
> and, putting it all together:
>
> def do_it_all(L):
>     sets_of_indices = find_sets_of_indices_to_permute(L)
>     for p in all_permutations_with_constraints(L, sets_of_indices):
>         print p
>
> Applied to your example list, this gives:
>
> brain:~ alex$ python cp.py
> ['a', 'b', 'c1', 'd', 'e1', 'f', 'c2', 'x', 'e2']
> ['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']
>
> Warning: untested beyond this single run, and _definitely_ not optimal
> in either clarity, style, or speed -- just a quick hack to get you
> started.
>
> Alex

Thanks.