java - 递归计算所有数组元素组合问题

Question

我有一个程序，给定一个数组，返回其值的所有可能的组合(排列？)。我递归地这样做。它计算一切正常，但是，我想要做的是，我不想将每次迭代打印结果数组，而是将其附加到我之前声明的数组列表中。

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);
            }
        }
    }

但是包含所有可能状态的最终 Array List 的结果是错误的。而不是这个:

[[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]]

我明白了:

[[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]]

我不知道为什么会发生这种情况。也许递归事实导致附加操作以错误的方式工作？

Answer 1

嗨，

您总是向 ArrayList 添加相同的 State 对象。 每个递归循环都在修改同一个 State 对象。

您必须在 State 类中实现克隆:

@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;
}

并用 states.add(state.clone()); 替换 states.add(state);