All combinations in array of arrays
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;
}
}
arrays algorithm
|
show 2 more comments
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;
}
}
arrays algorithm
en.wikipedia.org/wiki/Cartesian_product
– m69
Nov 10 at 23:08
Thanks m69! That helped.
– skg
Nov 10 at 23:24
What's the question? What have you tried to solve it?
– maxpaj
Nov 10 at 23:31
You can simply recurse to deeper levels and get those combinations. What have you tried?
– vivek_23
Nov 11 at 5:16
1
@vivek_23 I posted the approach I am following.
– skg
Nov 11 at 23:38
|
show 2 more comments
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;
}
}
arrays algorithm
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;
}
}
arrays algorithm
arrays algorithm
edited Nov 12 at 0:08
asked Nov 10 at 23:07
skg
11
11
en.wikipedia.org/wiki/Cartesian_product
– m69
Nov 10 at 23:08
Thanks m69! That helped.
– skg
Nov 10 at 23:24
What's the question? What have you tried to solve it?
– maxpaj
Nov 10 at 23:31
You can simply recurse to deeper levels and get those combinations. What have you tried?
– vivek_23
Nov 11 at 5:16
1
@vivek_23 I posted the approach I am following.
– skg
Nov 11 at 23:38
|
show 2 more comments
en.wikipedia.org/wiki/Cartesian_product
– m69
Nov 10 at 23:08
Thanks m69! That helped.
– skg
Nov 10 at 23:24
What's the question? What have you tried to solve it?
– maxpaj
Nov 10 at 23:31
You can simply recurse to deeper levels and get those combinations. What have you tried?
– vivek_23
Nov 11 at 5:16
1
@vivek_23 I posted the approach I am following.
– skg
Nov 11 at 23:38
en.wikipedia.org/wiki/Cartesian_product
– m69
Nov 10 at 23:08
en.wikipedia.org/wiki/Cartesian_product
– m69
Nov 10 at 23:08
Thanks m69! That helped.
– skg
Nov 10 at 23:24
Thanks m69! That helped.
– skg
Nov 10 at 23:24
What's the question? What have you tried to solve it?
– maxpaj
Nov 10 at 23:31
What's the question? What have you tried to solve it?
– maxpaj
Nov 10 at 23:31
You can simply recurse to deeper levels and get those combinations. What have you tried?
– vivek_23
Nov 11 at 5:16
You can simply recurse to deeper levels and get those combinations. What have you tried?
– vivek_23
Nov 11 at 5:16
1
1
@vivek_23 I posted the approach I am following.
– skg
Nov 11 at 23:38
@vivek_23 I posted the approach I am following.
– skg
Nov 11 at 23:38
|
show 2 more comments
1 Answer
1
active
oldest
votes
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 add1
to[4]
,1
to[5]
,2
to[4]
and2
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 add1
to each list in[[1,4],[1,5],[2,4],[2,5]]
and same goes for2
and3
. - 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.
@skg any update?
– vivek_23
Nov 13 at 20:03
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53244303%2fall-combinations-in-array-of-arrays%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
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 add1
to[4]
,1
to[5]
,2
to[4]
and2
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 add1
to each list in[[1,4],[1,5],[2,4],[2,5]]
and same goes for2
and3
. - 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.
@skg any update?
– vivek_23
Nov 13 at 20:03
add a comment |
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 add1
to[4]
,1
to[5]
,2
to[4]
and2
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 add1
to each list in[[1,4],[1,5],[2,4],[2,5]]
and same goes for2
and3
. - 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.
@skg any update?
– vivek_23
Nov 13 at 20:03
add a comment |
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 add1
to[4]
,1
to[5]
,2
to[4]
and2
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 add1
to each list in[[1,4],[1,5],[2,4],[2,5]]
and same goes for2
and3
. - 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.
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 add1
to[4]
,1
to[5]
,2
to[4]
and2
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 add1
to each list in[[1,4],[1,5],[2,4],[2,5]]
and same goes for2
and3
. - 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.
answered Nov 12 at 8:02
vivek_23
2,0931518
2,0931518
@skg any update?
– vivek_23
Nov 13 at 20:03
add a comment |
@skg any update?
– vivek_23
Nov 13 at 20:03
@skg any update?
– vivek_23
Nov 13 at 20:03
@skg any update?
– vivek_23
Nov 13 at 20:03
add a comment |
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53244303%2fall-combinations-in-array-of-arrays%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
en.wikipedia.org/wiki/Cartesian_product
– m69
Nov 10 at 23:08
Thanks m69! That helped.
– skg
Nov 10 at 23:24
What's the question? What have you tried to solve it?
– maxpaj
Nov 10 at 23:31
You can simply recurse to deeper levels and get those combinations. What have you tried?
– vivek_23
Nov 11 at 5:16
1
@vivek_23 I posted the approach I am following.
– skg
Nov 11 at 23:38