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

Answer 1

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]