使用递归或任何其他解决方案替换嵌套的 FOR 循环

Question

<?xml version="1.0"?>
<Event>
 <Country>England</Country>
 <City>London</City>
 <City>Liverpool</City>  
 <Code>DWW</Code>  
 <ID>DG300</ID>
 <ID>SS500</ID>
 <Division>Europe</Division>
</Event>

假设我有一个像上面那样的 XML。我有一个采用不同数量参数的方法：

myMethod(String... params){}

参数是我想从 XML 中读取的元素。举个例子，让 3 个元素形成 XML

myMethod(Country, City, ID){}

一开始我统计了这个方法传递了多少个参数：

int count=  params.size(); // let say for this example count=3

这里我创建了一个数组，列表作为元素：

List<String>[] tab= new ArrayList[count];

这里我迭代了多少次count参数等于，然后在每个数组元素中放入一个列表：

for(int i=0; i<count; i++){
    tab[i] = new ArrayList<>();
}

在我的方法中间，我有一些循环从 XML 中读取元素并将它们放入数组（将它们添加到列表中）。我使用 JAVAX

最后我的数组看起来像这样

tab=[(England),(London,Liverpool),(DG300,SS500)]

现在我有一个问题。我需要每个列表的笛卡尔，这意味着我需要行：

England London DG300
England London SS500
England Liverpool DG300
England Liverpool SS500

我可以用这样的嵌套循环来做到这一点

for(int i=0; i< tab[0].size();i++){
    for(int j=0; i< tab[1].size();j++){
        for(int k=0; i< tab[2].size();k++){

        System.out.println(tab[0].get(i)+ " " + tab[1].get(j)+" "+tab[2].get(k))
}}}}}

但这不是我一开始提到的好主意，我可以有不同数量的参数，所以我可以有不同数量的嵌套循环。可以是两个也可以是十个

如何使用 RECURSION 替换这个嵌套循环？或者也许我可以使用递归以外的任何其他方式来做到这一点？

Answer 1

这是一个解决方案。这是我对你的另一个 post 的回答的修改：.

public static void iterate(Object[] previousValues, List<Object>[] tabs) {
    if (tabs.length == 0) {
        System.out.println(Arrays.toString(previousValues));
    }
    else {
        final Object[] values = new Object[previousValues.length + 1];
        for (int i = 0; i < previousValues.length; i++) {
            values[i] = previousValues[i];
        }
        final List<Object>[] nextTabs = new List[tabs.length - 1];
        for (int i = 0; i < nextTabs.length; i++) {
            nextTabs[i] = tabs[i + 1];
        }
        for (Object o : tabs[0]) {
            values[values.length - 1] = o;
            iterate(values, nextTabs);
        }
    }
}
public static void iterate(List<Object>[] tabs) {
    iterate(new Object[0], tabs);
}

public static void main(String[] args) {
    final List<String> firstTab = new ArrayList<>();
    firstTab.add("England");
    final List<String> secondTab = new ArrayList<>();
    secondTab.add("London");
    secondTab.add("Liverpool");
    final List<String> thirdTab = new ArrayList<>();
    thirdTab.add("DG300");
    thirdTab.add("SS500");
    iterate(new List[]{firstTab, secondTab, thirdTab});
}

Answer 2

建议您使用Guava的Lists.cartesianProduct方法：

import java.util.Arrays;
import java.util.List;

import com.google.common.collect.Lists;

public class CartesianParams
{
    public static void main(String args[])
    {
        List<String> countries = Arrays.asList("England", "Bhutan", "Peru");
        List<String> cities = Arrays.asList("London", "Thimphu", "Lima");
        List<String> codes = Arrays.asList("DG300", "SS500");
        printCartesian(countries, cities, codes);
    }

    private static void printCartesian(List<String>... params)
    {
        //Exactly one line of code
        List<List<String>> results = Lists.cartesianProduct(params); 

        System.out.println("results: " + results);
    }
}

输出：

results: [[England, London, DG300], [England, London, SS500], [England, Thimphu, DG300], [England, Thimphu, SS500], [England, Lima, DG300], [England, Lima, SS500], [Bhutan, London, DG300], [Bhutan, London, SS500], [Bhutan, Thimphu, DG300], [Bhutan, Thimphu, SS500], [Bhutan, Lima, DG300], [Bhutan, Lima, SS500], [Peru, London, DG300], [Peru, London, SS500], [Peru, Thimphu, DG300], [Peru, Thimphu, SS500], [Peru, Lima, DG300], [Peru, Lima, SS500]]

需要注意的是，这个方案正好是一行代码：

维护起来更容易，继承您代码的开发人员也更容易理解。
被未来开发者破解的可能性大大降低。
几乎不值得进行单元测试，而提供的递归解决方案确实值得。
你确实问过你能不能"do this any other way using something else than recursion"。

Answer 3

假设您已设置列表，tab[0] 是要打印的第一个字符串的列表，tab[1] 是以下字符串的列表，等等，您可以按如下方式使用递归：

void print_rec(List<String>[] tab, int depth, String str) {
    int maxdepth = tab.length - 1;
    for (int i = 0; i < tab[depth].size(); i++) { // number of strings at this depth
        if (depth == maxdepth) {
            System.out.println(str + tab[depth].get(i)); // print line
            // no more lists to go through, print the line
        } else {
            print_rec(tab, depth + 1, str + tab[depth].get(i) + " ");
            // add next entry at this level to str and recurse
        }
    }
    // done with this depth, go back up one
}

void printAll(List<Strings>[] tab) {
    print_rec(tab, 0, "");
}

这涵盖了所有条目，就像嵌套循环一样。

Answer 4

说到写递归代码，我更喜欢先把函数写在Haskell，然后再翻译回Java。 Java 太冗长了，我无法考虑全局。

这是我的 Haskell 实现：

combinations :: [[String]] -> [[String]]
combinations []     = [[]]
combinations (x:xs) = do
    ys <- combinations xs
    y <- x
    return (y:ys)

快速测试表明 it works:

λ> mapM_ print $ combinations [["England"],["London","Liverpool"],["DG300","SS500"]]
["England","London","DG300"]
["England","London","SS500"]
["England","Liverpool","DG300"]
["England","Liverpool","SS500"]

如果您不知道 Haskell，没关系。这是 combinations 的 Java 实现：

// combinations :: [[String]] -> [[String]]
public static List<List<String>> combinations(List<List<String>> values) {

    // combinations [] = [[]]
    if (values.isEmpty()) {
        return Arrays.asList(Arrays.asList());
    }

    // combinations (x:xs) =
    List<String>       x  = values.get(0);
    List<List<String>> xs = values.subList(1, values.size());

    // do
    List<List<String>> outputs = new LinkedList<>();

    // ys <- combinations xs
    for (List<String> ys : combinations(xs)) {

        // y <- x
        for (String y : x) {

            // (y:ys)
            List<String> output = new LinkedList<>();
            output.add(y);
            output.addAll(ys);

            // return
            outputs.add(output);
        }
    }

    return outputs;
}

Ideone Demo

注意：此Java 代码效率非常低，因为Haskell 进行了优化，使递归和链表更加高效。优化此代码将是我对 reader 的挑战。我希望这将具有教育意义（并激励一些人 learn Haskell）。

使用递归或任何其他解决方案替换嵌套的 FOR 循环

Replacing nested FOR loops using recursion or any other solution

java

recursion

nested-loops