CODEWITHSUNDEEP
javaalgorithmrecursion
Amosa
Amosa

Reputation: 73

Recursive permutation function not returning correct ArrayList in Java

I am trying to create a permutation of given string array. 

public static ArrayList<String[]> permutate(String[] str) {
    return permutate( str, 0, str.length -1, null );
}

public static ArrayList<String[]> permutate(String[] str, int curr, int stop, ArrayList<String[]> result) {
    if(result == null) {
        result = new ArrayList<String[]>();
    }
    if(curr == stop) {
        result.add(str);
        System.out.println(Arrays.toString(str));
        return result;
    }
    else {
        for(int j = curr; j <= stop ; j++) {
            //swap str[j] and str[curr]
            String tmp = str[j];
            str[j] = str[curr];
            str[curr] = tmp;

            permutate(str, curr+1, stop, result);

            //swap str[j] and str[curr]
            tmp = str[j];
            str[j] = str[curr];
            str[curr] = tmp;
        }           
        return result;
    }
}

In Main

    String[] str = {"A","B","C"};

    System.out.println("Inside the recursion:");
    result = permutate(str);
    System.out.println("Permutation result:");
    for(String[] arr: result){
        System.out.println(Arrays.toString(arr));
    }

This is the out put from running in main.

Inside the recursion:
[A, B, C]
[A, C, B]
[B, A, C]
[B, C, A]
[C, B, A]
[C, A, B]
Permutation result:
[A, B, C]
[A, B, C]
[A, B, C]
[A, B, C]
[A, B, C]
[A, B, C]

What is weird is that it's printing the right permutation in the recursive function itself. But, it's not returning the right ArrayList.

Upvotes: 0

Views: 76

Answers (1)

Luigi Cortese
Luigi Cortese

Reputation: 11121

You're always modifying the same object, change your code to this

    if(curr == stop) {
        String[] dest = new String[str.length];
        System.arraycopy( str, 0, dest, 0, str.length );
        result.add(dest);

        System.out.println(Arrays.toString(str));
        return result;
    }

By doing 

    result.add(str);

you're filling your result object with references to the same object.

In fact, if you change you inner println from this

    System.out.println(Arrays.toString(str));

to this 

    for(String[] arr: result)
        System.out.println(Arrays.toString(arr));

you'll get this output

    [A, B, C]

    [A, C, B]
    [A, C, B]

    [B, A, C]
    [B, A, C]
    [B, A, C]

    [B, C, A]
    [B, C, A]
    [B, C, A]
    [B, C, A]

    [C, B, A]
    [C, B, A]
    [C, B, A]
    [C, B, A]
    [C, B, A]

    [C, A, B]
    [C, A, B]
    [C, A, B]
    [C, A, B]
    [C, A, B]
    [C, A, B]

showing that, at every loop, your result array elements are always the same

Upvotes: 2

Related Questions