Hi, I'm testing a script and I ran into a persistent error. The output of the program should be:

123
132
312
321
231
213

However, I just get a stack overflow error. I'm a bit lost as to what isn't running correctly.

CODE:

import java.util.Arrays;

public class RecursionTest {
    private static void permute(String prefix, int[] s) {
        N = s.length;
        if (N == 0) {
            System.out.println(prefix);
        } else {
            for (int i = 0; i < N; i++) {
                permute(prefix + s[i], Arrays.copyOfRange(s, 0, N));
            } /end for loop/ } /end if loop/}

public static int N=0;
public static void permute(int[] s) { permute("", s); } //initial call
      public static void main(String[] args) {
        N = Integer.parseInt(args[0]);
        int[] elements = {1,2,3};
        permute(elements);
        System.out.println(); }//end main method
} //end RecursionTest class

Edited 3 Years Ago by Nick Evan: Fixed formatting

Arrays.copyOfRange(s, 0, N)
returns the array as it is. you're not changing it, so you're continously calling the method with the same input, and the same result

I just rechecked something:
for (int i = 0; i < N; i++) {
System.out.println(i + " - " + N + " s == " + s.length);
permute(prefix + s[i], Arrays.copyOfRange(s, 0, N));
}

add this print statement to your code, and you'll not only see where you create that stackoverflow problem,but you'll also see a logical problem with your for-loop.

I implemented some changes and the debug code you suggested. The error went away and the program stops.
I still haven't sorted everything out though, I think the loop is causing things to be reset while also the scope of variables hasn't been set right. I guess I find that aspect of recursion confusing. Any advice?

public class RecursionTest {
static int i=0;
    private static void permute(String prefix, int[] s) {
        i++;
        N = s.length;
        if (N == 0) {
            System.out.println(prefix);
        } else {
            for ( ; i < s.length; ) {
                System.out.println(i + "-" + N + " s==" + s.length); //debug code
                permute(prefix + s[i], Arrays.copyOfRange(s, i, N));
            } /*
             * end for loop
             */ } /*
         * end if loop
         */
    }

Edited 4 Years Ago by pyTony: Use code tags

I think you're making it way too hard for yourself:

static boolean repeat = true;

private static void sort(int[]s, int elToMove){
while(repeat){
    printArray(s);        
    s = getShiftedS(s, elToMove);        
    if ( checkEqualArrays(s)){
        repeat = false;
     //   printArray(s); add this line if you want the original value to be printed again
    }
    if ( repeat&& elToMove == s[0])
        sort(s, s[s.length-1]);      
}
}

private static void printArray(int[] toPrint){
for ( int i : toPrint)
    System.out.print("" + i);
System.out.println();
}

private static boolean checkEqualArrays(int[] array){
for ( int i = 0; i < array.length; i++){
    if ( array[i] != original[i])
        return false;
}
return true;
}

private static int[] getShiftedS(int[] s, int elToMove){
int[] row = s;
int loc = 0;
for ( int i = 0; i < row.length; i++){
    if ( row[i] == elToMove){
        loc = i;
        break;
    }
}
if ( loc != 0 ){
    row[loc] += row[loc-1];
    row[loc-1] = row[loc] - row[loc-1];
    row[loc] = row[loc] - row[loc-1];
}
return row;
}

static int[] original = {1,2,3};
static int[] toSort;

public static void main(String[] args){
toSort = new int[original.length];
for ( int i = 0; i < original.length; i++){
    toSort[i] = original[i];
}
sort(toSort, toSort[toSort.length-1]);
}

and sure this can be done better. up to you to improve it

Edited 4 Years Ago by stultuske: old code tags were easier :)

This article has been dead for over six months. Start a new discussion instead.