473,387 Members | 1,585 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,387 software developers and data experts.

Permutation over a list with selected elements

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 3119
we********@gmail.com <we********@gmail.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_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
Jun 20 '07 #2
On Jun 20, 12:37 pm, a...@mac.com (Alex Martelli) wrote:
weidong...@gmail.com <weidong...@gmail.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_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.

Jun 20 '07 #3
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 -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.pop(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_indices_to_permute(L):
set_by_letter = defaultdict(list)
for i, elem in enumerate(L):
if len(elem)>1:
set_by_letter[elem[0]].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 thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

5
by: radio | last post by:
I have a list box populated with some groups. All groups have a list of related offices; I have these in the following xml format: <Location>My Group 1</Location> <Location Group="My Group...
5
by: Nick Calladine | last post by:
Learning : Loop to list all dropdown box values on a form Can some one point me in the right direction : I have a form which I want to loop through I basically want to get all the selected...
10
by: Talin | last post by:
I'm sure I am not the first person to do this, but I wanted to share this: a generator which returns all permutations of a list: def permute( lst ): if len( lst ) == 1: yield lst else: head =...
3
by: Jack Middleton | last post by:
Hi! I'm lookin for a faster permutation algorithm for matrices. I know that it can be done with multiplying a matrix with a permutation matrix. It just seems a waste to iterate through all those...
1
by: user | last post by:
Hello I have Array of 50 ints. I want to receive random permutation, so in each int will be different number from 0-49. Is there any class for permutation ? Thanx Michal
6
by: Rajesh | last post by:
Hello Everybody, Can anybody help me in writing a C program to generate and print all possible combinations of n numbers. For eg. for 3 numbers(1,2,3) there turn out 3! combinations. (1,2,3),...
1
by: Christina | last post by:
Hi, I've been looking at some code for dependent list boxes to adapt to a State and City list. There will only be 2 states for the first list box, and 3 cities in the second list box. When the...
6
by: badcrusher10 | last post by:
Hello. I'm having trouble figuring out what to do and how to do.. could someone explain to me what I need to do in order to work? THIS IS WHAT I NEED TO DO: Professor Snoop wants a program...
7
by: xirowei | last post by:
Let's say i create a String array that store 4 Alphabets {"A","B","C","D"} How can i get the result if i need permutation of 4P3 and 4P2? I had refer to many examples from the internet, but...
0
by: Charles Arthur | last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
0
by: ryjfgjl | last post by:
If we have dozens or hundreds of excel to import into the database, if we use the excel import function provided by database editors such as navicat, it will be extremely tedious and time-consuming...
0
by: emmanuelkatto | last post by:
Hi All, I am Emmanuel katto from Uganda. I want to ask what challenges you've faced while migrating a website to cloud. Please let me know. Thanks! Emmanuel
0
BarryA
by: BarryA | last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
1
by: nemocccc | last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
0
by: Hystou | last post by:
There are some requirements for setting up RAID: 1. The motherboard and BIOS support RAID configuration. 2. The motherboard has 2 or more available SATA protocol SSD/HDD slots (including MSATA, M.2...
0
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However,...
0
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers,...
0
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.