All possible combinations of N elements from one list, with M elements from another list

Question

I want to make a method in java that receives two String Lists: list1, list2, and two integers: i1 and i2. The method has to return a list of lists (List<List<String>>) with all possible distinct list combinations of (i1+i2) elements, so that these combinations has i1 elements from list1, and i2 elements from list2.

Examples:

list1 = {A,B,C};  list2 = {1,2,3,4};

example1:
i1 = 1;           i2 = 3;
method(lis1,i1,list2,i2) results:
{{A,1,2,3};{A,2,3,4};{A,1,3,4};{A,1,2,3}
{B,1,2,3};{B,2,3,4};{B,1,3,4};{B,1,2,3}
{C,1,2,3};CA,2,3,4};{C,1,3,4};{C,1,2,3}}
////////////////////////////////////////////////////////////////////

example2:
i1 = 2;           i2 = 2;

method(lis1,i1,list2,i2) results:
{{A,B,1,2};{A,B,1,3};{A,B,1,4};{A,B,2,3};{A,B,2,4};{A,B,3,4};
{A,C,1,2};{A,C,1,3};{A,C,1,4};{A,C,2,3};{A,C,2,4};{A,C,3,4};
{B,C,1,2};{B,C,1,3};{B,C,1,4};{B,C,2,3};{B,C,2,4};{B,C,3,4}}
///////////////////////////////////////////////////////////////

example3:
i1 = 2;           i2 = 1;

method(lis1,i1,list2,i2) results:
{{A,B,1};{A,B,2};{A,B,3};{A,B,4}
{A,C,1};{A,C,2};{A,C,3};{A,C,4};
{B,C,1};{B,C,2};{B,C,3};{B,C,4};}
///////////////////////////////////////////////////////////////


example4:
i1 = 0;           i2 = 1;

method(lis1,i1,list2,i2) results:
{{1};{2};{3};{4}}
///////////////////////////////////////////////////////////////

-Lists has not duplicate elements.

-Elements in one list do not appear in the other one.

-I don't need two different lists with same elements:(if i have {A,1} i don't need {1,A}).

My current solution only works with fixed size of i1 and i2, and i adapt it from this question: ( Algorithm to return all combinations of k elements from n )

Can anybody please tell me any algorithm or structure for this problem?.

thanks!

EDIT: (added some of my code)

//This method returns a list containing, all possible distinct combinations
//of 3 items from the elemnts of "someList".
private List<List<String>> combinationOfThree(List<String> someList){
     List<List<String>> toReturn = new ArrayList<>();
     List<String> oneCombination = new ArrayList<>();
     int i, j, k;
     int len = someList.size();

     if (len<=3){
         for(String s :someList){
             oneCombination.add(s);
         }
         toReturn.add(oneCombination);
     }
     else{
         for (i = 0; i < len - 2; i++){
             for (j = i + 1; j < len - 1; j++){
                 for (k = j + 1; k < len; k++){
                     oneCombination = new ArrayList<>();
                     oneCombination.add(someList.get(i));
                     oneCombination.add(someList.get(j));
                     oneCombination.add(someList.get(k));
                     toReturn.add(oneCombination);
                 }
             }
         }
     }
 return toReturn;
}

