On Jun 20, 12:37 pm, [EMAIL PROTECTED] (Alex Martelli) wrote: > [EMAIL PROTECTED] <[EMAIL PROTECTED]> 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. -- http://mail.python.org/mailman/listinfo/python-list
