Permutation over a list with selected elements

[weidongtom]

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.

[Alex Martelli]

we********@gmai l.com <we********@gma il.comwrote:

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_in dices_to_permut e(L):
set_by_letter = collections.def aultdict(list)
for i, elem in enumerate(L):
if len(elem)>1:
set_by_letter[elem[0]].append(i)
return set_by_letter.v alues()

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_permutation s_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_permutation s_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_permutation s_with_constrai nts(L, constraints):
if len(constraints ) == 1:
for p in all_permutation s_given_indices (L, constraints[0]):
yield L
return
indices = constraints.pop ()
for p in all_permutation s_given_indices (L, indices):
for pp in all_permutation s_with_constrai nts(p, constraints):
yield pp
constraints.app end(indices)

and, putting it all together:

def do_it_all(L):
sets_of_indices = find_sets_of_in dices_to_permut e(L)
for p in all_permutation s_with_constrai nts(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

[weidongtom]

On Jun 20, 12:37 pm, [e-mail] (Alex Martelli) wrote:

weidong...@gmai l.com <weidong...@gma il.comwrote:

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_in dices_to_permut e(L):
set_by_letter = collections.def aultdict(list)
for i, elem in enumerate(L):
if len(elem)>1:
set_by_letter[elem[0]].append(i)
return set_by_letter.v alues()

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_permutation s_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_permutation s_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_permutation s_with_constrai nts(L, constraints):
if len(constraints ) == 1:
for p in all_permutation s_given_indices (L, constraints[0]):
yield L
return
indices = constraints.pop ()
for p in all_permutation s_given_indices (L, indices):
for pp in all_permutation s_with_constrai nts(p, constraints):
yield pp
constraints.app end(indices)

and, putting it all together:

def do_it_all(L):
sets_of_indices = find_sets_of_in dices_to_permut e(L)
for p in all_permutation s_with_constrai nts(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.

[Anton Vredegoor]

we********@gmai l.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,rang e(2,len(L)+1),1 ) #faculty

def __getitem__(sel f,i):
L = self.L
if not -1<i<self.n:
raise IndexError
def func(R):
Q = perm([R[j] for j in L],i)
for j,x in zip(L,Q):
R[j] = x
return func

def perm(L,m):
#permutation m of list L
res = []
T = L[::-1]
for i in range(len(L),0,-1):
res.append(T.po p(m%i))
m /= i
return res[::-1]

def cross(args):
#Raymond Hettinger's cross product function from ASPN
ans = [[]]
for arg in args:
ans = [x+[y] for x in ans for y in arg]
return ans

def find_sets_of_in dices_to_permut e(L):
set_by_letter = defaultdict(lis t)
for i, elem in enumerate(L):
if len(elem)>1:
set_by_letter[elem[0]].append(i)
return set_by_letter.v alues()

def test():
L = ['a', 'b', 'c1', 'd', 'e1', 'f', 'c2', 'x', 'e2']
I = find_sets_of_in dices_to_permut e(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__=='__ma in__':
test()