可变数量的集合的笛卡尔积，每个集合的大小可变

Question

设 G 为某个对象。

设 n = f(G) 为组数。

令 S_i = {1,2, ..., h(i) - 1, h(i)} 其中 1 ≤ i ≤ n.

我想写一个方法(Java) returns一个代表笛卡尔积的二维数组 S = S₁ X S₂ X ... X S_n-1 X S_n。该方法的意图显示在下面的 java-like 伪代码中。它意味着迭代解决方案，但递归解决方案也可以。

int[][] varCart(G, j) {
      int[][] result = new int[sizeOfCartProduct][f(G)]
      ....
      return result;
}

此外，S_j 更改为 { 1 }（或任何其他单例）。

举个例子：

设 G 为对象，使得：

f(G) = 3

S₁ = {1,2} [h(1) = 2]

S₂ = {1,2,3} [h(2) = 3]

S₃ = {1,2,3,4} [h(3) = 4]

并令 j = 2。

那么varCart(G,2)的结果一定是

int[2*1*4 = 8][3] = {{1,1,1},{1,1,2},{1,1,3},{1,1,4},{2,1,1},{2,1,2},{2,1,3},{2,1,4}}

Answer 1

创建一个数组，每个数字的最大值；在您的示例中，那将是 [2,3,4].
将数字 j 的最大值设置为 1，所以你得到 [2,1,4].
创建第一个组合 [1,1,1] 并将其添加到结果中。然后重复增加组合并将其添加到结果中。
要增加组合，请增加最后一位数字；如果该数字等于最大值，则将其设置为 1 并递增前一个数字，依此类推。如果第一个数字需要递增并且它已经设置为最大值，则您已找到所有组合。

[1,1,1] -> [1,1,2] -> [1,1,3] -> [1,1,4] ->
4 is maximum for last digit, so set it to 1 and increment previous digit ->
1 is maximum for second digit, so set it to 1 and increment previous digit ->
[2,1,1] -> [2,1,2] -> [2,1,3] -> [2,1,4] ->
4 is maximum for last digit, so set it to 1 and increment previous digit ->
1 is maximum for second digit, so set it to 1 and increment previous digit ->
2 is maximum for first digit, so all combinations have been found.

可变数量的集合的笛卡尔积，每个集合的大小可变

Cartesian product of a variable number of sets each of variable size

java

algorithm

recursion

set

cartesian-product