Permutation over a list with selected elements

[Alex Martelli]

weidongtom at gmail.com <weidongtom at gmail.com> wrote:

> Hi,
> 
> I have been working at this problem, and I think I need a permutation
> 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