可变数量的嵌套For循环 [英] Variable Number of Nested For Loops

问题描述

我正在用Java解释单词.现在，我有一个程序可以打印从3个或更多字母(无重复)的单词中选择的3个字母的所有重排.因此，例如，如果参数为 abcd ，它将打印以下内容:

I'm making a word unscrambler in java. Right now I have a program that can print all rearrangements of 3 letters chosen from a word with 3 or more letters (no repeats). So for example, if the parameter is abcd, it will print this:

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

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

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

I'm filling a 2D array list with the permutations. Right now the 2D array has only one array inside of it, which contains the permutations for 3 letters. I want the 2D array to have arrays for permuations of 1 letter, 2 letters, 3 letters, and so on, stopping at the length of the word. The problem is that I need a variable number of nested for loops to accomplish this. For the 3 letter permutations, I have 3 nested for loops. Each one cycles through the letters in the parameter.

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

我看过其他文章，听说递归可以解决这个问题.不过，我不知道该如何实现.而且，我还看到了一些我不理解的复杂解决方案.我正在寻求一种可能的最简单解决方案，无论它是否涉及递归.

I've looked at other posts and I've heard that recursion can solve this. I don't know how I would implement that, though. And I've also seen some complicated solutions that I don't understand. I'm asking for the simplest solution possible, whether it involves recursion or not.

推荐答案

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

With the recursive method you would put one of your looping in a function pass the loop parameters to that function. Then from within the function's loop, it calls its to nest another loop.

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个级别的递归，因此您可以通过以下方式开始递归:

So for your example you need 3 levels of recursion so you would start the recursion with:

loopFunction(newWords, 3);

修改

由于您遇到了麻烦，因此这里是一个有效的版本.它保留要比较的索引列表，并随即建立字符串.重新排列的单词在每个级别都添加到2D数组中，以获取单词的所有长度.通过递归，最简单的方法是从功能上进行思考，而不进行更改，并使变量保持不变(不变).尽管我为了方便起见更新了indices而不是创建新副本，但是这段代码基本上做到了这一点.

Since you have been having trouble here is a working version. It keeps a list of indices to compare against and it builds up the string as it goes. The rearranged words are added to the 2D array at each level to get all lengths of words. With recursion it is easiest to think functionally and not change and keep the variables immutable (unchangeable). This code mostly does that although I update the indices rather than create a new copy for convenience.

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

这篇关于可变数量的嵌套For循环的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！