3

Lets say I have 3 lists with 3 elements each.

List1: "cat, sat, mat"; List2: "every, boy, deserves; List3: all, lines, here . My output should be:

Listout: cat,every,all; cat,every,lines; cat,every,here; cat,boy,all; cat,boy,lines;..

I can write a method that can append all elements of first while there is a loop that runs through the two other lists. But how to tackle this for more than 3 lists. Like 10 lists. The output will contain 3 to the 10 elements. Can you give me an idea of how the code/method in Java would look like? I know I might need recursion: but what would be the input to that recursive method?

I have tried this one like this and it works: 

public static LinkedList<String> getPermutations(LinkedList<String> list1, LinkedList<String> list2, LinkedList<String> list3){
    LinkedList<String> final_list = new LinkedList<String>();
    Iterator<String> it = list1.iterator();
    while (it.hasNext()) {
        String this_element1 = it.next();
        //System.out.println("elem1: "+this_element1);
        Iterator<String> it2 = list2.iterator();
        while (it2.hasNext()) {
            String this_element2 = it2.next();
            //System.out.println("elem2: "+this_element2);
            Iterator<String> it3 = list3.iterator();
            while (it3.hasNext()) {
                String this_element3 = it3.next();
                //System.out.println(this_element3);
                final_list.add(this_element1+","+this_element2+","+this_element3);
            }//3
        }//2
    }//1
    return final_list;
}
4

3 回答 3

2

您正在计算的内容称为广义笛卡尔积

这个问题有一个很好的 Python 实现，说明如何遍历任意数量的变长向量的笛卡尔积。将它移植到 Java 应该相当容易 - 但是，如果必须使用 LinkedLists，最好为计数列表保存迭代器，而不是索引。

于 2013-04-18T21:13:11.287 回答
1

到目前为止，这是可行的：代码是根据@PhilipWhitehouse 和其他人的评论修改的。这里是。如果有人发现这有任何缺陷，请告诉我：

    public static LinkedList<String> getPermutationsComb2(LinkedList<LinkedList<String>> lists) {
    LinkedList<String> retList = new LinkedList<String>();

    if(lists.size() > 1) {
        LinkedList<LinkedList<String>> subLists = new LinkedList<LinkedList<String>>();
        for(int i = 1; i < lists.size(); i++) {
            subLists.add(lists.get(i));
        }
        LinkedList<String> listTails = getPermutationsComb2(subLists);
        Iterator<String> it_tail1 = lists.get(0).iterator();
        while(it_tail1.hasNext()){
            String listHead2 = it_tail1.next();
            Iterator<String> it_tail2 = listTails.iterator();
            while(it_tail2.hasNext()){
                retList.add(listHead2+","+it_tail2.next());
            }
        }
    } else {
        retList = lists.get(0);
    }
    return retList;
}
于 2013-04-18T22:30:46.450 回答
0

对于使用递归的“n”个列表数组：

public static LinkedList<String> getPermutations(LinkedList<String>[] lists) {
    LinkedList<String> retList = new LinkedList<String>();
    Iterator<String> iList = lists[0].iterator();
    if (lists.length > 1) {
        while (iList.hasNext()) {
            String listHead = iList.next();
            @SuppressWarnings("unchecked")
            LinkedList<String>[] subLists = new LinkedList[lists.length - 1];
            for (int i = 1; i < lists.length; i++) {
                subLists[i - 1] = lists[i];
            }
            LinkedList<String> listTails = getPermutations(subLists);
            Iterator<String> iTails = listTails.iterator();
            while (iTails.hasNext()) {
                retList.add(listHead + "," + iTails.next());
            }
        }
    } else {
        retList = lists[0];
    }
    return retList;
}
于 2013-04-18T21:23:58.173 回答