arrays - 数组数组中的所有组合

Question

我正在练习一些编码问题，但出于某些原因，我无法找到以下问题的解决方案。如果有人可以用算法或代码帮助我解决它，我将不胜感激。

给定一个二维数组，例如

 {{1}, {2,3}, {4,5,6}}        

我们需要生成所有可能的组合，以便从每个数组中恰好选择一个元素。

所以对于上面的输入结果集应该是

{{1,2,4}, {1,2,5}, {1,2,6}, {1,3,4}, {1,3,5}, {1,3,6}}

另一个例子:

Input = {{1,2,3}, {1,2}, {4,5}}
Output = {{1,1,4}, {1,1,5}, {1,2,4}, {1,2,5}, {2,1,4}, {2,1,5}, {2,2,4}, {2,2,5},{3,1,4}, {3,1,5}, {3,2,4}, {3,2,5}}

我尝试实现笛卡尔积方法，但在维护修改后的列表时遇到问题。这段代码不起作用，因为我正在更新结果列表本身，它给我的最终结果为 [[1,2,3],[1,2,3]] 但它应该是 [[1,2],[1 ,3]]

public class CartisianProduct {
public static void main(String[] args) {
    int[][] arr = { { 1 }, { 2, 3 } };
    cartisian(arr);
}

private static void cartisian(int[][] arr) {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    List<Integer> ll = new ArrayList<Integer>();
    for (int i : arr[0]) {
        ll.add(i);
    }
    result.add(ll);

    for (int i = 1; i < arr.length; i++) {
        result = cartisianHelper(result, arr[i]);
    }
    //System.out.println(result.get(0).toString() + "-" + result.get(1).toString());
}

private static List<List<Integer>> cartisianHelper(List<List<Integer>> result, int[] arr) {

    List<List<Integer>> rs = new ArrayList<List<Integer>>();
    List<List<Integer>> temp = new ArrayList<List<Integer>>();
    temp.addAll(result);
    for (int i = 0; i < result.size(); i++) {

        for (int j = 0; j < arr.length; j++) {
            List<Integer> ll = temp.get(i);
            ll.add(arr[j]);
            rs.add(ll);
        }
    }
    return rs;
}
}

Answer 1

import java.util.ArrayList;
import java.util.List;
class Solution{
    public static void main(String[] args){
        int[][] arr1 = {{1,2,3}, {1,2}, {4,5}};
        System.out.println(cartesianProduct(arr1,0,arr1.length).toString());
        int[][] arr2 = {{1},{2,3},{4,5,6}};
        System.out.println(cartesianProduct(arr2,0,arr2.length).toString());
        int[][] arr3 = {};
        System.out.println(cartesianProduct(arr3,0,arr3.length).toString());
        int[][] arr4 = {{1},{2}};
        System.out.println(cartesianProduct(arr4,0,arr4.length).toString());
        int[][] arr5 = {{99,101},{2000}};
        System.out.println(cartesianProduct(arr5,0,arr5.length).toString());
        int[][] arr6 = {{1},{2},{3},{4},{5},{6}};
        System.out.println(cartesianProduct(arr6,0,arr6.length).toString());
    }

    private static List<List<Integer>> cartesianProduct(int[][] arr,int curr_row,int length){
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if(curr_row == length) return res;

        List<List<Integer>> subproblem_result = cartesianProduct(arr,curr_row + 1,length);
        int size = subproblem_result.size();

        for(int i=0;i<arr[curr_row].length;++i){            
            if(size > 0){
                for(int j=0;j<size;++j){
                   List<Integer> current_combs = new ArrayList<>();
                   current_combs.add(arr[curr_row][i]);
                   current_combs.addAll(subproblem_result.get(j));
                   res.add(current_combs);
                }  
            }else{
                List<Integer> current_combs = new ArrayList<>();
                current_combs.add(arr[curr_row][i]);
                res.add(current_combs);
            }              
        }        

        return res;
    }
}

输出:

[[1, 1, 4], [1, 1, 5], [1, 2, 4], [1, 2, 5], [2, 1, 4], [2, 1, 5], [2, 2, 4], [2, 2, 5], [3, 1, 4], [3, 1, 5], [3, 2, 4], [3, 2, 5]]
[[1, 2, 4], [1, 2, 5], [1, 2, 6], [1, 3, 4], [1, 3, 5], [1, 3, 6]]
[]
[[1, 2]]
[[99, 2000], [101, 2000]]
[[1, 2, 3, 4, 5, 6]]

解释:

• 我们可以采用自上而下的方法(就像您的代码尝试做的那样)或自下而上的方法，但让我们采用自下而上的方法，因为您会更好地理解它。

  <

• 我们以{{1,2,3}, {1,2}, {4,5}}为例。

• 我们递归调用 cartesianProduct() 直到最深层次，即直到最后一行。如果调用超出它，我们返回一个空列表。
• 在最深层次上，我们的代码将位于 {4,5}。我们通过创建一个新列表、添加元素并最终将此列表添加到列表集合来将每个元素添加到列表中。因此，我们将列表作为 [[4],[5]] 返回到下一个顶行。
• 下一行是 {1,2}。在这里，我们再次迭代它的元素，同时，我们将该元素添加到从连续行返回的列表集合中的每个列表中。所以，我们将1添加到[4]，将1添加到[5]，2 到 [4] 和 2 到 [5]。所以，现在我们新返回的集合看起来像 [[1,4],[1,5],[2,4],[2,5]]。
• 下一行是 {1,2,3}。我们和上面一样。因此，我们将 1 添加到 [[1,4],[1,5],[2,4],[2,5]] 中的每个列表，同样适用于 2 和 3。
• 因此，我们的最终列表看起来像 [[1, 1, 4], [1, 1, 5], [1, 2, 4], [1, 2, 5], [2, 1, 4], [2, 1, 5], [2, 2, 4], [2, 2, 5], [3, 1, 4], [3, 1, 5], [3, 2, 4], [3, 2, 5]].
• 最后，我们像往常一样返回列表并使用 toString() 方法打印它。
• 请注意，如果您使用自上而下的方法，您仍会得出正确答案，但问题是获得的组合顺序与您预期的不同。