CODEWITHSUNDEEP
javarecursionpass-by-referencecombinationspermutation
user2659201
user2659201

Reputation: 1

Pass-by-reference behaviour recursion in Java: Combinations and permutations of strings

I have been working on a recursive function in java to output all the the combinations of a string where repetition is not allowed ('c'letter output all combinations choosing 'e' letters). I have been having trouble with arrays and vectors returning to the state they were in before the recursive call. It's almost as if everything was being passed by reference (this could be what's happening: I'm not sure how to get past it I am more used to programming in C++ than Java).

Here is my Java code:

void calcCombNoRep(Vector c, String[] e){
    if(isFull(e)){
        output(e);
        return;          
    }
    for (int i = 0; i < c.capacity(); ++i){
        e[getNextInd(e)] = (String)c.remove(i);
        calcCombNoRep(c,e);
    }
}

Here is how it is working from the debug window (all called functions like output() etc. seem to work fine):

Initial Call: c = [a b c d]; e = [ _ _ ]

Recursive Call 1: c = [b c d]; e = [a _ ]

Recursive Call 2: c = [c d]; e = [a b]

RETURN

After return: c = [c d]; e = [a b]

Then we get a collision in the array, because I am trying to put a value in the array at index 1 where the b is.

How it should work in my mind:

Initial Call: c = [a b c d]; e = [ _ _ ]

Recursive Call 1: c = [b c d]; e = [a _ ]

Recursive Call 2: c = [c d]; e = [a b]

RETURN

After return: c = ; e = [a _ ]

Then I should be able to put a value in the array at index 1 because the array has returned from its state after recursive call 2 to its previous state after recursive call 1.

I'm not sure if my algorithm is correct; I haven't been able to get by the recursion issue to find out.

Upvotes: 0

Views: 263

Answers (1)

Tom Hawtin - tackline
Tom Hawtin - tackline

Reputation: 147154

There seems to be at least two problems there.

Firstly you are removing items from the Vector by index. So if we were to start with a vector containing a, b, c, d, e, f, each iteration of the loop would give us:

`b, c, d, e, f` // remove(0)
`b, d, e, f` // remove(1)
`b, d, f` // remove(2)
!!! // remove(3)

Secondly, Java passes references by value. There is no deep copy. You could either copy the Vector for each element, or more efficiently repair for each iteration:

    String str = (String)c.remove(i);
    e[getNextInd(e)] = str;
    calcCombNoRep(c,e);
    c.add(str, i);

(Also I should point out List (with ArrayList implementation) is used instead of Vector since 1998, and since 2004 we have generics (List<String>).)

Upvotes: 1

Related Questions