Permutation over a list with selected elements
weidongtom at gmail.com
weidongtom at gmail.com
Wed Jun 20 07:02:39 CEST 2007
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.
More information about the Python-list
mailing list