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. 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 substeps:
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
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 substeps:
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. 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() This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
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...

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...

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 =...

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...

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 049.
Is there any class for permutation ?
Thanx
Michal

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),...

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...

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...

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...

by: Charles Arthur 
last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone

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 timeconsuming...

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

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...

by: nemocccc 
last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?

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...

by: marktang 
last post by:
ONU (Optical Network Unit) is one of the key components for providing highspeed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However,...

by: Oralloy 
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bitfields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers,...

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...
 