Follow us on Twitter!
Become the change you seek in the world. - Gandhi
Thursday, April 17, 2014
Navigation
Home
HellBoundHackers Main:
HellBoundHackers Find:
HellBoundHackers Information:
Learn
Communicate
Submit
Shop
Challenges
HellBoundHackers Exploit:
HellBoundHackers Programming:
HellBoundHackers Think:
HellBoundHackers Track:
HellBoundHackers Patch:
HellBoundHackers Other:
HellBoundHackers Need Help?
Other
Members Online
Total Online: 13
Guests Online: 12
Members Online: 1

Registered Members: 82813
Newest Member: VesuviusSentinel
Latest Articles
View Thread

HellBound Hackers | Computer General | Programming

Author

a little help , maybe

newbee
Member



Posts: 127
Location: India
Joined: 27.12.11
Rank:
Active User
Warn Level: 20
Posted on 06-07-13 06:24
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
Posted on 08-07-13 10:51
to be more specific , explain to me how the recursion part works , that's the place where i'm stuck at...


www.hellboundhackers.org/sig/r/64440.png
i1078.photobucket.com/albums/w488/ads99nrg/signature.png

Author

RE: a little help , maybe

chokola
Member



Posts: 3
Location:
Joined: 16.07.13
Rank:
Hacker Level 3
Posted on 28-07-13 07:40
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