一个列表中的 N 个元素与另一个列表中的 M 个元素的所有可能组合

Question

我想在 java 中创建一个接收两个字符串列表的方法：list1、list2 和两个整数：i1 和 i2 .该方法必须 return 列表 (List<List<String>>) 的列表，其中包含 (i1+i2) 元素的所有可能的不同列表组合，因此这些组合具有 i1 来自 list1 的元素，以及来自 list2.

的 i2 元素

示例：

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

-列表没有重复元素。

-一个列表中的元素不会出现在另一个列表中。

-我不需要两个具有相同元素的不同列表:(如果我有 {A,1} 我不需要 {1,A}）。

我目前的解决方案只适用于 i1 和 i2 的固定大小，我根据这个问题改编它：( Algorithm to return all combinations of k elements from n )

任何人都可以告诉我这个问题的任何算法或结构吗？

谢谢！

编辑：（添加了我的一些代码）

//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

从提问：

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.

代码如下：

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

测试

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

输出

[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]

一个列表中的 N 个元素与另一个列表中的 M 个元素的所有可能组合

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

java

combinations

arraylist