как создать список кортежей из каждого значения в наборе списков

Question

Я хотел бы создать список кортежей из каждого значения в наборе списков. Набор списков может быть открытым, но для примера у меня есть следующие три списка строк.

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

Я хотел бы вернуть список кортежей, где в каждом кортеже есть элемент по каждому списку. В этом случае у меня будет 18 комбинаций (3 х 3 х 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

Рекурсивное решение, приведенное выше, завершается неудачей, если какой-либо из списков имеет общие элементы.Использование стека и добавление / удаление элементов вместо добавления / удаления их из списка исправляет это.Вот пересмотренный код для метода рекурсии:

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 3

  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 4

Это должно быть довольно легко с рекурсивной функцией.Это не проверено:

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