Java Multiple Array Recursion regardless of array size

Question

I have three arrays:

{}    
{a, b, c}
{d, e}

I am trying to combine them to get the following arrays:

{a, d}
{a, e}
{b, d}
{b, e}
{c, d} 
{c, e}

The problem I am coming across is the first empty array causes a nested for loop to not run at all - logically makes sense. ie:

 for (int i = 0; i < bL.size(); i++) {
        for (int j = 0; j < dL.size(); j++) {
            for (int k = 0; k < oL.size(); k++) {

What I am trying to find is the most efficient way to combine the three arrays regardless of their size. Most of the time all three have elements, but there are cases where one might generate an empty set.

Any help appreciated.

EDIT: Adding output for all three arrays

Input - {a,b} {c,d} {e,f}

Output - {a,c,e} {a,c,f} {a,d,e} {a,d,f} {b,c,e} {b,c,f}

EDIT: It's only possible for the first or third array to result in an empty set

Why don't you just recursively call a method that combines two arrays and inside that method you'd handle the special case of empty arrays? You'd not even have to call it recursively, just call it for the first two arrays and then for the current combination result and the next array. — Thomas
– Thomas, Commented Feb 12, 2012 at 23:04
Suppose the first array had elements {f,g}. What should the answer be in that case? — President James K. Polk
– President James K. Polk, Commented Feb 12, 2012 at 23:04
@GregS I assume he wants a cartesian product, although it differs in the fact that empty arrays/sets are effectively ignored. — Thomas
– Thomas, Commented Feb 12, 2012 at 23:08
@Thomas I can see how the method would work. Would that be considered common practice to achieve the cartesian product? — Josh
– Josh, Commented Feb 12, 2012 at 23:12
@Josh Producing Cartesian products of potentially unlimited sets explicitly isn't too common because of the danger of consuming loads of memory. Usually, you also want to filter your result based on some criteria, and the two operations are rolled into one. But if memory consumption isn't a problem and you can't reduce the size of the result straight away, then go ahead. — biziclop
– biziclop, Commented Feb 12, 2012 at 23:19

Sergey Kalinichenko · Accepted Answer · 2012-02-12 23:45:46Z

0

Assuming that you are going through arrays of int values, here is what you can do:

void printCombination(int[][] data, List<int> partial) {
    if (partial.size() == data.Length) {
        for (int i : partial) {
            if (i != -1) {
                System.out.writeln(" " + i);
            }
        }
        return;
    }
    if (data[partial.size()].length == 0) {
        partial.add(-1);
        printCombination(data, partial);
        partial.remove(partial.size()-1);
        return;
    }
    for (int i = 0 ; i != data[partial.size()].length; i++) {
        partial.add(data[partial.size()][i]);
        printCombination(data, partial);
        partial.remove(partial.size()-1);
    }
}

Initial call looks like this:

List<int> partial = new ArrayList();
int[][] data = new int[][] {new int[] {}, new int[] {1,2}, new int[] {3, 4, 5}};
printCombination(data, partial);

edited Feb 12, 2012 at 23:45

answered Feb 12, 2012 at 23:11

Sergey Kalinichenko

729k85 gold badges1.2k silver badges1.6k bronze badges

Where does 'p' and 'str' come from? Trying to follow the logic. I'm actually using Character[].

Josh
– Josh

02/12/2012 23:19:46
Commented Feb 12, 2012 at 23:19
There seem to be some errors in your code: 1. Why do you check the length of the list against the length of the 2D array? I assume you want that condition to be partial.size() == data[p].Length, don't you? 2. I assume you're missing the outer loop over data. You use the variable p but don't declare it.

Thomas
– Thomas

02/12/2012 23:21:10
Commented Feb 12, 2012 at 23:21
@Josh Oops, I lifted the code from another answer I gave earlier today, and forgot to rename variables. I edited the code to fix these.

Sergey Kalinichenko
– Sergey Kalinichenko

02/12/2012 23:24:22
Commented Feb 12, 2012 at 23:24
@Thomas I edited the code. The first check is actually right: I'm checking the length of partial against the outer dimension of the list. When they are equal, partial is actually "complete". The outer loop over data is the recursive invocation itself, so it is not needed.

Sergey Kalinichenko
– Sergey Kalinichenko

02/12/2012 23:26:10
Commented Feb 12, 2012 at 23:26
Wouldn't the line partial.add(data[partial.size()][i]); produce ArrayIndexOutOfBounds exception when trying to access the empty array?

Josh
– Josh

02/12/2012 23:34:08
Commented Feb 12, 2012 at 23:34

| Show 5 more comments

tom · Accepted Answer · 2012-02-13 07:23:08Z

Here is a simple recursive approach, which returns the result as a 2D ArrayList instead of printing it.

import java.util.ArrayList;

public class Program
{
    public static void main(String[] args)
    {
        String[][] x = { {}, {"a", "b", "c"}, {"d", "e"} };
        System.out.println(cartProd(x));
    }

    public static ArrayList< ArrayList<String> > cartProd(String[][] x)
    {
        return cartProd(x, new ArrayList<String>(), 0);
    }

    public static ArrayList< ArrayList<String> > cartProd(String[][] x, ArrayList<String> current, int index)
    {
        ArrayList< ArrayList<String> > result = new ArrayList< ArrayList<String> >();

        while (index < x.length && x[index].length == 0)
        {
            index++;
        }

        if (index == x.length)
        {
            result.add(new ArrayList<String>(current));
        }
        else
        {
            for (int i = 0; i < x[index].length; i++)
            {
                current.add(x[index][i]);
                result.addAll(cartProd(x, current, index + 1));
                current.remove(current.size() - 1);
            }
        }

        return result;
    }
}

Collectives™ on Stack Overflow

Java Multiple Array Recursion regardless of array size

2 Answers 2

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Your Answer

Sign up or log in

Post as a guest

Related