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

    Recursive Permutation Loop

    843789
      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();
                          finishedRoutes.add(input.clone());
                          min = sum;
                     }
                     else if(sum == min) {
                          finishedRoutes.add(input.clone());
                     }
                }
                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
          843789
          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
            843789
            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?
              843789
              Bump
              • 4. Re: Recursive Permutation Loop
                843789
                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) {
                      alistTry.add(iTry);
                      stack.removeElement(iTry);
                      alistTry.add(buildRoute(stack);
                      }
                
                   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?
                  843789
                  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?
                    843789
                    What's your code look like now?
                    • 7. Re: Any Ideas on Branching/Bounding?
                      843789
                      public void getRoute(int[] input, int n) {
                                sum = myMatrix.getCost(input);
                                if (n == 2) {
                                          nodes++;
                                          if(sum < min || min == 0) {
                                          finishedRoutes.clear();
                                          finishedRoutes.add(input.clone());
                                          min = sum;
                                     }
                                     else if(sum == min) {
                                          finishedRoutes.add(input.clone());
                                     }
                                }
                                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?
                        843789
                        ((sum >= min) && (min > 0))
                        ?
                        • 9. Re: Any Ideas on Branching/Bounding?
                          843789
                          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?
                            843789
                            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?
                              843789
                              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?
                                843789
                                            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?
                                  843789
                                  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?
                                    843789
                                    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