如何从一组列表中的每个值创建元组列表

Question

我想从一组列表中的每个值创建一个元组列表。该列表可以打开，但是对于这个例子，我有以下三个字符串列表。

L1: (one, two three) 
L2: (a, b, c) 
L3: (yes, no) 

我想返回一个元组列表，其中每个元组中的元素来自每个列表。在这种情况下，我将有18种组合（3 x 3 x 2）

T1: (one, a, yes) 
T2: (one, a, no) 
T3: (one, b, yes) 
T4: (one, b, no) 
T5: (one, c, yes) 
T6: (one, c, no) 
T7: (two, a, yes) 

等等。在这种情况下，我们使用Java。

List<List<String>> list = getInput(); 
List<List<String> tuples = combinations(list); 

其中getInput（）返回我的输入（L1，L2，L3），以及它们的组合创建我的输出（T1，T2，T3 ......）

Answer 1

这应与一个递归函数很容易。这是未经测试：

List<List<String>> listOfTuples(<List<List<String>> list) { 
    ArrayList<List<String>> result = new ArrayList<List<String>>(); 
    List<String> prefix = new ArrayList<String>(); 
    recurse(0, list, prefix, result); 
    return result; 
} 

void recurse(int index, 
      List<List<String>> input, 
      List<String> prefix, 
      List<List<String>> output) 
{ 
    if (index >= input.size()) { 
     output.add(new ArrayList<String>(prefix)); 
    } else { 
     List<String> next = input.get(index++); 
     for (String item : next) { 
      prefix.add(item); 
      recurse(index, input, prefix, output); 
      prefix.remove(item); 
     } 
    } 
} 

Answer 2

1. Impose an arbitrary ordering on the lists. 
    For instance, create a list with order 
    given by index. 
    2. Call permute(thelists[1..n], buffer[1..n], 1). 

    permute(thelist[1..n], buffer[1..n], pos) 
    1. if pos > n then print buffer 
    2. else then 
    3. for i = 1 to |thelists[pos]| do 
    4.  buffer[pos] = thelists[pos][i] 
    5.  permute(thelists[1..n], buffer[1..n], pos + 1) 

Answer 3

由于@Ted霍普发布了递归解决方案我张贴的非递归解决方案。 这是一个可行的解决方案，

/** 
* @author kalyan 
* 
*/ 
import java.util.ArrayList; 
import java.util.LinkedList; 
import java.util.List; 
import java.util.Stack; 

public class Permutation 
{ 

    public static void printLists(List<List<String>> list) { 

     for(List<String> lstItem : list) { 
      System.out.println(lstItem.toString()); 
     } 
    } 

    public static List<List<String>> recurse(List<LinkedList<String>> list) { 

     List<List<String>> out = new ArrayList<List<String>>(); 
     Stack<String> mystack = new Stack<String>(); 
     int i = 0; 

     while (! (i == 0 && list.get(0).get(0).equals("TAIL"))) { 

      if (i >= list.size()) { 
       /* We have got one element from all the list */ 
       out.add(new ArrayList<String>(mystack)); 

       /* Go back one row */ 
       i --; 

       /* remove the last added element */ 
       mystack.pop(); 
       continue; 
      } 

      LinkedList<String> tuple = list.get(i); 

      if (tuple.getFirst().equals("TAIL")) { 

       /* We have finished one sub list go back one row */ 
       i--; 

       mystack.pop(); 
       /* also fall below to move the TAIL from begining to end */ 
      } 
      else { 
       mystack.add(tuple.getFirst()); 
       i++; 
      } 
      tuple.add(tuple.getFirst()); 
      tuple.removeFirst(); 
     } 

     return out; 
    } 

    public static void main(String[] args) { 
     List<LinkedList<String>> list = new ArrayList<LinkedList<String>>(); 
     List<List<String>> perm = new ArrayList<List<String>>(); 

     /* keep TAIL, so that we know processed a list */ 
     LinkedList<String> num = new LinkedList<String>(); 
     num.add("one"); num.add("two"); num.add("three"); num.add("TAIL"); 

     LinkedList<String> alpha = new LinkedList<String>(); 
     alpha.add("a"); alpha.add("b"); alpha.add("c"); alpha.add("TAIL"); 

     LinkedList<String> bool = new LinkedList<String>(); 
     bool.add("yes"); bool.add("no"); bool.add("tristate"); bool.add("TAIL"); 

     list.add(num); list.add(alpha); list.add(bool); 

     perm = recurse (list); 
     printLists(perm); 
    } 

}