11 Replies Latest reply: Apr 4, 2009 1:27 PM by 807588 RSS

    skipping to a specific place in a recursive function

    807588
      I wrote a recursive function that recurses Adding times, then calls go (). The entire function will call go () billions of times. When I call this function, I want to only run go () 5,000,000 times. It should run the first 5,000,000 go's if the Part variable is set to 1, the 2nd 5,000,000 go's if Part is 2, etc. The bolded code below is my attempt at implementing this. This code runs the correct 5,000,000-part pieces, but it takes too long because it is still recursing through every part, it's just not calling go () for the other ones. How can I only run the specific piece without recursing through all of the other ones?
      Add (int X, int Y, int Adding)
      {
        int Tile;
        while (Y < 12)
        {
          while (X < 16)
          {
            if (aRoom [nRoom] [Y] [X] == 0)
            {
              Changes [Adding - 1] [1] = X;
              Changes [Adding - 1] [2] = Y;
              for (Tile = 0; aTiles [nRoom] [Tile] [0] != 0; Tile++)
              {
                if (aTiles [nRoom] [Tile] [1] > 0)
                {
                  aTiles [nRoom] [Tile] [1]--;
                  aRoom [nRoom] [Y] [X] = aTiles [nRoom] [Tile] [0];
                  Changes [Adding - 1] [0] = aTiles [nRoom] [Tile] [0];
                  if (Adding > 1)
                  {
                    Add (X + 1, Y, Adding - 1);
                  }
                  else
                  {
      PartTests++;
      if (Part == 0 || Part == Parts)
      *{*
      go ();
      *}*
      if (PartTests == 5000000)
      *{*
      Parts++;
      PartTests = 0;
      *}*
                  }
                  aTiles [nRoom] [Tile] [1]++;
                }
              }
              aRoom [nRoom] [Y] [X] = 0;
            }
            X++;
          }
          X = 0;
          Y++;
        }
      }
        • 1. Re: skipping to a specific place in a recursive function
          jwenting
          there is no goto in Java.
          • 2. Re: skipping to a specific place in a recursive function
            807588
            I don't think the question is clear enough. Can you elaborate a bit more? At first glance, I believe the solution should just involve the adding of some extra conditions.
            • 3. Re: skipping to a specific place in a recursive function
              807588
              what go()?

              here's a cleaned up version of the code ( not a soln. ):
              Add( int X, int Y, int Adding )
              {
                   int Tile;
                   
                   while ( Y < 12 )
                   {
                        while ( X < 16 )
                        {
                             if ( aRoom [nRoom][Y][X] == 0 )
                             {
                                  Changes[Adding - 1][1] = X;
                                  Changes[Adding - 1][2] = Y;
                                  
                                  for ( Tile = 0; aTiles [nRoom][Tile][0] != 0; Tile++ )
                                  {
                                       if ( aTiles[nRoom][Tile][1] > 0 )
                                       {
                                            aTiles[nRoom][Tile][1]--;
                                            aRoom[nRoom][Y][X] = aTiles [nRoom] [Tile] [0];
                                            Changes[Adding - 1][0] = aTiles[nRoom][Tile][0];
                                            
                                            if ( Adding > 1 )
                                            {
                                                 Add ( X + 1, Y, Adding-1 );
                                            }
                                            else
                                            {
                                                 PartTests++;
                                                 if ( Part == 0 || Part == Parts )
                                                 {
                                                      go();
                                                 }
                                                 if ( PartTests == 5000000 )
                                                 {
                                                      Parts++;
                                                      PartTests = 0;
                                                 }
                                            }
                                            
                                            aTiles[nRoom][Tile][1]++;
              
                                       } // end of if
                                  } // end of for
                             
                                  aRoom[nRoom][Y][X] = 0;
              
                             } // end of if
                             
                             X++;
              
                        } // end of inner while
                        
                        X = 0;
                        Y++;
              
                   } // end of outer while
              }
              Edited by: scphan on Apr 4, 2009 1:13 PM
              • 4. Re: skipping to a specific place in a recursive function
                807588
                can you give a more elaborate explanation on what go() does?
                • 5. Re: skipping to a specific place in a recursive function
                  807588
                  I'm sorry it wasn't clear. I'll try to explain better:

                  I have a recursive method that creates permutations on a grid like:

                  A0000
                  B0000
                  C0000
                  D0000

                  0A000
                  0B000
                  0C000
                  0D000

                  [...]

                  AA000
                  AB000
                  AC000
                  AD000

                  [...]

                  DDDDA
                  DDDDB
                  DDDDC
                  DDDDD

                  Except there are some rules like A can only be used twice, so while BBB00 is acceptable, AA00A is not.

                  I want to code a function that will take a number as a parameter and will calculate what the permutation would be after that many permutations.

                  Meaning:
                  f(1) returns A0000
                  f(2) returns B0000
                  f(3) returns C0000
                  f(4) returns D0000
                  f(5) returns 0A000
                  f(6) returns 0B000
                  f(7) returns 0C000
                  f(8) returns 0D000
                  etc.

                  How can I do this without recursing through every combination?
                  • 6. Re: skipping to a specific place in a recursive function
                    807588
                    so you want to stop it when it finds the correct combination? like a 'break' to the loop?

                    this is kinda reminding me of those numbers at the gasoline pump except maybe backwards

                    is there some specification of how the permutation will proceed?

                    Edited by: scphan on Apr 4, 2009 1:55 PM
                    • 7. Re: skipping to a specific place in a recursive function
                      807588
                      I don't want it to loop at all. I want it to return what the nth permutation would be, without actually going through the previous permutations.
                      • 8. Re: skipping to a specific place in a recursive function
                        DarrylBurke
                        Why the new account for every post?
                        • 9. Re: skipping to a specific place in a recursive function
                          807588
                          00000
                          A0000
                          B0000
                          C0000
                          D0000
                          0A000
                          AA000
                          BA000
                          CA000
                          DA000
                          0B000
                          AB000
                          BB000
                          CB000
                          DB000
                          0C000
                          AC000
                          BC000
                          CC000
                          DC000
                          0D000
                          AD000
                          BD000
                          CD000
                          DD000
                          00A00
                          A0A00
                          B0A00
                          C0A00
                          D0A00
                          0AA00
                          AAA00
                          ...

                          like this?

                          well then you need to know the order of the permutations, the one you give an example of earlier?
                          is there a certain permutation for the nth permutation?

                          Edited by: scphan on Apr 4, 2009 2:02 PM

                          Edited by: scphan on Apr 4, 2009 2:05 PM
                          • 10. Re: skipping to a specific place in a recursive function
                            807588
                            DarrylBurke wrote:
                            Why the new account for every post?
                            i agree, how very ominous
                            • 11. Re: skipping to a specific place in a recursive function
                              807588
                              You may be able to improve the performance of your algorithm to avoid some looping but I don't think you can get rid of it completely. As one of the previous posters mentioned, you can use the "break" statement in your logic.