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;
}
Knight
  • 223
  • 2
  • 10
  • have an input of `LinkedList> list1` and do a `for(LinkedList list2 :list1){`. Inside it, do this: `for(String s: list2){` and `returnString += s`. You should be able to figure the rest out. – Justin Apr 18 '13 at 21:10
  • @gangqinlaohu: can you please elaborate? – Knight Apr 18 '13 at 22:08

3 Answers3

2

What you are computing is called the generalized Cartesian Product

This question has a nice Python implementation of how to loop through the Cartesian Product of an arbitrary number of varied-length vectors. Porting it to Java should be fairly easy - though, if you must use LinkedLists, it is better to save Iterators, not indexes, for your counting list.

Community
  • 1
  • 1
torquestomp
  • 3,304
  • 19
  • 26
1

So far this works: The code is modified from @PhilipWhitehouse and other's comments. Here it is. Please let me know if anyone finds any flaw in this.:

    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;
}
Knight
  • 223
  • 2
  • 10
0

For an array of 'n' lists using recursion:

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;
}
Philip Whitehouse
  • 4,293
  • 3
  • 23
  • 36
  • `LinkedList ... lists` is more appropriate in this case... If this would compile, that is. – m0skit0 Apr 18 '13 at 21:25
  • @m0skit0 It's essentially the same as a array of them - you access them as an array. I've never seen the point. – Philip Whitehouse Apr 18 '13 at 21:45
  • The point is not having to create an array and fill it only to be able to pass the argument. And I insist: your code does not compile. – m0skit0 Apr 18 '13 at 21:46
  • @Philip Whitehouse: Thanks for the code. But it doesn't compile. Could you please update it with a workable version? I am trying to modify yours, and when I am done I will upload my code. So, far I am still trying. – Knight Apr 18 '13 at 21:56