Results 1 to 10 of 10

# Thread: need help with backtracking

- 02-13-2010, 04:34 PM #1
## 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 } } } } }

silence i'm trying to meditate:p

- 02-17-2010, 11:04 AM #2
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

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 outputLast edited by Dumisan; 02-17-2010 at 12:12 PM.

silence i'm trying to meditate:p

- 02-17-2010, 12:08 PM #3Moderator
- Join Date
- Apr 2009
- Posts
- 13,541

- Rep Power
- 25

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.

- 02-17-2010, 12:18 PM #4
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 conditionssilence i'm trying to meditate:p

- 02-17-2010, 12:22 PM #5Moderator
- Join Date
- Apr 2009
- Posts
- 13,541

- Rep Power
- 25

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

- 02-17-2010, 12:23 PM #6Moderator
- Join Date
- Apr 2009
- Posts
- 13,541

- Rep Power
- 25

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

- 02-17-2010, 12:35 PM #7
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

silence i'm trying to meditate:p

- 02-17-2010, 12:43 PM #8Moderator
- Join Date
- Apr 2009
- Posts
- 13,541

- Rep Power
- 25

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.

- 02-17-2010, 12:45 PM #9
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

- 02-17-2010, 01:02 PM #10Moderator
- Join Date
- Apr 2009
- Posts
- 13,541

- Rep Power
- 25

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)

## Bookmarks