14 Replies Latest reply: Mar 4, 2010 4:55 PM by 843789

# Recursive Permutation Loop

I'm working on a function to obtain all permutations of an array, except for the first value (0). Currently, it succeeds in finding all the permutations, but does far to many. I can't seem to figure out what I'm doing wrong. This method also will use bound techniques to minimize the amount of recursive processes. Would appreciate any help!
``````public void getRoute(int[] input, int n) {
nodes++;
sum = myMatrix.getCost(input);
if (n == 1) {
if(sum < min || min == 0) {
finishedRoutes.clear();
min = sum;
}
else if(sum == min) {
}
}
else {
for (int i = 1; i < n; i++) {
swap(input, i, n-1);
sum = myMatrix.getCost(input);
//if(sum <= min || min == 0) {
getRoute(input, n-1);
swap(input, i, n-1);
}
//}
}
}

private void swap(int[] input, int i, int j) {
int temp = input;
input[i] = input[j];
input[j] = temp;
}                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                ``````
• ###### 1. Re: Recursive Permutation Loop
jordan.haber wrote:
Would appreciate any help!
I note that when i is 1 and n is 2 then the same array element will be swapped meaning nothing happens.

Couldn't this have the effect that the array is saved twice with the same content somehow?

Maybe you should save the array when

if (n == 2)
• ###### 2. Re: Recursive Permutation Loop
Great that helped! Its still working and the number of permutations are brought down. They still are above the amount needed however. Any other ideas?

On another note, any idea how I can implement the commented out part of the code? I've been trying to add it, but I keep cutting the permutations too short.

Edited by: jordan.haber on Mar 4, 2010 8:43 AM
• ###### 3. Anyone?
Bump
• ###### 4. Re: Recursive Permutation Loop
Rather than swapping values, have you considered using a pool / stack of unused elements...
This code isn't exact just a rough idea you could flesh out on your own.
``````public ArrayList<int> buildRoute(ArrayList<int> stack) {

ArrayList<int> alistTry = new ArrayList<int>();

for (int iTry : stack) {
stack.removeElement(iTry);
}

return alistTry;
}``````
Edited by: porpoisepower on Mar 4, 2010 10:37 AM
Sorry! Naming an int "try" is bad on many, many levels.
• ###### 5. Any Ideas on Branching/Bounding?
Ok, I got the permutations section working. Now my problem is I need to implement some sort of bounding technique to backtrack if the values are already higher than those previously calculated. I can't figure out how or where to add it. What I am trying to add in is the commented out section in the beginning of the code. Ideas would be greatly appreciated, I'm trying to leave it in an int[] and keep the original code I am using.
• ###### 6. Re: Any Ideas on Branching/Bounding?
What's your code look like now?
• ###### 7. Re: Any Ideas on Branching/Bounding?
``````public void getRoute(int[] input, int n) {
sum = myMatrix.getCost(input);
if (n == 2) {
nodes++;
if(sum < min || min == 0) {
finishedRoutes.clear();
min = sum;
}
else if(sum == min) {
}
}
else {
for (int i = 1; i < n; i++) {
//if(sum >= min && min > 0) { backtrack here }

swap(input, i, n-1);
getRoute(input, n-1);
swap(input, i, n-1);
}
}
}``````
• ###### 8. Re: Any Ideas on Branching/Bounding?
``((sum >= min) && (min > 0))``
?
• ###### 9. Re: Any Ideas on Branching/Bounding?
Sorry, let me clarify.

Its not the if statement itself that I am having trouble with, it is where to place it, and what variables to change in order to have the loop skip to the next permutation. However, maybe this isn't possible recursively as you need that permutation to create the next?
• ###### 10. Re: Any Ideas on Branching/Bounding?
I think I understand what your doing now, feel free to correct me, I can't see the definitions for myMatrix(etc)...

if sum(your current cost or route?) is bigger than the current minimum cost of route, you want to stop the permutation thread?
• ###### 11. Re: Any Ideas on Branching/Bounding?
Exactly. I want to speed up the algorithm by essentially skipping any permutations that already have a higher cost than the minimum calculated route. This is part of a traveling salesman problem.

Edited by: jordan.haber on Mar 4, 2010 12:16 PM
• ###### 12. Re: Any Ideas on Branching/Bounding?
``````            for (int i = 1; i < n; i++) {
if (sum < min) {
swap(input, i, n-1);
getRoute(input, n-1);
swap(input, i, n-1);
}
else {
break;
}``````
Edited by: porpoisepower on Mar 4, 2010 12:27 PM
• ###### 13. Re: Any Ideas on Branching/Bounding?
Hm, I see where you are going with that. The problem is, it now only goes through the first two cycles (two nodes).
How could it be changed to allow for the continuation of the method - permuting the others that come later - but only ending that single node development short?
Maybe this won't work the way the permutation generator is set up.
• ###### 14. Re: Any Ideas on Branching/Bounding?
Have tried playing with the sample data?

Also a while loop may be preferable to the for loop. Using break is valid but not pretty.

What are using for a development environment? A text editor or something you can run in debug and watch your variables? Not that you can't thrown in lots of system.out commands to print values at any given moment, but watches are alot easier :D