11

我正在用java做一个单词解读器。现在我有一个程序可以打印从具有 3 个或更多字母（不重复）的单词中选择的 3 个字母的所有重新排列。例如，如果参数是abcd，它将打印：

[[abc，abd，acb，acd，adb，adc，bac，坏，bca，bcd，bda，bdc，cab，cad，cba，cbd，cda，cdb，dab，dac，dba，dbc，dca，dcb] ]

我正在用排列填充一个二维数组列表。现在二维数组内部只有一个数组，其中包含 3 个字母的排列。我希望二维数组具有 1 个字母、2 个字母、3 个字母等排列的数组，在单词的长度处停止。问题是我需要可变数量的嵌套 for 循环来完成此操作。对于 3 个字母排列，我有 3 个嵌套的 for 循环。每一个循环遍历参数中的字母。

public static void printAllPermuations(String word)
{
    int len = word.length();
    ArrayList<String> lets = new ArrayList<String>();
    //this array of letters allows for easier access
    //so I don't have to keep substringing
    for (int i = 0; i < len; i++)
    {
        lets.add(word.substring(i, i + 1));
    }

    ArrayList<ArrayList<String>> newWords = new ArrayList<ArrayList<String>>();
    newWords.add(new ArrayList<String>());
    for (int i = 0; i < len; i++)
    {
        for (int j = 0; j < len; j++)
        {
            for (int k = 0; k < len; k++)
            {
                if (i != j && i != k && j != k)
                //prevents repeats by making sure all indices are different
                {
                    newWords.get(0).add(lets.get(i) + lets.get(j) + lets.get(k));
                }
            }
        }
    }
    System.out.println(newWords);
}

我看过其他帖子，听说递归可以解决这个问题。不过，我不知道我将如何实现它。而且我还看到了一些我不理解的复杂解决方案。我要求尽可能简单的解决方案，无论是否涉及递归。

4

3 回答 3

5

使用递归方法，您可以将其中一个循环放入函数中，将循环参数传递给该函数。然后从函数的循环中，它调用它来嵌套另一个循环。

void loopFunction(ArrayList<ArrayList<String>> newWords, int level) {
    if (level == 0) { // terminating condition
        if (/* compare the indices by for example passing down a list with them in  */)
        {
            newWords.get(...).add(...);
        }
    } else {// inductive condition
        for (int i = 0; i < len; i++) {
            loopFunction(newWords, level-1);
        }
    }
}

因此，对于您的示例，您需要 3 级递归，因此您可以使用以下方法开始递归：

loopFunction(newWords, 3);

编辑

既然你在这里遇到了麻烦，那就是一个工作版本。它保留一个索引列表以进行比较，并在运行时构建字符串。将重新排列的单词添加到每个级别的 2D 数组中，以获得所有长度的单词。使用递归，最容易从功能上思考而不改变并保持变量不可变（不可更改）。这段代码主要是这样做的，尽管indices为了方便我更新而不是创建一个新副本。

void loopFunction(ArrayList<String> lets, ArrayList<ArrayList<String>> newWords, int level, ArrayList<Integer> indices, String word) {
    if (level == 0) { // terminating condition
        return;
    } else { // inductive condition
        for (int i = 0; i < lets.size(); i++) {
            if (!indices.contains(i)) { // Make sure no index is equal
                int nextLevel = level-1;
                String nextWord = word+lets.get(i);

                newWords.get(level-1).add(nextWord);

                indices.add(i);
                loopFunction(lets, newWords, nextLevel, indices, nextWord);
                indices.remove((Integer) i);
            }
        }
    }
}
于 2013-08-10T20:17:44.920 回答
0

根据@DrYap 所说，我写了这个（与他的有点不同）：

这是启动它的代码：

for(int i = 1; i <= len; i++)
{
    newWords.add(new ArrayList<String>());
    loop(i);
}

这是循环方法。许多变量被声明为实例变量，所以我不必将它们传递给参数：

public static void loop(int level)
{
    if (level == 0)
    {
        int pos = indices.size() - 1;
        int pos2 = newWords.get(pos).size();
        newWords.get(pos).add("");
        for (Integer letIndex : indices)
        {
            String previous = newWords.get(pos).get(pos2);
            newWords.get(pos).set(pos2, previous + lets.get(letIndex));
        }
    }
    else
    {
        for (int i = 0; i < len; i++)
        {
            if (!indices.contains(i))
            {
                int indicesIndex = indices.size();

                indices.add((Integer) i);
                loop(level - 1);
                indices.remove(indicesIndex);
            }
        }
    }
}
于 2013-08-17T18:47:08.893 回答
0

我不会给你实际的代码，但这应该让你知道递归的样子（我相信还有其他递归方式：P）

void findAllCombination(String tmpResult, 
                        String rawString, 
                        int noOfChar, 
                        List<String> allCombinations) {
  if (tmpResult.size() == noOfChar) {
    allCombinations.add(tmpResult );
  } else {
    for (i in 0 to rawString.size()) {
      findAllCombination(tmpResult + rawString[i], 
                         rawString.removeCharAt(i),
                         noOfChar, 
                         allCombinations);
    }
  }
}

List<String> foo(String input, int level) {
    List<String> allResults = ...;
    findAllCombination("", input, level, allResults);
    return allResults;
}

主要的递归部分是findAllCombination. 这个想法是严格向前的。查找所有排列的方法是，对于我们拥有的rawString输入，我们将字符一个一个取出，并附加到之前找到的tmpResult，并使用该tmpResult做进一步的处理。一旦我们达到 tmpResult 足够长的点，我们就将 tmpResult 放到结果allCombinations列表中。

（foo() 方法在这里只是为了让您的调用更容易：P 实际执行工作的代码只有 6 行，不包括只有括号的行和忽略我为了更好的可读性而故意中断的行）

于 2013-08-16T07:49:15.930 回答