Ndtyjky

I am practicing a few coding questions and for some reasons I am not able to figure out a solution to below problem. I will appreciate if somebody could help me with algorithm or code to solve it.

Given a 2D array such as

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

we need to generate all possible combinations such that exactly one element is picked from each array.

So for above input the result set should be

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

Another example:

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

I tried implementing cartesian product approach but facing issues maintaining the modified list. This code is not working because I am updating the result list itself which is giving me final result as [[1,2,3],[1,2,3]] however it should be [[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;

}

}

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;

    }

}

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

Explanation:

• We can adopt either a top-bottom approach(like your code tries to do) or bottom-up approach, but let's go with bottom-up approach as you will understand it better.




• Let's take {{1,2,3}, {1,2}, {4,5}} as an example.



• We recursively call the cartesianProduct() till the deepest level, meaning till the last row. If the call exceeds it, we return an empty list.


• At the deepest level, we will be at {4,5} in our code. We add each element to the list by creating a new list, adding the element and finally adding this list to the list collection. Hence, we return the list to the next top row as [[4],[5]].


• Next top row is {1,2}. Here, we again iterate over it's elements and while doing so, we add that element to each list inside returned list collection from our successive row.
  So, we add 1 to [4], 1 to [5], 2 to [4] and 2 to [5]. So, now our new returned collection would look like [[1,4],[1,5],[2,4],[2,5]].


• Next top row is {1,2,3}. We do the same as above. So, we add 1 to each list in [[1,4],[1,5],[2,4],[2,5]] and same goes for 2 and 3.


• Hence, our final list would look like [[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]].


• In the end, we just return the list as usual and print it using the toString() method.


• Note that if you use the top-bottom approach, you would still arrive at the correct answer, but the thing is order of combinations obtained would be different than you expected.