Generate Permutations of array recurssive function.
Producing consecutive permutations.Need to develop a method that lists one by one all permutations of the numbers 1, 2, ? n (n is a positive integer).
(a) Recursive method . Given a verbal description of the algorithm listing all permutations one by one, you are supposed to develop a recursive method with the following header:
public static boolean nextPermutation(int[] array)
The method receives an integer array parameter which is a permutation of integers 1, 2, ? n. If there is 搉ext?permutation to the permutation represented by the array, then the method returns true and the array is changed so that it represents the 搉ext?permutation. If there is no 搉ext?permutation, the method returns false and does not change the array.
Here is a verbal description of the recursive algorithm you need to implement:
1. The first permutation is the permutation represented by the sequence (1, 2, ? n).
2. The last permutation is the permutation represented by the sequence (n, ? 2, 1).
3. If n a ,...,a 1 is an arbitrary permutation, then the 搉ext?permutation is produced by
the following procedure:
(i) If the maximal element of the array (which is n) is not in the first position of the array, say i n = a , where i > 1, then just swap i a and i-1 a . This will give you the 搉ext?permutation in this case.
(ii) If the maximal element of the array is in the first position, so 1 n = a , then to find
the 搉ext?permutation to the permutation ( ,..., ) 1 n a a , first find the 搉ext?br>permutation to ( ,..., ) 2 n a a , and then add 1 a to the end of thus obtained array of (n-1) elements.
(iii) Consecutively applying this algorithm to permutations starting from (1, 2, ? n),you will eventually list all n! possible permutations. The last one will be (n, ? 2, 1).For example, below is the sequence of permutations for n = 3 , listed by the described algorithm:
(0 1 2) ; (0 2 1) ; (2 0 1) ; (1 0 2) ; (1 2 0) ; (2 1 0)
Please help...i have done the iterative one..but unable to figure out the recursive..
Thank you in advance..
Please help
[2169 byte] By [
i.mogala] at [2007-10-2 18:26:46]
For each permutation a_1 a_2 ... a_n-1 of {1,2,...,n-1},form n others by inserting n in all possible places, obtaining:n a_1 a_2 ... a_n-1a_1 n a_2 ... a_n-1...a_1 a_2 ... n a_n-1a_1 a_2 ... a_n-1 n
Thanks for your reply...it would be great if a code is provided..i am try to do but this not working here is my code
// print N! permutation of the elements of array a (not in order)
public static boolean nextPermutation(int a[]) {
int N = a.length;
int[] t = new int[N];
/* for (int i = 0; i < N; i++)
t = a;*/
return(perm2(a, N));
}
private static boolean perm2(int [] a, int n) {
int i=n-1;
// start from last but 2
for (; i>0; i--) if (a<a[i+1]) break;
if (i ><0) return false;
for (int j = 0; j < n; j++) {
swap(a, j, n-1);
perm2(a, n-1);
// swap(a, j, n-1);
}
return true;
}
// swap the numbers at indices i and j
private static void swap(int[] a, int i, int j) {
int c;
c = a; a = a[j]; a[j] = c;
}
public static void main(String s[]){
int count=1;
// Initialize array
for(int i=0;i<num;i++){
a=i;
}
// call nextPermutation to generate possible permutations - recurssive method
for (int j=0; nextPermutation(a);j++){
count++; // Count number of records
// print the permutation array
for(int i=0;i<num;i++){
System.out.print(a);
}>
> Thanks for your reply...it would be great if a code> is provided..i am try to do but this not working> here is my codePlease use code-tags, see: http://forum.java.sun.com/help.jspa?sec=formattingNot working? Could you explain?
Thanks for your reply...it would be great if a code is provided..i am try to do but this not working here is my code
[/*
* Permutations.java
*
* Created on April 25, 2006, 12:42 PM
*
*/
package javaapplication1;
/**
*
* @author ismail
*/
public class Permutations {
// print N! permutation of the elements of array a (not in order)
public static boolean nextPermutation(int a[]) {
int N = a.length;
int[] t = new int[N];
/* for (int i = 0; i < N; i++)
t[i] = a[i];*/
return(perm2(a, N));
}
private static boolean perm2(int [] a, int n) {
int i=n-1;
// start from last but 2
for (; i>0; i--) if (a[i]<a[i+1]) break;
if (i ><0) return false;
for (int j = 0; j < n; j++) {
swap(a, j, n-1);
perm2(a, n-1);
// swap(a, j, n-1);
}
return true;
}
// swap the characters at indices i and j
private static void swap(int[] a, int i, int j) {
int c;
c = a[i]; a[i] = a[j]; a[j] = c;
}
private static final int num = 3; // number of elements to permutate
private static int [] a = new int[num]; // permutations array
private static int qkCounter = 0; // Counter for Quick sort
private static int mrgCounter = 0; // Counter for Merge sort
private static int qkSum = 0; // Total sum for Quick sort
private static int mrgSum = 0; // Total sum for Merge sort
public static void main(String s[]){
int count=1;
int [] qkArray = new int[num]; // Quick Sort array
int [] mrgArray = new int[num]; // Merge Sort array
int avgQuick = 0;
int avgMerge = 0;
// Initialize array
for(int i=0;i<num;i++){
a[i]=i;
}
// call nextPermutation to generate possible permutations - iterative method
for (int j=0; nextPermutation(a);j++){
count++; // Count number of records
// print the permutation array
for(int i=0;i<num;i++){
System.out.print(a[i]);
}
}
}
}
not working means-- it keeps on printing 012>
> not working means-- it keeps on printing 012
I find your code a bit hard to follow. So I didn't bother to decipher it. But here's some pseudo-ish code of the algorithm I posted earlier:
public static void permute(int[] oldArray, int n){
if(array.length < n) {
// create a new array (newArray) with a length of oldArray.length+1
// add an initial element in the first slot of the 'newArray' (this element is oldArray.length+1)
// fill the rest of the 'newArray' with the elements of 'oldArray'
// make a recursive call with the 'newArray'
// loop through the 'newArray' and swap elements at index
// 0 with 1, and permute that newly created array,
// swap 1 with 2, and permute that newly created array,
// ...
// (untill newArray.length-2 and newArray.length-1 indexes are swapped)
}
else {
// we found a permutation, print the array here
}
}
And call it like this:public static void main(String[] args) {
permute(new int[]{}, 4);
}
Good luck.
Thanks for you help...
but i am looking for exact code according to the verbal description of the algorithm given.
I will really appriciate you help....if you can give me some code help..
and also the function should return boolean, to see if there is any permutations left.
Thank you..please help
> Thanks for you help...
> but i am looking for exact code according to the
> verbal description of the algorithm given.
>
> I will really appriciate you help....if you can give
> me some code help..
> and also the function should return boolean,
> to see if there is any permutations left.
> Thank you..please help
Do your own work.
jverda at 2007-7-13 19:47:54 >
And please refer to this: http://forum.java.sun.com/thread.jspa?threadID=730654
