Permutation of a string
Moderator: Board moderators

 New poster
 Posts: 9
 Joined: Wed Apr 02, 2003 10:28 am
Permutation of a string
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
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

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

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

 Experienced poster
 Posts: 202
 Joined: Fri Mar 22, 2002 2:00 am
 Location: Chittagong. CSE  CUET
 Contact:
Re: Permutation of a string
Can you explain what you are really looking for ???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
We are all in a circular way, no advances, only moving and moving!

 New poster
 Posts: 32
 Joined: Thu Jul 31, 2003 6:21 am
 Location: Daffodil Univ, Bangladesh
 Contact:
Hy I think you wanted like this
Code: Select all
Input:
ab
Output:
ab
ba
Code: Select all
Input:
ba
Output:
ba
ab
The algorithm must be very efficient.
Hate WA
Visit phpBB!
Visit phpBB!

 Experienced poster
 Posts: 114
 Joined: Wed Jul 30, 2003 10:30 pm
 Location: Newfoundland, Canada (St. John's)
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.length1];
for(int i = 0; i < pos; i++) tmp = arr;
for(int i = pos+1; i < arr.length; i++) tmp[i1] = 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!!
[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.length1];
for(int i = 0; i < pos; i++) tmp = arr;
for(int i = pos+1; i < arr.length; i++) tmp[i1] = 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!!

 Learning poster
 Posts: 60
 Joined: Tue Aug 13, 2002 2:39 am
 Location: Mexico
I think
I think the recursive approach is nice because lets you make permutations of n elements taken r at time in a very easy way.
Miguel & Marina

 Experienced poster
 Posts: 202
 Joined: Fri Mar 22, 2002 2:00 am
 Location: Chittagong. CSE  CUET
 Contact:
Re: I think
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 ???
We are all in a circular way, no advances, only moving and moving!

 Experienced poster
 Posts: 114
 Joined: Wed Jul 30, 2003 10:30 pm
 Location: Newfoundland, Canada (St. John's)
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).
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).