两个数组的笛卡尔积

Question

如何使用两个数组进行笛卡尔积？

A={1,2,3}
B={2,3,4}
C={(1,2),(1,3),(1,4),(2,2),(2,3),(2,4),(3,2),(3,3),(3,4)}

这是我使用的代码，但我总是得到 IndexOutOfBoundException。

public int[] cartesianProduct(int[] s1, int[] s2) {
    ArrayList<Integer> list = new ArrayList<>();
    for (int i = 0; i < s1.length; i++) {
        for (int v1 : s1) {
            for (int v2 : s2) {
                list.add(s1[i], s2[i]);
            }
        }
    }
    int[] result = new int[list.size()];
    int k = 0;
    for (int i : list) {
        result[k++] = i;
    }
    return result;
}

Answer 1

输出数组的元素应该是整数对，因此 int 数组不能作为输出类型，也不能使用 List<Integer> 来收集数据。

表示每对数字的一种方法是两个元素的 int 数组。这样输出将是一个二维数组，用于收集数据的 List 可以是 List<int[]>:

public int[][] cartesianProduct(int[] s1, int[] s2) {
    List<int[]> list = new ArrayList<>();
    for (int v1 : s1) {
        for (int v2 : s2) {
            list.add(new int[]{v1, v2});
        }
    }
    int[][] result = new int[list.size()][2];
    int k = 0;
    for (int[] i : list) {
        result[k++] = i;
    }
    return result;
}

Answer 2

作为@Eran 给出的答案的替代方案，我将停止使用有序对列表：

public List<int[]> cartesianProduct(int[] s1, int[] s2) {
    List<int[]> list = new ArrayList<int[]>();
    for (int v1 : s1) {
        for (int v2 : s2) {
            list.add(new int[]{v1, v2});
        }
    }
    return list;
}

要获得您想要的输出，您可以按如下方式遍历列表。

用法：

int[] s1 = new int[]{1, 2, 3};
int[] s2 = new int[]{2, 3, 4};
List<int[]> list = cartesianProduct(s1, s2);
System.out.print("{");
for (int i = 0; i < list.size(); ++i) {
    if (i > 0) System.out.print(", ");
    System.out.print("(" + list.get(i)[0] + ", " + list.get(i)[1] + ")");
}
System.out.println("}");

输出：

{(1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4)}

Answer 3

您不需要 List。试试这个。

public static int[][] cartesianProduct(int[] s1, int[] s2) {
    int size1 = s1.length;
    int size2 = s2.length;
    int[][] result = new int[size1 * size2][2];
    for (int i = 0, d = 0; i < size1; ++i) {
        for (int j = 0; j < size2; ++j, ++d) {
            result[d][0] = s1[i];
            result[d][1] = s2[j];
        }
    }
    return result;
}

Answer 4

用 Java 得到笛卡尔积 8:

int[] A = {1, 2, 3};
int[] B = {2, 3, 4};
int[][] AB = Arrays.stream(A).boxed()
        .flatMap(ai -> Arrays.stream(B).boxed()
                .map(bi -> new int[]{ai, bi}))
        .toArray(int[][]::new);
System.out.println("Cartesian product:\n" + Arrays.deepToString(AB));

输出：

Cartesian product:
[[1, 2], [1, 3], [1, 4], [2, 2], [2, 3], [2, 4], [3, 2], [3, 3], [3, 4]]

Answer 5

n 数组的递归解决方案。使用参数 i = 0

调用

public <T> List<List<T>> cartesianProduct(int i, List<T>... a) {
    if (i == a.length) {
        List<List<T>> result = new ArrayList<>();
        result.add(new ArrayList());
        return result;
    }
    List<List<T>> next = cartesianProduct(i + 1, a);
    List<List<T>> result = new ArrayList<>();
    for (int j = 0; j < a[i].size(); j++) {
        for (int k = 0; k < next.size(); k++) {
            List<T> concat = new ArrayList();
            concat.add(a[i].get(j));
            concat.addAll(next.get(k));
            result.add(concat);
        }
    }
    return result;
}

Answer 6

//Also, works great with int[][] input, returning int[][][]
public static int[][][] cartesianProduct(int[][] s1, int[][] s2) {
    int size1 = s1.length;
    int size2 = s2.length;
    int[][][] result = new int[size1 * size2][2][2];
    for (int i = 0, d = 0; i < size1; ++i) {
        for (int j = 0; j < size2; ++j, ++d) {
            result[d][0] = s1[i];
            result[d][1] = s2[j];
        }
    }
    return result;
}

两个数组的笛卡尔积

Cartesian product of two arrays

java

arrays

exception

cartesian-product