private List<List<String>> allPosibleCombinations(List<String> list1, int list1_Amount, List<String> list2, int list2_Amount){
    List<List<String>> toReturn = new ArrayList<>();
    //currently i can only make combinations of 3 items. 
    //I can implement "combinationOfTwo" , "combinationOfFour" and so on, but it is nasty as hell.
    if (list1_Amount == list2_Amount == 3){
        List<List<String>> combinationOfThreeFromList1 = combinationOfThree(list1);
        List<List<String>> combinationOfThreeFromList2 = combinationOfThree(list2);

    for (List<String> a_l1_comb : combinationOfThreeFromList_1){
        for (List<String> a_l2_comb : combinationOfThreeFromList_2){
            toReturn.add(appendLists(a_l1_comb , a_l2_comb);
        }
    }
}
return toReturn;
}

It may help if you'd include your current solution in your question, even if it only works with fixed sizes. It'd probably make clear what you want, better than your examples. And it may be easier to hack that to what you want instead of writing something from scratch. — Arjan, Jun 08 '16 at 23:59
thanks for the response, i added some code, it is all i have. I did not proceed with this implementation because i think is pretty nasty, and i cant make a "combinationOf..." method for each amount. — joradev, Jun 09 '16 at 00:26
You write a *recursive* method to generate all combinations of `N` values from a `List`. Return value is `List>`. You call it twice, once for each list. You then create a method to generate all combinations of two `List>`, where result is a list of values, each list-value being a concatenation of a list-value from list 1 with a list-value from list 2. — Andreas, Jun 09 '16 at 01:38
The first method can also be done non-recursively. See this answer: [Algorithm to get all the combinations of size n from an array (Java)?](http://stackoverflow.com/a/29914908/5221149). — Andreas, Jun 09 '16 at 02:07
thanks for respones. Andreas, your implementation help me a lot, ty! — joradev, Jun 09 '16 at 18:56

score 0 · Accepted Answer · edited May 23 '17 at 12:31

From my comment to question:

You write a recursive method to generate all combinations of N values from a List<E>. Return value is List<List<E>>. You call it twice, once for each list. You then create a method to generate all combinations of two List<List<E>>, where result is a list of values, each list-value being a concatenation of a list-value from list 1 with a list-value from list 2.

Here is the code:

@SuppressWarnings("unchecked")
public static <T> List<List<T>> combos(int len, List<T> list) {
    if (len <= 0 || len > list.size())
        throw new IllegalArgumentException();
    List<List<T>> result = new ArrayList<>();
    combos(list, 0, Arrays.asList((T[])new Object[len]), 0, result);
    return result;
}
private static <T> void combos(List<T> list, int listIdx, List<T> values, int valueIdx, List<List<T>> result) {
    if (valueIdx == values.size()) {
        result.add(new ArrayList<>(values));
        return;
    }
    int lastIdx = list.size() - (values.size() - valueIdx);
    for (int i = listIdx; i <= lastIdx; i++) {
        values.set(valueIdx, list.get(i));
        combos(list, i + 1, values, valueIdx + 1, result);
    }
}
public static <T> List<List<T>> combos(List<List<T>> list1, List<List<T>> list2) {
    List<List<T>> result = new ArrayList<>(list1.size() * list2.size());
    for (List<T> value1 : list1)
        for (List<T> value2 : list2) {
            List<T> combo = new ArrayList<>(value1.size() + value2.size());
            combo.addAll(value1);
            combo.addAll(value2);
            result.add(combo);
        }
    return result;
}

TEST

List<List<Integer>> result = combos(combos(3, Arrays.asList(0,1,2,3,4)),
                                    combos(2, Arrays.asList(5,6,7,8,9)));
for (List<Integer> list : result)
    System.out.println(list);

OUTPUT

[0, 1, 2, 5, 6]
[0, 1, 2, 5, 7]
[0, 1, 2, 5, 8]
[0, 1, 2, 5, 9]
[0, 1, 2, 6, 7]
[0, 1, 2, 6, 8]
[0, 1, 2, 6, 9]
[0, 1, 2, 7, 8]
[0, 1, 2, 7, 9]
[0, 1, 2, 8, 9]
[0, 1, 3, 5, 6]
[0, 1, 3, 5, 7]
[0, 1, 3, 5, 8]
[0, 1, 3, 5, 9]
[0, 1, 3, 6, 7]
[0, 1, 3, 6, 8]
[0, 1, 3, 6, 9]
[0, 1, 3, 7, 8]
[0, 1, 3, 7, 9]
[0, 1, 3, 8, 9]
[0, 1, 4, 5, 6]
[0, 1, 4, 5, 7]
[0, 1, 4, 5, 8]
[0, 1, 4, 5, 9]
[0, 1, 4, 6, 7]
[0, 1, 4, 6, 8]
[0, 1, 4, 6, 9]
[0, 1, 4, 7, 8]
[0, 1, 4, 7, 9]
[0, 1, 4, 8, 9]
[0, 2, 3, 5, 6]
[0, 2, 3, 5, 7]
[0, 2, 3, 5, 8]
[0, 2, 3, 5, 9]
[0, 2, 3, 6, 7]
[0, 2, 3, 6, 8]
[0, 2, 3, 6, 9]
[0, 2, 3, 7, 8]
[0, 2, 3, 7, 9]
[0, 2, 3, 8, 9]
[0, 2, 4, 5, 6]
[0, 2, 4, 5, 7]
[0, 2, 4, 5, 8]
[0, 2, 4, 5, 9]
[0, 2, 4, 6, 7]
[0, 2, 4, 6, 8]
[0, 2, 4, 6, 9]
[0, 2, 4, 7, 8]
[0, 2, 4, 7, 9]
[0, 2, 4, 8, 9]
[0, 3, 4, 5, 6]
[0, 3, 4, 5, 7]
[0, 3, 4, 5, 8]
[0, 3, 4, 5, 9]
[0, 3, 4, 6, 7]
[0, 3, 4, 6, 8]
[0, 3, 4, 6, 9]
[0, 3, 4, 7, 8]
[0, 3, 4, 7, 9]
[0, 3, 4, 8, 9]
[1, 2, 3, 5, 6]
[1, 2, 3, 5, 7]
[1, 2, 3, 5, 8]
[1, 2, 3, 5, 9]
[1, 2, 3, 6, 7]
[1, 2, 3, 6, 8]
[1, 2, 3, 6, 9]
[1, 2, 3, 7, 8]
[1, 2, 3, 7, 9]
[1, 2, 3, 8, 9]
[1, 2, 4, 5, 6]
[1, 2, 4, 5, 7]
[1, 2, 4, 5, 8]
[1, 2, 4, 5, 9]
[1, 2, 4, 6, 7]
[1, 2, 4, 6, 8]
[1, 2, 4, 6, 9]
[1, 2, 4, 7, 8]
[1, 2, 4, 7, 9]
[1, 2, 4, 8, 9]
[1, 3, 4, 5, 6]
[1, 3, 4, 5, 7]
[1, 3, 4, 5, 8]
[1, 3, 4, 5, 9]
[1, 3, 4, 6, 7]
[1, 3, 4, 6, 8]
[1, 3, 4, 6, 9]
[1, 3, 4, 7, 8]
[1, 3, 4, 7, 9]
[1, 3, 4, 8, 9]
[2, 3, 4, 5, 6]
[2, 3, 4, 5, 7]
[2, 3, 4, 5, 8]
[2, 3, 4, 5, 9]
[2, 3, 4, 6, 7]
[2, 3, 4, 6, 8]
[2, 3, 4, 6, 9]
[2, 3, 4, 7, 8]
[2, 3, 4, 7, 9]
[2, 3, 4, 8, 9]

All possible combinations of N elements from one list, with M elements from another list

1 Answers1