CODEWITHSUNDEEP
javaarraysrecursioncombinationspermutation
chick3n0x07CC
chick3n0x07CC

Reputation: 798

Calculate all array elements combinations recursively issue

I have a program that, given an array, returns all possible combinations (permutations?) of its values. I do that recursively. And it calculate all ok, but, what I want to do is, instead of printing the resulting array each iteration, I want to append it to an Array List I declared before.

public static final int NUMBER_OF_CELLS = 3;
public static final int NUMBER_OF_ATTRIBUTES = 3;
// I want all possible combinations all elements 0, 1 and 2, taken 3 at a time 

private ArrayList<State> states= new ArrayList<State>();

public void createAllPossibleStates() {
        State state = new State(NUMBER_OF_CELLS);
        setValues(0, state);
        System.out.println(states);  // This gives me a wrong ouput and I don't know why
    }

public void setValues(int cell, State state) {
        if(cell == NUMBER_OF_CELLS) {
                // System.out.println(state.toString());  // Instead of this
                states.add(state);  // I want this. Append the array to an array list
            }
        }
        else {
            for(int i = 0; i < NUMBER_OF_ATTRIBUTES; i++) {
                state.values[cell] = i;
                setValues(cell + 1, state);
            }
        }
    }

But the result of the final Array List contining all possible states is wrong. Instead of this:

[[0, 0, 0],[0, 0, 1],[0, 0, 2],[0, 1, 0],[0, 1, 1],[0, 1, 2],[0, 2, 0],[0, 2, 1],[0, 2, 2],[1, 0, 0],[1, 0, 1],[1, 0, 2],[1, 1, 0],[1, 1, 1],[1, 1, 2],[1, 2, 0],[1, 2, 1],[1, 2, 2],[2, 0, 0],[2, 0, 1],[2, 0, 2],[2, 1, 0],[2, 1, 1],[2, 1, 2],[2, 2, 0],[2, 2, 1],[2, 2, 2]]

I get this:

[[2, 2, 2], [2, 2, 2], [2, 2, 2], [2, 2, 2], [2, 2, 2], [2, 2, 2], [2, 2, 2], [2, 2, 2], [2, 2, 2], [2, 2, 2], [2, 2, 2], [2, 2, 2], [2, 2, 2], [2, 2, 2], [2, 2, 2], [2, 2, 2], [2, 2, 2], [2, 2, 2], [2, 2, 2], [2, 2, 2], [2, 2, 2], [2, 2, 2], [2, 2, 2], [2, 2, 2], [2, 2, 2], [2, 2, 2], [2, 2, 2]]

I can't wonder why this happens. Maybe the recursion fact causes the appending operation work the wrong way?

Upvotes: 0

Views: 88

Answers (2)

Bohemian
Bohemian

Reputation: 424983

You only have 1 instance of State and you're passing it down through the call stack, modifying it, then adding it to the list multiple times (one for each recursion termination). Of course, since there's only one object involved, it will have whatever state (no pun intended) was the last state given to it.

Without modifying too much code, you need to make a copy of the State object and add the copy to the list - to permanently capture the state at the time you added it to the list.

There are a few standard ways of doing that, but perhaps the easiest to understand and the most commonly used is the copy constructor:

public State(State state) {
    this.values = Arrays.copyOf(state.values, state.values.length);
    // copy over whatever other fields you need
}

Then in your code:

states.add(new State(state));

Upvotes: 1

Ele
Ele

Reputation: 33726

Hi,

You're always adding the same State object to the ArrayList. Every recursion loop is modifying the same State object.

You must implement clone in State class:

@Override
protected State clone() throws CloneNotSupportedException {
    State state = new State(NUMBER_OF_CELLS);
    System.arraycopy(this.values, 0, state.values, 0, this.values.length);

    return state;
}

And replace states.add(state); by states.add(state.clone());

Upvotes: 1

Related Questions