448,678 Members | 1,175 Online Need help? Post your question and get tips & solutions from a community of 448,678 IT Pros & Developers. It's quick & easy.

# Permutation over a list with selected elements

 P: n/a 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. Jun 19 '07 #1
3 Replies

 P: n/a we********@gmail.com 1: set_by_letter[elem].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): 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 Jun 20 '07 #2

 P: n/a On Jun 20, 12:37 pm, a...@mac.com (Alex Martelli) wrote: weidong...@gmail.com 1: set_by_letter[elem].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): 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. Jun 20 '07 #3

 P: n/a we********@gmail.com wrote: 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'] Another idea, untested. Also I am not sure whether sequences types are supposed to be returning functions ... A. from operator import mul from collections import defaultdict class Swapper: """ Given a set of indices this class returns functions which will swap elements in a list *in place*. Each function corresponds to a permutation of the set of indices. """ def __init__(self,L): self.L = L self.n = reduce(mul,range(2,len(L)+1),1) #faculty def __getitem__(self,i): L = self.L if not -11: set_by_letter[elem].append(i) return set_by_letter.values() def test(): L = ['a', 'b', 'c1', 'd', 'e1', 'f', 'c2', 'x', 'e2'] I = find_sets_of_indices_to_permute(L) #Alex Martelli's function M = map(Swapper,I) for F in cross(M): # conserve the original list because #the functions modify a list in place R = list(L) # apply each permutation function one by one, # each is acting on a different set of indices for fn in F: fn(R) print R if __name__=='__main__': test() Jun 20 '07 #4

### This discussion thread is closed

Replies have been disabled for this discussion. 