arrays - 多数组的笛卡尔积

Question

我认为这基本上是一个简单的问题，但我被卡住了。脑子被这个问题给堵住了，希望大家能帮帮我。我有 2 到 N 个整数数组，比如

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

现在我想要一个包含 int[N] 数组的列表，每个可能性都像

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

所以里面有6*5*3(90)个元素。

有没有简单的算法可以做到？我认为语言并不重要，但我更喜欢 Java。

Answer 1

谢谢你的帮助!我为下一个有同样问题的人添加了一个有效的 Java 实现答案。我也做它是通用的，所以你可以在任何对象上使用任何 CartesianProduct，而不仅仅是整数:

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