Permutation of a string

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
Syed Mubashshir Husain
New poster
Posts: 9
Joined: Wed Apr 02, 2003 10:28 am

Permutation of a string

Post by Syed Mubashshir Husain »

Hello everyone

Is there any algo to permutate a string?
It must be efficient.

please give me the algo or site where i can get me requirement.


-------
SMH

Joseph Kurniawan
Experienced poster
Posts: 136
Joined: Tue Apr 01, 2003 6:59 am
Location: Jakarta, Indonesia

Post by Joseph Kurniawan »

I've heard of an algo called SEPA algo. People solve prob 10098 using this algo. But I don't know for sure what that is. :oops: :oops:

bugzpodder
Experienced poster
Posts: 147
Joined: Fri Jun 13, 2003 10:46 pm

Post by bugzpodder »

google would be fine. some problems in the set uses Knuth's permutation: insert the next element every possible place and recurse.

Moni
Experienced poster
Posts: 202
Joined: Fri Mar 22, 2002 2:00 am
Location: Chittagong. CSE - CUET
Contact:

Re: Permutation of a string

Post by Moni »

Syed Mubashshir Husain wrote:Hello everyone

Is there any algo to permutate a string?
It must be efficient.

please give me the algo or site where i can get me requirement.


-------
SMH
Can you explain what you are really looking for ???
ImageWe are all in a circular way, no advances, only moving and moving!

Jewel of DIU
New poster
Posts: 32
Joined: Thu Jul 31, 2003 6:21 am
Location: Daffodil Univ, Bangladesh
Contact:

Post by Jewel of DIU »

:lol:

Hy I think you wanted like this

Code: Select all

Input:
ab
Output:
ab
ba

Code: Select all

Input:
ba
Output:
ba
ab
I also need this kind of permutation to solve "Titans in danger"-P.no: 10395
The algorithm must be very efficient.
Hate WA
Visit phpBB!

Moni
Experienced poster
Posts: 202
Joined: Fri Mar 22, 2002 2:00 am
Location: Chittagong. CSE - CUET
Contact:

Post by Moni »

Why don't you try to use STL ???

with it's:


[cpp]

include<algorithm>

next_permutation()

[/cpp]

Isn't it better for use?

But if you wanna know the algorithm you have to go through the books!

What I use is a recursive approach!
ImageWe are all in a circular way, no advances, only moving and moving!

xbeanx
Experienced poster
Posts: 114
Joined: Wed Jul 30, 2003 10:30 pm
Location: Newfoundland, Canada (St. John's)

Post by xbeanx »

Here's a couple of functions I used.

[java] static int[] numberToPermutation(int value, int size) {
int[] permutationSet = new int[size];
int[] offsets = new int[size];

int nperms = 0, noffsets = 0;
int remainder = value, curSize = size, segment;
for(int i = 0; i < size; i++) offsets = i;
while(curSize-- > 1) {
segment = (remainder / factorial(curSize)) % size;
permutationSet[nperms++] = offsets[segment];
offsets = removeElement(segment, offsets);
remainder = remainder % factorial(curSize);
}
permutationSet[nperms++] = offsets[0];
return permutationSet;
}

static int[] removeElement(int pos, int[] arr) {
int[] tmp = new int[arr.length-1];
for(int i = 0; i < pos; i++) tmp = arr;
for(int i = pos+1; i < arr.length; i++) tmp[i-1] = arr;
return tmp;
}

static int factorial(int n)
{int r=n;while(--n>0)r*=n;return r;}[/java]

This is how you use it:

Say you have an array of n objects and you want to permute this array.

[java]int nperms = factorial(n);
for(int i = 0; i < nperms; i++) {
int[] perm = numberToPermutation(i, n);
for(int j = 0; j < n; j++)
array[j] = origArr[perm[j]];
}[/java]

Where origArr is the original ordering array. Its pretty fast. Recursive permutation is slow.

One advantage of this is you don't have to sort the original array (as you must with STL). So if the problem asks for output in the order it appears in input, you're good!!

Miguel Angel
Learning poster
Posts: 60
Joined: Tue Aug 13, 2002 2:39 am
Location: Mexico

I think

Post by Miguel Angel »

I think the recursive approach is nice because lets you make permutations of n elements taken r at time in a very easy way.
:D Miguel & Marina :D

Moni
Experienced poster
Posts: 202
Joined: Fri Mar 22, 2002 2:00 am
Location: Chittagong. CSE - CUET
Contact:

Re: I think

Post by Moni »

Miguel Angel wrote:I think the recursive approach is nice because lets you make permutations of n elements taken r at time in a very easy way.

Hmm... but it will take time than the iterative one!

And I am not sure how the STL's permutations is implemented :(

Can anyone know about "Combination" library ???
ImageWe are all in a circular way, no advances, only moving and moving!

xbeanx
Experienced poster
Posts: 114
Joined: Wed Jul 30, 2003 10:30 pm
Location: Newfoundland, Canada (St. John's)

Post by xbeanx »

The thing about doing it recursively, is if you have a collection of Objects or classes that you want permuted, each time you recurse these classes must be stored.

If using something like C you won't notice too much of a difference. But in some situations (like JAVA or C++) you can notice a huge difference even when working with small numbers (such as n=5).

But the recursive solution is very intuitive. Unlike the one I presented here (which, I may add, I do not fully understand).

Post Reply

Return to “Algorithms”