| Author | a little help , maybe | newbee
Member
Posts: 127
Location: India
Joined: 27.12.11
Rank: Active User
Warn Level: 20
| | so i found a piece of code on the web which finds out all the possible permutations of the elements of an integer array .
the code works fine , but the problem is , i can't make head or tail out of it .... would someone please analyze it and explain it to me ?
//code begins here
public class Permutation_N
{
void printArray(int []a)
{
for (int i = 0; i < a.length; i++)
{
System.out.print(a[i] + " ");
}
System.out.println("");
}
void permute(int []a,int k )
{
if(k == a.length)
printArray(a);
else
for (int i = k; i < a.length; i++)
{
int temp = a[k];
a[k] = a[i];
a[i] = temp;
permute(a,k+1);
temp = a[k];
a[k] = a[i];
a[i] = temp;
}
}
public static void main(String[] args)
{
Permutation_N obj = new Permutation_N();
int a[] = {1,2,3}; // enter any no. of integers here.
obj.permute(a,0);
}
}
Edited by korg on 06-07-13 07:02 |
 |
| Author | RE: a little help , maybe | newbee
Member
Posts: 127
Location: India
Joined: 27.12.11
Rank: Active User
Warn Level: 20
| | to be more specific , explain to me how the recursion part works , that's the place where i'm stuck at...
| |
|
| Author | RE: a little help , maybe | chokola
Member
Posts: 3
Location:
Joined: 16.07.13
Rank: Hacker Level 3 | | I'll try to explain it:
First, it seems the method needs to be called for k = 0 initially.
For k = 0, the method won't change anything, unless the length of the array is 0 (it would then print the array)
The method will now be called for the same array, but with k=1.
Now it only will try to get all possible permutations for the first two elements:
* Permutation 1: leave them the way they are
* Permutation 2: switch them
So for both possible permutations of the first two elements, we now do have an own recursive branch.
Now that we've seen, that things start correctly, let's see what the method does in a general step:
Suppose you've already got all permutations for the partial array from 0 to k-1 (each will have its own recursive branch)
Now you want to get all permutations for the partial array, which is longer by one.
To get all of those, you can now simply, for every permutation of the shorter array that you've got, consider every place that you could put your additional element a[k] in.
It could be at a[0], a[1], a[2].... so therefore, we're gonna switch it with any of them and all of those new, longer permutations will now get their own recursive branch.
Finally, when the method gets called for k=a.length, this means that we already have all permutations of a[0],a[1],...,a[a.length-1], which is the whole array. So we're finished and can print what we've got | |
|
|
Main:
