CODEWITHSUNDEEP
javalistarraylist
Knight
Knight

Reputation: 223

How to code this particular method?

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

Upvotes: 3

Views: 138

Answers (3)

Philip Whitehouse
Philip Whitehouse

Reputation: 4157

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

Upvotes: 0

Knight
Knight

Reputation: 223

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

Upvotes: 1

torquestomp
torquestomp

Reputation: 3344

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.

Upvotes: 2

Related Questions