Cartesian Product of multiple array

Question

I think it is basically an easy problem, but I'm stuck. My brain is blocked by this problem, so I hope you can help me. I have 2 to N arrays of integers, like

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

Now i want to have a list containing arrays of int[N] with every posibillity like

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

so there are 6*5*3 (90) elements in it.

Is there a simple algorithm to do it? I think the language didn't matter but I prefer Java.

You're searching for the "Cartesian product algorithm". Try google with this keywords. — Aurelio De Rosa, Oct 30 '11 at 14:50
Here http://stackoverflow.com/questions/1140164/scala-can-yield-be-used-multiple-times-with-a-for-loop/5177163#5177163 is a short, recursive solution in Scala. — user unknown, Oct 30 '11 at 18:02
@userunknown sorry, I couldn't read that... Scala is to weird and I never worked with it... other recursive solutions are appreciated — Rafael T, Oct 30 '11 at 18:27
You can find a python implementation using numpy here: http://stackoverflow.com/questions/1208118/using-numpy-to-build-an-array-of-all-combinations-of-two-arrays/1235363#1235363 — j13r, Mar 03 '12 at 16:50

score 2 · Accepted Answer · edited Jan 08 '14 at 02:15

Thx for the help! I add a valid answer with the implementation in java for the next guy, who has the same problem. I also do it generic so u can have any CartesianProduct on any Object, not just ints:

public class Product {

    @SuppressWarnings("unchecked")
    public static <T> List<T[]> getCartesianProduct(T[]... objects){
        List<T[]> ret = null;
        if (objects != null){               
            //saves length from first dimension. its the size of T[] of the returned list
            int len = objects.length;
            //saves all lengthes from second dimension
            int[] lenghtes = new int[len];
            // arrayIndex
            int array = 0;
            // saves the sum of returned T[]'s
            int lenSum = 1;
            for (T[] t: objects){
                lenSum *= t.length;
                lenghtes[array++] = t.length;
            }
            //initalize the List with the correct lenght to avoid internal array-copies
            ret = new ArrayList<T[]>(lenSum);
            //reusable class for instatiation of T[]
            Class<T> clazz = (Class<T>) objects[0][0].getClass();
            T[] tArray;
            //values stores arrayIndexes to get correct values from objects
            int[] values = new int[len];

            for (int i = 0; i < lenSum; i++){
                tArray = (T[])Array.newInstance(clazz, len);
                for (int j = 0; j < len; j++){
                    tArray[j] = objects[j][values[j]];
                }
                ret.add(tArray);
                //value counting:
                //increment first value
                values[0]++;
                for (int v = 0; v < len; v++){
                    //check if values[v] doesn't exceed array length
                    if (values[v] == lenghtes[v]){
                        //set it to null and increment the next one, if not the last
                        values[v] = 0;
                        if (v+1 < len){
                            values[v+1]++;
                        }
                    }
                }

            }
        } 
        return ret;
    }
}

Thank you! This method works very nice for me (I cant use recursion due performance). If you remove Generics and set result to array of array, the performance increase a lot! — Gilian, Aug 23 '18 at 22:43

score 0 · Answer 2 · answered May 23 '16 at 10:49

As I see this should work fine:

concatMap (λa -> concatMap (λb -> concatMap (λc -> (a,b,c)) L3) L2) L1

where concatMap(called SelectMany in C#) is defined as

concatMap f l = concat (map f l).

and map maps a function over a list

and concat(sometimes called flatten) takes a List of List and turns it into a flat List

score 0 · Answer 3 · answered Oct 30 '11 at 14:49

0

As i understand what you want, you need to get all permutations.

Use recursive algorithm, detailed here.

answered Oct 30 '11 at 14:49

mishadoff

10,719
2
33
55

I think that the OP want the Cartesian Product of 2 to N sets, not the permutations of a given set. – Aurelio De Rosa Oct 30 '11 at 14:51
this confuses me. What do I need now? note i edited the question – Rafael T Oct 30 '11 at 15:01
I was wrong. Now i got what you want. Use AurelioDeRosa's advice – mishadoff Oct 30 '11 at 15:03

Cartesian Product of multiple array

3 Answers3