[EMAIL PROTECTED] <[EMAIL PROTECTED]> 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
--
http://mail.python.org/mailman/listinfo/python-list
