时间戳

首页 > 解决方案 > 数组数组中的所有组合

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

问题描述

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

给定一个二维数组，例如 

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

标签： arraysalgorithm

解决方案

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()until the deepest level，意思是直到最后一行。如果调用超过它，我们返回一个空列表。
  • 在最深层次，我们将{4,5}在我们的代码中。我们通过创建一个新列表、添加元素并最终将此列表添加到列表集合来将每个元素添加到列表中。因此，我们将列表返回到下一个顶行[[4],[5]]。
  • 下一个顶行是{1,2}。在这里，我们再次迭代它的元素，在这样做的同时，我们将该元素添加到从我们连续行返回的列表集合中的每个列表中。因此，我们添加1to [4]、1to [5]、2to[4]和2to [5]。所以，现在我们新返回的集合看起来像[[1,4],[1,5],[2,4],[2,5]].
  • 下一个顶行是{1,2,3}。我们做和上面一样。所以，我们添加1到每个列表中和[[1,4],[1,5],[2,4],[2,5]]也是如此。23
  • 因此，我们的最终列表看起来像[[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() 方法打印它。
  • 请注意，如果您使用自上而下的方法，您仍然会得到正确的答案，但问题是获得的组合顺序会与您的预期不同。

推荐阅读