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

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

由于@Ted Hopp 发布了一个递归解决方案，我正在发布一个非递归解决方案。
这是一个可行的解决方案，

/**
 * @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);
    }

}

Answer 2

使用递归函数这应该很容易。这是未经测试的：

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 3

如果任何列表共享公共元素，则上述递归解决方案将失败。
使用堆栈并推送/弹出元素而不是从列表中添加/删除它们可以解决此问题。
这是递归方法的修改后的代码：

void recurse(int index, List<List<String>> input, Stack<String> prefix, List<List<String>> output) {
    if (index >= input.size()) {
        String[] tuple = new String[prefix.size()];
        prefix.copyInto(tuple);
        output.add(Arrays.asList(tuple));
    } else {
        List<String> next = input.get(index++);
        for (String item : next) {
            prefix.push(item);
            recurse(index, input, prefix, output);
            prefix.pop();
        }
    }
}

Answer 4

  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)