Results 1 to 10 of 10
  1. #1
    Dumisan's Avatar
    Dumisan is offline Member
    Join Date
    Feb 2010
    Location
    Romania
    Posts
    30
    Rep Power
    0

    Default need help with backtracking

    Hi
    i have beed studying algorithms for some time but in teoretics so i decided to implement a beacktracking algorithm to generate some permutations though i respected all the instruactions my cod is not working proper :confused:
    here is the cod i wrote
    Java Code:
    public class permutation_bktr {
        public static void main(String args[]) {
          System.out.println("give n");
          java.util.Scanner in = new java.util.Scanner(System.in);
          int n = in.nextInt();
          in.close();
          int sp=1; 
          int [] x = new int[n];
          int k = 0;
          x[1] = 0;
    
          while (k>=0) {
          x[k] = x[k] + 1 ;
          if(x[k]>n) k-=1;
          else {
              for(int i=0;i<k-1;i++)
              if(x[i]==x[k]) sp=0;
              else sp=1;
              if(sp==1)
                if(k==n)
              for(int i=0;i<k;i++ ) {
              System.out.print(x[i]);              
             System.out.println();     }
               else {
                k+=1;
                x[k] = 0;  //not sure why but i get the out of bound exception here
          }
          }
         }
    
     }
    }
    if someones knows what;s wrong help plz
    silence i'm trying to meditate:p

  2. #2
    Dumisan's Avatar
    Dumisan is offline Member
    Join Date
    Feb 2010
    Location
    Romania
    Posts
    30
    Rep Power
    0

    Default

    i have been thinking of this and i have found the mistake that give the out of bound exception
    well the algorithm saies that k values is the first position of the array wich is 0 in java so in stand of x[1] = 0 it should be x[0] = 0 becous x[o] is the first element of the java array ....
    the secound mistake is the while condition becous it sdould stop when there are no more values that can be added in the first array position and the result to be a valid solution so it should be while(k>0) becous when k==0 it's the end condition....

    the coud is like this

    Java Code:
    public class permutari_bktr {
        public static void main(String args[]) {
          System.out.println("give n");
          java.util.Scanner in = new java.util.Scanner(System.in);
          int n = in.nextInt();
          in.close();
          int sp=1; 
          int [] x = new int[n];
          int k = 0;
          x[0] = 0;
    
          while (k>0) {      //here is the while 
          x[k] = x[k] + 1 ;
          if(x[k]>n) k=k-1;
          else {
              for(int i=0;i<k-1;i++)
              if(x[i]==x[k]) sp=0;
              else sp=1;
              if(sp==1) {
                if(k==n) {
              for(int i=0;i<k;i++ ) {
              System.out.print(x[i]);              
             System.out.println();     } //end of the for
                } // if (k==n)
               else {
                k+=1;
                x[k] = 0;  
          } // else from if(k==n)     
              } //if(sp==1)
          } // else from if(x[k]==n)
         } //end of the while
     } //end of main
    } // end of class
    but now i get a new problem:
    the cod compile and startes but after reading the array length it stopes with build successful with no output :confused:

    someone have an ideea why there is no output
    Last edited by Dumisan; 02-17-2010 at 12:12 PM.
    silence i'm trying to meditate:p

  3. #3
    Tolls is offline Moderator
    Join Date
    Apr 2009
    Posts
    11,450
    Rep Power
    19

    Default

    Your comments say there's a while loop, but I can't see one.
    Also, you really must indent properly...lack of decent indentation makes code-flow almost impossible to see.
    Also also, use brackets even for single lined if statements, or controls. It makes sure you don't miss something simple.

  4. #4
    Dumisan's Avatar
    Dumisan is offline Member
    Join Date
    Feb 2010
    Location
    Romania
    Posts
    30
    Rep Power
    0

    Default

    i have marked the while
    about the indent well it should work like that but is not :(
    now i'm remacking the code based on the backtracking general implementation to see if somehow i missed something on the conditions
    silence i'm trying to meditate:p

  5. #5
    Tolls is offline Moderator
    Join Date
    Apr 2009
    Posts
    11,450
    Rep Power
    19

    Default

    If you're using netbeans then Shift-Alt-F to format it.

  6. #6
    Tolls is offline Moderator
    Join Date
    Apr 2009
    Posts
    11,450
    Rep Power
    19

    Default

    That code will never go into the while:

    Java Code:
          [B]int k = 0;[/B]
          x[0] = 0;
    
          while ([B]k>0[/B]) {      //here is the while

  7. #7
    Dumisan's Avatar
    Dumisan is offline Member
    Join Date
    Feb 2010
    Location
    Romania
    Posts
    30
    Rep Power
    0

    Default

    ok so here is the cod formated and with the while conditon modified

    Java Code:
    public class permutari_bktr {
        public static void main(String args[]) {
            System.out.println("give n");
            java.util.Scanner in = new java.util.Scanner(System.in);
            int n = in.nextInt();
            in.close();
            int sp = 1;
            int[] x = new int[n];
            int k = 0;
            x[0] = 0;
            while (k >= 0) {
                x[k] = x[k] + 1;
                if (x[k] > n) {
                    k = k - 1;
                } else {
                    for (int i = 0; i < k - 1; i++) {
                        if (x[i] == x[k]) {
                            sp = 0;
                        } else {
                            sp = 1;
                        }
                    }
                    if (sp == 1) {
                        if (k == n) {
                            for (int i = 0; i < k; i++) {
                                System.out.print(x[i]);
                                System.out.println();
                            } //end of the for
                        } // if (k==n)
                        else {
                            k += 1;
                            x[k] = 0;  //i got a ArrayIndexOutOfBoundsException here 
                        } // else from if(k==n)
                    } //if(sp==1)
                } // else from if(x[k]==n)
            } //end of the while
        } //end of main
    } // end of class
    it's like my first post it's the same cod
    silence i'm trying to meditate:p

  8. #8
    Tolls is offline Moderator
    Join Date
    Apr 2009
    Posts
    11,450
    Rep Power
    19

    Default

    The exception will tell you what index you're attempting to read.
    You can then compare that number to the number you entered...and possibly spot why it's going wrong.

  9. #9
    Dumisan's Avatar
    Dumisan is offline Member
    Join Date
    Feb 2010
    Location
    Romania
    Posts
    30
    Rep Power
    0

    Default

    run:
    give n
    4
    Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 4
    at learn.permutari_bktr.main(permutari_bktr.java:42)
    Java Result: 1
    BUILD SUCCESSFUL (total time: 6 seconds)
    silence i'm trying to meditate:p

  10. #10
    Tolls is offline Moderator
    Join Date
    Apr 2009
    Posts
    11,450
    Rep Power
    19

    Default

    OK, so going through this bit:

    Java Code:
                        if (k == n) {
                            for (int i = 0; i < k; i++) {
                                System.out.print(x[i]);
                                System.out.println();
                            } //end of the for
                        } // if (k==n)
                        else {
                            k += 1;
                            x[k] = 0;  //i got a ArrayIndexOutOfBoundsException here 
                        } // else from if(k==n)
    What happens when you get to this code with k = 3?

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •