need help with backtracking

[Dumisan]

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

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

[Dumisan]

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

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

[Tolls]

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.

[Dumisan]

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

[Tolls]

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

[Tolls]

That code will never go into the while:

      [B]int k = 0;[/B]
      x[0] = 0;

      while ([B]k>0[/B]) {      //here is the while

[Dumisan]

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

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

[Tolls]

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.

[Dumisan]

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)

[Tolls]

OK, so going through this bit:

                    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?