Taking one element from each list, in "every possible way"

Question

I will have x number of lists and each list will have an arbitrary number of elements. Each element is a word. I would like to take one element from each list and build a new list that contains one word from each list. I would like to store every list and when I'm finished I will have one list for every possibility of adding the words. Let us say we have 4 lists for example:

List 0: That Is Nice
List 1: You Look Good
List 2: Awesome
List 3: How Did You Do This

One way of taking an element from each list and adding them together would be:

New List 0: That You Awesome How

or

New List 1: Is You Awesome This

How can I build a recursive algorithm that works for an arbitrary number of list with an arbitrary number of elements? Preferably I would like to solve this problem in Java.

This is what I have done so far (I haven't used counter and length yet, but I plan to use it to only get the interesting combinations):

void everyPossibleWay(HashMap<Integer, ArrayList<String>> table, ArrayList<String> everyWay, int x, int y, int length, int counter) {
    if (table.get(x) != null) {
        if (y < table.get(x).size()) {
            everyWay.add(table.get(x).get(y));
            everyPossibleWay(table, everyWay, 0, y + 1, length, counter + 1);
            everyPossibleWay(table, everyWay, x + 1, y, length, counter);   
        }
    }
    else { 
        for (String s : everyWay)
        System.out.println(s + " ");
    }
}

I also know that I will get all the results in one list. But I'm just doing this to get something to work and then improve. When I run the code I only get one word from the last list.

Please post the code you've attempted so far. I'm sure you've read the other examples on this site for permutations and have tried something, right? — Duncan Jones, Jun 18 '13 at 13:10
First of all - do you want a recursive algorithm, which takes *random* element? Dude, that looks just overthought. Also, I'd take slightly different approach: imagine your List_1..List_n with enumerated words, i.e. list1:(0..list_1.length - 1), list2:(0..list_2.length - 1) and so on. Than just take n random numbers with k-th number in range (o..list_k.length-1) and than just select necessary words (By this you eliminate need of traversing list each time - just repeat the procedure as much times as you need and and that's it). — tkroman, Jun 18 '13 at 13:14
Thanks, I have added my code I done so far. @cdshines I'm not really sure I understand what you mean yet. But the elements won't be random. Just the size of the lists and how many lists. — David Lindahl, Jun 18 '13 at 13:20

score 2 · Accepted Answer · answered Jun 18 '13 at 14:20

This quiet simple recursive method works for me:

private List<List<String>> getAllCombinations(List<List<String>> lists)
{
    List<List<String>> result = new ArrayList<List<String>>();
    List<String> firstList = lists.get(0);
    List<List<String>> newParam = new ArrayList<>(lists);
    newParam.remove(0);
    if (!newParam.isEmpty()) {
        List<List<String>> midresult = getAllCombinations(newParam);
        for (String string : firstList) {
            for (List<String> list : midresult) {
                List<String> listNew = new ArrayList<>(list);
                listNew.add(0, string);
                result.add(listNew);
            }
        }
    } else {
        for (String string : firstList) {
            List<String> list = new ArrayList<String>();
            list.add(string);
            result.add(list);
        }
    }
    return result;
}

Can be tested like this:

    List<String> list1 = Arrays.asList("That", "Is");
    List<String> list2 = Arrays.asList("That2", "Is2", "all2");
    List<List<String>> param = new ArrayList<List<String>>();
    param.add(list1);
    param.add(list2);
    param = getAllCombinations(param);

Works better with Java 1.7 – Ondrej Bozek Jun 18 '13 at 14:47 — Ondrej Bozek, Jun 18 '13 at 14:47

score 0 · Answer 2 · answered Jun 18 '13 at 13:20

0

It's not recursive, but you can try something like this:

public ArrayList<ArrayList<String>> randomWord(ArrayList<ArrayList<String>> listWord, int nbNewList)
    {
        ArrayList<ArrayList<String>> newListWord = new ArrayList<ArrayList<String>>();
        for(int i=0; i< nbNewList ; i++)
        {
            ArrayList<String> al = new ArrayList<String>();
            for(ArrayList<String> al2 : listWord)
            {
                al.add(al2.get((int)(Math.random() * (al2.size()-1))));
            }
            newListWord.add(al);
        }

        return newListWord;
    }

answered Jun 18 '13 at 13:20

TroyAndAbed

301
1
10

Why are you using the random function? – David Lindahl Jun 18 '13 at 13:27
@TroyAndAbed please delete this answer, or modify it so that it relates to the question. – Bobulous Jun 18 '13 at 13:55

score 0 · Answer 3 · edited May 23 '17 at 11:59

0

Check out my answer to this question. There he was using tables but the concept is the same, and the method I suggested and provided pseudo code for was recursive. Good luck, Similar Question

If you have any experience with recursion here is what you do, you test for your base case and then you make two calls, one where you use the first element in the list and continue to the next list, and one call where you do not use that element and stay in the current list.

Something like this, obviously it is pseudocode so do not copy paste!

method buildLists(currentList, restOfLists, currentIndex, String combination){
restOfLists.removeHead
return buildLists(restOfLists.getHead, 0, combination + currentList.get(currentIndex))
return buildLists(currentList, restOfLists, currentIndex++, combination)
if(index<currentList.size()-1 restOfLists.isNull){
combinationList.add(combination)
}
}

edited May 23 '17 at 11:59

Community

1
1

answered Jun 18 '13 at 13:23

PandaBearSoup

699
3
9
20

I asked that question ;) And I got that one to work, but somehow I have difficulty solving this problem even though it's very similar. – David Lindahl Jun 18 '13 at 13:27
Oh that is silly, let me write you some more specific pseudo code and well see if that helps. – PandaBearSoup Jun 18 '13 at 13:29
Thank you! But, I do not really understand how I should use "currentList" and "restOfLists". Would you like to elaborate a little? – David Lindahl Jun 18 '13 at 13:50
currentList is the list you are currently looking at individual elements in. You will iterate through this list and use/not use each element. restOfLists is a list of lists of the other lists, each time you use an element in currentList, you move on to the next list contained within restOfLists. Unfortunately it looks like someone just gave you the answer though, but I hope you learned a bit about recursion! – PandaBearSoup Jun 18 '13 at 13:57
Thank you! I think I'm starting to grasping recursion a bit more. – David Lindahl Jun 18 '13 at 18:27

Taking one element from each list, in "every possible way"

3 Answers3