0

我一直在研究java中的递归函数来输出不允许重复的字符串的所有组合（'c'letter输出所有选择'e'字母的组合）。我一直在数组和向量返回到递归调用之前的状态时遇到问题。就好像一切都是通过引用传递的（这可能是正在发生的事情：我不知道如何通过它我更习惯用 C++ 编程而不是 Java）。

这是我的Java代码：

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

以下是它在调试窗口中的工作方式（所有调用的函数，如 output() 等似乎都可以正常工作）：

初始调用：c = [abcd]; e = [ _ _ ]

递归调用 1：c = [bcd]; e = [一个_]

递归调用 2：c = [cd]; e = [ab]

返回

返回后：c = [cd]; e = [ab]

然后我们在数组中遇到冲突，因为我试图在数组中 b 所在的索引 1 处放置一个值。

它应该如何在我的脑海中发挥作用：

初始调用：c = [abcd]; e = [ _ _ ]

递归调用 1：c = [bcd]; e = [一个_]

递归调用 2：c = [cd]; e = [ab]

返回

返回后：c = ; e = [一个_]

然后我应该能够在数组中的索引 1 处放置一个值，因为数组已经从递归调用 2 之后的状态返回到递归调用 1 之后的先前状态。

我不确定我的算法是否正确；我无法通过递归问题找出答案。

4

1 回答 1

1

那里似乎至少有两个问题。

Vector首先，您要从by 索引中删除项目。因此，如果我们从一个包含 的向量开始a, b, c, d, e, f，循环的每次迭代都会给我们：

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

其次，Java 按值传递引用。没有深拷贝。您可以Vector为每个元素复制 ，或者更有效地修复每次迭代：

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

（另外我应该指出List（有ArrayList实现）是使用而不是Vector自 1998 年以来，自 2004 年以来我们有泛型（List<String>）。）

于 2013-08-07T05:30:16.000 回答