使用递归或任何其他解决方案替换嵌套的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]; 

我在这里重复多次，次数参数等于，把每一个数组元素的列表：

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

假设你有你的列表设置，使标签[0]是第一个字符串列表打印，标签[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 2

这是一个解决方案。这是我对你的其他帖子的回复修改：how to use recursion for nested 'for' loops。

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 3

建议你用番石榴的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); 
    } 
} 

输出：

结果：[英格兰，伦敦，DG300]，[英格兰，伦敦，SS500]，[英国，廷布，DG300]，[英国，廷布，SS500]，[英国，利马，DG300]，[英国，利马，SS500]，[不丹，伦敦，DG300]，[不丹，伦敦，SS500]廷布，DG300]，[不丹，廷布，SS500]，[不丹，利马，DG300]，[不丹，利马，SS500]，[每[秘鲁，利马，SS500]，[秘鲁，利马，SS500]] [秘鲁，伦敦，SS500]，[秘鲁，廷布，DG300]，[秘鲁廷布，SS500]]

应当指出的是，该解决方案是完全的一行代码：

• 更容易维护和谁继承您的代码来了解开发商。
• 未来的开发人员很可能会被打破。
• 几乎不值得一个单元测试，而提供的递归解决方案当然可以。
• 您确实询问您是否可以“以任何其他方式使用除递归以外的其他方式”。

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

如果你不知道哈斯克尔，这很好。这里的Java实现combinations：

// 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有优化，这使得递归和链表更加高效。优化此代码将是我对读者的挑战。我希望这将是教育（并激励一些到learn Haskell）。