笛卡尔幂（一种特殊的笛卡尔积）——以可重复的方式从数组中选择元素
Cartesian power (a special Cartesian product) -- choose elements from array, in repeatable style
输入:
有一个长度为 n.
的输入数组（假设没有重复元素）
输出：
并且想打印所有可能的相同长度的数组 n 由输入数组中的元素组成，每个输入元素可以在输出数组中多次使用。
提示：
n 在多个输入之间是可变的。
例如
输入数组：[0, 1, 2]
预期输出：
- 000
- 001
- 002
- 010
- 011
- 012
- 020
- 021
022
100
- 101
- 102
- 110
- 111
- 112
- 120
- 121
122
200
- 201
- 202
- 210
- 211
- 212
- 220
- 221
- 222
有 3 * 3 * 3 = 27 种组合，或者通常 n^n 长度为 n 的数组。
问题
- 如何为小输入
n (<=5) 打印这个，可能是递归样式？
- 如何针对大输入
n 有效地打印此内容，而不会在堆栈中溢出，可能只需要一个循环？
例如当n = 9时，有387420489个输出，程序应该能够处理这样的输入。
- 这个问题应该叫什么？这不是典型的排列，因为元素是可重复的。欢迎修改标题。
单循环很难。递归可能是最直观的方法。但这是一个有两个循环的迭代版本，使用 Python 但避免了 itertools 的神奇功能，所以它并不是所有特定于语言的：
a = [0]*n
while(True):
for i in range(n):
a[i] += 1
if a[i] == n:
a[i] = 0
else:
break
else:
break
print("".join(map(str, reversed(a))))
想法如下：从右到左索引您的号码（因此 reversed 调用在那里）。增加最右边的数字。只要您在那里达到 n 的限制，就重置为零，但将数字再向左增加一位。这实质上是使用带进位的长加法加 1。当没有进位时退出内循环。当您没有明确退出内部循环时退出外部循环，即当您对所有数字都有进位时。
在 https://ideone.com/n0ScW8 测试 运行。
实际上，现在我再次查看代码，我看到了一种使用单个循环的方法，并避免了 Python 的 for-else 结构，它在其他一些语言中没有明显的对应结构。这次让我们使用 JavaScript 进行更改。
a = Array.from(Array(n), x=>0);
i = n - 1;
while (i >= 0) {
a[i]++;
if (a[i] == n) {
a[i] = 0;
i--;
} else {
console.log(a.join(""));
i = n - 1;
}
}
请注意，这两个版本都省略了初始的 000…0 解，因此它们都是短解。很容易预先添加。另请注意，我误解了这个问题，所以我假设一个数字数组 0 到 n-1，而实际上您要求的是任意输入。但是一个简单的间接会将一个变成另一个，所以我把它留作练习。
我写了一个 Java 实现，其中包括几个算法：
- 基数转换.
- 迭代 （根据@MvG的回答，来自这个问题：
） .
- 递归 （根据@MBo 的回答，来自另一个问题：
） .
代码 - 实现
CartesianPower.java:
import java.util.Arrays;
/**
* Cartesian power of n elements.
* <h2>Refer:</h2>
* <li><a href="">Original question, with radix & iteration solution.</a>
* <li><a href="">Additional question, with recursion solution.</a>
*
* <h2>Algorithms:</h2>
* <li><b>Radix</b>: intuitive, but not very efficient,
* <li><b>Iteration</b>: best choice, most efficient & scalable,
* <li><b>Recursion</b>: elegant, but not very intuitive, and performance is bad (or even stack overflow) for large input size,
* <li>
*
* @author eric
* @date Oct 25, 2018 4:53:34 PM
*/
public class CartesianPower {
public static final int MIN_ARR_LEN = 2; // min length of input array ,
public static final int MAX_ARR_LEN = 10; // max length of input array,
public static final int ARR_PRINT_LEN_LIMIT = 6; // max array length, that is allowed to print detailed output items to console,
/**
* Print cartesian power of array elements, by converting between radix.
* <p>
* time complexity: O(n) for each output item, and O(n^(n+1)) overall.
*
* @param arr
* an array with length between [Character.MIN_RADIX, Character.MAX_RADIX]
* @return count of cartesian, or -1 if radix is out of range,
*/
public static <T> long cartesianPowerViaRadix(T arr[]) {
int len = arr.length; // length of array, also the radix,
// check radix range,
if (len < MIN_ARR_LEN || len > MAX_ARR_LEN) {
System.out.printf("%d is out of range [%d, %d]\n", len, MIN_ARR_LEN, MAX_ARR_LEN);
return -1;
}
long count = 0;
long totalCount = (long) Math.pow(len, len);
T tmpArr[] = Arrays.copyOf(arr, len);
while (count < totalCount) {
String baseStr = Long.toString(count, len);
for (int i = 0; i < baseStr.length(); i++) {
char c = baseStr.charAt(i);
int r = Integer.parseInt(String.valueOf(c), len);
tmpArr[i] = arr[r];
}
for (int i = baseStr.length(); i < len; i++) {
tmpArr[i] = arr[0];
}
printArr(tmpArr);
count++;
}
System.out.printf("input arr: %s, total count: %d\n", Arrays.toString(arr), count);
return count;
}
/**
* Print cartesian power of array elements, by a single iteration.
* <p>
* time complexity:
* <li>When don't print to console
* <p>
* O(1) for each output item, and O(n^n) overall.
* <li>When print to console
* <p>
* O(n) for each output item, and O(n^(n+1)) overall.
*
* @param n
* array length, array is assumed as numbers start from 0 and increase by 1, e.g [0, 1, 2],
* <p>
* it should be within range [CartesianProduct.MIN_ARR_LEN, CartesianProduct.MAX_ARR_LEN]
* @return count of cartesian, or -1 if array length is out of range,
*/
public static long cartesianPowerViaIterationN(int n) {
// check range of array length,
if (n < MIN_ARR_LEN || n > MAX_ARR_LEN) {
System.out.printf("input length [%d] is out of range [%d, %d]\n", n, MIN_ARR_LEN, MAX_ARR_LEN);
return -1;
}
long startTime = System.currentTimeMillis();
long count = 0;
int tmpArr[] = new int[n];
Arrays.fill(tmpArr, 0);
// initial case,
printArr(tmpArr); // all elements as 0,
count++;
int i = n - 1;
while (i >= 0) {
tmpArr[i]++;
if (tmpArr[i] == n) {
tmpArr[i] = 0;
i--;
} else {
printArr(tmpArr);
i = n - 1;
count++;
}
}
long during = (System.currentTimeMillis() - startTime); // during in milliseconds,
System.out.printf("input arr length: %d, total count: %d, during: %d ms\n", n, count, during);
return count;
}
/**
* Print cartesian power of array elements, by a single iteration.
* <p>
* time complexity:
* <li>When don't print to console
* <p>
* O(1) for each output item, and O(n^n) overall.
* <li>When print to console
* <p>
* O(n) for each output item, and O(n^(n+1)) overall.
*
* @param arr
* input array, could be of any type without order requirement,
* <p>
* its length should be within range [CartesianProduct.MIN_ARR_LEN, CartesianProduct.MAX_ARR_LEN]
* @return count of cartesian, or -1 if array length is out of range,
* @return
*/
public static <T> long cartesianPowerViaIteration(T arr[]) {
int n = arr.length;
// check range of array length,
if (n < MIN_ARR_LEN || n > MAX_ARR_LEN) {
System.out.printf("input length [%d] is out of range [%d, %d]\n", n, MIN_ARR_LEN, MAX_ARR_LEN);
return -1;
}
long startTime = System.currentTimeMillis();
long count = 0;
T tmpArr[] = Arrays.copyOf(arr, n); // tmp array,
int idxArr[] = new int[n]; // index mapping array,
Arrays.fill(idxArr, 0); // all indices as 0,
// initial case,
printIndirectionArr(idxArr, arr, tmpArr);
count++;
int i = n - 1;
while (i >= 0) {
idxArr[i]++;
if (idxArr[i] == n) {
idxArr[i] = 0;
i--;
} else {
printIndirectionArr(idxArr, arr, tmpArr);
i = n - 1;
count++;
}
}
long during = (System.currentTimeMillis() - startTime); // during in milliseconds,
System.out.printf("input arr length: %d, total count: %d, during: %d ms\n", n, count, during);
return count;
}
/**
* Print cartesian power of array elements, via recursion, with raw int[] input.
* <p>
* Time complexity: O(1) for each output item, and O(n^n) overall.
*
* @param arr
* @return count of cartesian, or -1 if radix is out of range,
*/
public static <T> long cartesianPowerViaRecursion(int arr[]) {
int n = arr.length;
// check range of array length,
if (n < MIN_ARR_LEN || n > MAX_ARR_LEN) {
System.out.printf("input length [%d] is out of range [%d, %d]\n", n, MIN_ARR_LEN, MAX_ARR_LEN);
return -1;
}
long startTime = System.currentTimeMillis();
int tmpArr[] = Arrays.copyOf(arr, n);
long count = cartesianPowerViaRecursion(arr, tmpArr, 0);
long during = (System.currentTimeMillis() - startTime); // during in milliseconds,
System.out.printf("input arr length: %d, total count: %d, during: %d ms\n", n, count, during);
return count;
}
/**
* Print cartesian power of array elements, via recursion, the inner function, with raw int[] input.
*
* @param arr
* input array,
* @param tmpArr
* tmp array,
* @param t
* current index in tmp array,
* @return count of cartesian,
*/
private static <T> long cartesianPowerViaRecursion(int arr[], int tmpArr[], int t) {
int n = arr.length;
long count = 0;
if (t == n) {
printArr(tmpArr);
count++;
} else {
for (int i = 0; i < n; i++) {
tmpArr[t] = arr[i];
count += cartesianPowerViaRecursion(arr, tmpArr, t + 1);
}
}
return count;
}
/**
* Print cartesian power of array elements, via recursion.
* <p>
* Time complexity: O(1) for each output item, and O(n^n) overall.
*
* @param arr
* @return count of cartesian, or -1 if radix is out of range,
*/
public static <T> long cartesianPowerViaRecursion(T arr[]) {
int n = arr.length;
// check range of array length,
if (n < MIN_ARR_LEN || n > MAX_ARR_LEN) {
System.out.printf("input length [%d] is out of range [%d, %d]\n", n, MIN_ARR_LEN, MAX_ARR_LEN);
return -1;
}
long startTime = System.currentTimeMillis();
T tmpArr[] = Arrays.copyOf(arr, n);
long count = cartesianPowerViaRecursion(arr, tmpArr, 0);
long during = (System.currentTimeMillis() - startTime); // during in milliseconds,
System.out.printf("input arr length: %d, total count: %d, during: %d ms\n", n, count, during);
return count;
}
/**
* Print cartesian power of array elements, via recursion, the inner function.
*
* @param arr
* input array,
* @param tmpArr
* tmp array,
* @param t
* current index in tmp array,
* @return count of cartesian,
*/
private static <T> long cartesianPowerViaRecursion(T arr[], T tmpArr[], int t) {
int n = arr.length;
long count = 0;
if (t == n) {
printArr(tmpArr);
count++;
} else {
for (int i = 0; i < n; i++) {
tmpArr[t] = arr[i];
count += cartesianPowerViaRecursion(arr, tmpArr, t + 1);
}
}
return count;
}
/**
* Print int array, only when length <= limit.
*
* @param arr
* @return boolean, indicate whether printed,
*/
private static boolean printArr(int arr[]) {
if (arr.length > ARR_PRINT_LEN_LIMIT) {
return false;
}
System.out.println(Arrays.toString(arr));
return true;
}
/**
* Print array, only when length <= limit.
*
* @param arr
* @return boolean, indicate whether printed,
*/
private static <T> boolean printArr(T[] arr) {
if (arr.length > ARR_PRINT_LEN_LIMIT) {
return false;
}
System.out.println(Arrays.toString(arr));
return true;
}
/**
* Print indirection array, only when length <= limit.
*
* @param idxArr
* contain index mapping,
* @param arr
* @param tmpArr
* @return boolean, indicate whether printed,
*/
private static <T> boolean printIndirectionArr(int idxArr[], T[] arr, T[] tmpArr) {
if (arr.length > ARR_PRINT_LEN_LIMIT) {
return false;
}
fillArrFromIndex(idxArr, arr, tmpArr); // fill tmp array,
System.out.println(Arrays.toString(tmpArr));
return true;
}
/**
* Fill tmp array with elements from array, according to index mapping.
*
* @param idxArr
* contain index mapping,
* @param arr
* @param tmpArr
*/
private static <T> void fillArrFromIndex(int idxArr[], T[] arr, T[] tmpArr) {
for (int i = 0; i < idxArr.length; i++) {
tmpArr[i] = arr[idxArr[i]];
}
}
}
提示：
- 数组长度范围为
[2, 10]，避免运行过长。
- 只有当数组长度<=6时，才会打印详细输出，否则只打印摘要。
代码-测试用例
（所有测试用例都使用TestNG）
CartesianPowerRadixTest.java:
(测试用例-基数算法)
import org.testng.Assert;
import org.testng.annotations.Test;
/**
* CartesianPower radix - test.
*
* @author eric
* @date Oct 25, 2018 5:04:54 PM
*/
public class CartesianPowerRadixTest {
@Test
public void testOrderedNum() {
Integer arr[] = new Integer[] { 0, 1, 2 }; // len = 3,
Assert.assertEquals(CartesianPower.cartesianPowerViaRadix(arr), 27);
}
@Test
public void testRandomNum() {
Integer arr2[] = new Integer[] { 0, 2, 1 }; // len = 3,
Assert.assertEquals(CartesianPower.cartesianPowerViaRadix(arr2), 27);
}
@Test
public void testChar() {
Character charArr[] = new Character[] { 'a', 'b', 'c' }; // len = 3,
Assert.assertEquals(CartesianPower.cartesianPowerViaRadix(charArr), 27);
}
@Test
public void testObject() {
Object objectArr[] = new Object[] { 0, 'g', true }; // len = 3,
Assert.assertEquals(CartesianPower.cartesianPowerViaRadix(objectArr), 27);
}
@Test
public void testOutOfRange() {
Object tooShortArr[] = new Object[] { 1 }; // len = 1,
Assert.assertEquals(CartesianPower.cartesianPowerViaRadix(tooShortArr), -1);
Object tooLongArr[] = new Object[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30,
31, 32, 33, 34, 35, 36, 37, 38, 39 }; // len = 40,
Assert.assertEquals(CartesianPower.cartesianPowerViaRadix(tooLongArr), -1);
}
}
CartesianPowerIterationNTest.java:
(测试用例-迭代算法-输入长度为n，假设数组为int数组，从0开始增加1)
import org.testng.Assert;
import org.testng.annotations.Test;
/**
* CartesianPower iteration N - test.
*
* @author eric
* @date Oct 26, 2018 1:44:01 PM
*/
public class CartesianPowerIterationNTest {
@Test
public void testSmall() {
int len = 3;
Assert.assertEquals(CartesianPower.cartesianPowerViaIterationN(len), 27);
}
@Test
public void testLarge() {
int len = 9;
Assert.assertEquals(CartesianPower.cartesianPowerViaIterationN(len), 387420489);
}
@Test
public void testOutOfRange() {
int tooShortLen = CartesianPower.MIN_ARR_LEN - 1;
Assert.assertEquals(CartesianPower.cartesianPowerViaIterationN(tooShortLen), -1);
int tooLongLen = CartesianPower.MAX_ARR_LEN + 1;
Assert.assertEquals(CartesianPower.cartesianPowerViaIterationN(tooLongLen), -1);
}
}
CartesianPowerIterationArrTest.java:
(测试用例-用于迭代算法-输入数组是无顺序要求的任何类型)
import org.testng.Assert;
import org.testng.annotations.Test;
/**
* CartesianPower iteration array - test.
*
* @author eric
* @date Oct 26, 2018 2:48:50 PM
*/
public class CartesianPowerIterationArrTest {
@Test
public void testOrderedNum() {
Integer arr[] = new Integer[] { 0, 1, 2 }; // len = 3,
Assert.assertEquals(CartesianPower.cartesianPowerViaIteration(arr), 27);
}
@Test
public void testRandomNum() {
Integer arr2[] = new Integer[] { 0, 2, 1 }; // len = 3,
Assert.assertEquals(CartesianPower.cartesianPowerViaIteration(arr2), 27);
}
@Test
public void testChar() {
Character charArr[] = new Character[] { 'a', 'b', 'c' }; // len = 3,
Assert.assertEquals(CartesianPower.cartesianPowerViaIteration(charArr), 27);
}
@Test
public void testObject() {
Object objectArr[] = new Object[] { 0, 'g', true }; // len = 3,
Assert.assertEquals(CartesianPower.cartesianPowerViaIteration(objectArr), 27);
}
@Test
public void testLarge() {
Object arr[] = new Object[] { 1, 0, 2, 'c', 'a', 'b', true, false, null }; // len = 9,
Assert.assertEquals(CartesianPower.cartesianPowerViaIteration(arr), 387420489);
// Object arr2[] = new Object[] { 1, 0, 2, 'c', 'a', 'b', true, false, null, new Object() }; // len = 10,
// Assert.assertEquals(CartesianProduct.cartesianViaLoopArr(arr2), 10000000000L);
}
@Test
public void testOutOfRange() {
Object tooShortArr[] = new Object[] { 1 }; // len = 1,
Assert.assertEquals(CartesianPower.cartesianPowerViaIteration(tooShortArr), -1);
Object tooLongArr[] = new Object[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30,
31, 32, 33, 34, 35, 36, 37, 38, 39 }; // len = 40,
Assert.assertEquals(CartesianPower.cartesianPowerViaIteration(tooLongArr), -1);
}
}
CartesianPowerRecursiveRawTest.java:
(测试用例 - 对于递归算法 - 输入数组是 int[] 类型)
import org.testng.Assert;
import org.testng.annotations.Test;
/**
* CartesianPower recursion array - raw int[] input - test.
*
* @author eric
* @date Oct 27, 2018 4:09:18 AM
*/
public class CartesianPowerRecursiveRawTest {
@Test
public void testOrderedNum() {
int arr[] = new int[] { 0, 1, 2 }; // len = 3
Assert.assertEquals(CartesianPower.cartesianPowerViaRecursion(arr), 27);
}
@Test
public void testRandomNum() {
int arr2[] = new int[] { 0, 2, 1 }; // len = 3,
Assert.assertEquals(CartesianPower.cartesianPowerViaRecursion(arr2), 27);
}
@Test
public void testLarge() {
int arr[] = new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8 }; // len = 9,
Assert.assertEquals(CartesianPower.cartesianPowerViaRecursion(arr), 387420489);
// int arr2[] = new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }; // len = 10,
// Assert.assertEquals(CartesianPower.cartesianViaRecursion(arr2), 10000000000L);
}
@Test
public void testOutOfRange() {
int tooShortArr[] = new int[] { 1 }; // len = 1,
Assert.assertEquals(CartesianPower.cartesianPowerViaRecursion(tooShortArr), -1);
int tooLongArr[] = new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32,
33, 34, 35, 36, 37, 38, 39 }; // len = 40,
Assert.assertEquals(CartesianPower.cartesianPowerViaRecursion(tooLongArr), -1);
}
}
CartesianPowerRecursiveTest.java:
(测试用例 - 对于递归算法 - 输入数组是通用类型 T[])
import org.testng.Assert;
import org.testng.annotations.Test;
/**
* CartesianPower recursion array - test.
*
* @author eric
* @date Oct 26, 2018 11:45:27 PM
*/
public class CartesianPowerRecursiveTest {
@Test
public void testOrderedNum() {
Integer arr[] = new Integer[] { 0, 1, 2 };
Assert.assertEquals(CartesianPower.cartesianPowerViaRecursion(arr), 27);
}
@Test
public void testRandomNum() {
Integer arr2[] = new Integer[] { 0, 2, 1 }; // len = 3,
Assert.assertEquals(CartesianPower.cartesianPowerViaRecursion(arr2), 27);
}
@Test
public void testChar() {
Character charArr[] = new Character[] { 'a', 'b', 'c' }; // len = 3,
Assert.assertEquals(CartesianPower.cartesianPowerViaRecursion(charArr), 27);
}
@Test
public void testObject() {
Object objectArr[] = new Object[] { 0, 'g', true }; // len = 3,
Assert.assertEquals(CartesianPower.cartesianPowerViaRecursion(objectArr), 27);
}
@Test
public void testLarge() {
Object arr[] = new Object[] { 1, 0, 2, 'c', 'a', 'b', true, false, null }; // len = 9,
Assert.assertEquals(CartesianPower.cartesianPowerViaRecursion(arr), 387420489);
// Object arr2[] = new Object[] { 1, 0, 2, 'c', 'a', 'b', true, false, null, new Object() }; // len = 10,
// Assert.assertEquals(CartesianProduct.cartesianViaRecursion(arr2), 10000000000L);
}
@Test
public void testOutOfRange() {
Object tooShortArr[] = new Object[] { 1 }; // len = 1,
Assert.assertEquals(CartesianPower.cartesianPowerViaRecursion(tooShortArr), -1);
Object tooLongArr[] = new Object[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30,
31, 32, 33, 34, 35, 36, 37, 38, 39 }; // len = 40,
Assert.assertEquals(CartesianPower.cartesianPowerViaRecursion(tooLongArr), -1);
}
}
输入:
有一个长度为 n.
输出：
并且想打印所有可能的相同长度的数组 n 由输入数组中的元素组成，每个输入元素可以在输出数组中多次使用。
提示：
n在多个输入之间是可变的。
例如
输入数组：[0, 1, 2]
预期输出：
- 000
- 001
- 002
- 010
- 011
- 012
- 020
- 021
022
100
- 101
- 102
- 110
- 111
- 112
- 120
- 121
122
200
- 201
- 202
- 210
- 211
- 212
- 220
- 221
- 222
有 3 * 3 * 3 = 27 种组合，或者通常 n^n 长度为 n 的数组。
问题
- 如何为小输入
n(<=5) 打印这个，可能是递归样式？ - 如何针对大输入
n有效地打印此内容，而不会在堆栈中溢出，可能只需要一个循环？
例如当n = 9时，有387420489个输出，程序应该能够处理这样的输入。 - 这个问题应该叫什么？这不是典型的排列，因为元素是可重复的。欢迎修改标题。
单循环很难。递归可能是最直观的方法。但这是一个有两个循环的迭代版本，使用 Python 但避免了 itertools 的神奇功能，所以它并不是所有特定于语言的：
a = [0]*n
while(True):
for i in range(n):
a[i] += 1
if a[i] == n:
a[i] = 0
else:
break
else:
break
print("".join(map(str, reversed(a))))
想法如下：从右到左索引您的号码（因此 reversed 调用在那里）。增加最右边的数字。只要您在那里达到 n 的限制，就重置为零，但将数字再向左增加一位。这实质上是使用带进位的长加法加 1。当没有进位时退出内循环。当您没有明确退出内部循环时退出外部循环，即当您对所有数字都有进位时。
在 https://ideone.com/n0ScW8 测试 运行。
实际上，现在我再次查看代码，我看到了一种使用单个循环的方法，并避免了 Python 的 for-else 结构，它在其他一些语言中没有明显的对应结构。这次让我们使用 JavaScript 进行更改。
a = Array.from(Array(n), x=>0);
i = n - 1;
while (i >= 0) {
a[i]++;
if (a[i] == n) {
a[i] = 0;
i--;
} else {
console.log(a.join(""));
i = n - 1;
}
}
请注意，这两个版本都省略了初始的 000…0 解，因此它们都是短解。很容易预先添加。另请注意，我误解了这个问题，所以我假设一个数字数组 0 到 n-1，而实际上您要求的是任意输入。但是一个简单的间接会将一个变成另一个，所以我把它留作练习。
我写了一个 Java 实现，其中包括几个算法：
- 基数转换.
- 迭代 （根据@MvG的回答，来自这个问题：
- 递归 （根据@MBo 的回答，来自另一个问题：
代码 - 实现
CartesianPower.java:
import java.util.Arrays;
/**
* Cartesian power of n elements.
* <h2>Refer:</h2>
* <li><a href="">Original question, with radix & iteration solution.</a>
* <li><a href="">Additional question, with recursion solution.</a>
*
* <h2>Algorithms:</h2>
* <li><b>Radix</b>: intuitive, but not very efficient,
* <li><b>Iteration</b>: best choice, most efficient & scalable,
* <li><b>Recursion</b>: elegant, but not very intuitive, and performance is bad (or even stack overflow) for large input size,
* <li>
*
* @author eric
* @date Oct 25, 2018 4:53:34 PM
*/
public class CartesianPower {
public static final int MIN_ARR_LEN = 2; // min length of input array ,
public static final int MAX_ARR_LEN = 10; // max length of input array,
public static final int ARR_PRINT_LEN_LIMIT = 6; // max array length, that is allowed to print detailed output items to console,
/**
* Print cartesian power of array elements, by converting between radix.
* <p>
* time complexity: O(n) for each output item, and O(n^(n+1)) overall.
*
* @param arr
* an array with length between [Character.MIN_RADIX, Character.MAX_RADIX]
* @return count of cartesian, or -1 if radix is out of range,
*/
public static <T> long cartesianPowerViaRadix(T arr[]) {
int len = arr.length; // length of array, also the radix,
// check radix range,
if (len < MIN_ARR_LEN || len > MAX_ARR_LEN) {
System.out.printf("%d is out of range [%d, %d]\n", len, MIN_ARR_LEN, MAX_ARR_LEN);
return -1;
}
long count = 0;
long totalCount = (long) Math.pow(len, len);
T tmpArr[] = Arrays.copyOf(arr, len);
while (count < totalCount) {
String baseStr = Long.toString(count, len);
for (int i = 0; i < baseStr.length(); i++) {
char c = baseStr.charAt(i);
int r = Integer.parseInt(String.valueOf(c), len);
tmpArr[i] = arr[r];
}
for (int i = baseStr.length(); i < len; i++) {
tmpArr[i] = arr[0];
}
printArr(tmpArr);
count++;
}
System.out.printf("input arr: %s, total count: %d\n", Arrays.toString(arr), count);
return count;
}
/**
* Print cartesian power of array elements, by a single iteration.
* <p>
* time complexity:
* <li>When don't print to console
* <p>
* O(1) for each output item, and O(n^n) overall.
* <li>When print to console
* <p>
* O(n) for each output item, and O(n^(n+1)) overall.
*
* @param n
* array length, array is assumed as numbers start from 0 and increase by 1, e.g [0, 1, 2],
* <p>
* it should be within range [CartesianProduct.MIN_ARR_LEN, CartesianProduct.MAX_ARR_LEN]
* @return count of cartesian, or -1 if array length is out of range,
*/
public static long cartesianPowerViaIterationN(int n) {
// check range of array length,
if (n < MIN_ARR_LEN || n > MAX_ARR_LEN) {
System.out.printf("input length [%d] is out of range [%d, %d]\n", n, MIN_ARR_LEN, MAX_ARR_LEN);
return -1;
}
long startTime = System.currentTimeMillis();
long count = 0;
int tmpArr[] = new int[n];
Arrays.fill(tmpArr, 0);
// initial case,
printArr(tmpArr); // all elements as 0,
count++;
int i = n - 1;
while (i >= 0) {
tmpArr[i]++;
if (tmpArr[i] == n) {
tmpArr[i] = 0;
i--;
} else {
printArr(tmpArr);
i = n - 1;
count++;
}
}
long during = (System.currentTimeMillis() - startTime); // during in milliseconds,
System.out.printf("input arr length: %d, total count: %d, during: %d ms\n", n, count, during);
return count;
}
/**
* Print cartesian power of array elements, by a single iteration.
* <p>
* time complexity:
* <li>When don't print to console
* <p>
* O(1) for each output item, and O(n^n) overall.
* <li>When print to console
* <p>
* O(n) for each output item, and O(n^(n+1)) overall.
*
* @param arr
* input array, could be of any type without order requirement,
* <p>
* its length should be within range [CartesianProduct.MIN_ARR_LEN, CartesianProduct.MAX_ARR_LEN]
* @return count of cartesian, or -1 if array length is out of range,
* @return
*/
public static <T> long cartesianPowerViaIteration(T arr[]) {
int n = arr.length;
// check range of array length,
if (n < MIN_ARR_LEN || n > MAX_ARR_LEN) {
System.out.printf("input length [%d] is out of range [%d, %d]\n", n, MIN_ARR_LEN, MAX_ARR_LEN);
return -1;
}
long startTime = System.currentTimeMillis();
long count = 0;
T tmpArr[] = Arrays.copyOf(arr, n); // tmp array,
int idxArr[] = new int[n]; // index mapping array,
Arrays.fill(idxArr, 0); // all indices as 0,
// initial case,
printIndirectionArr(idxArr, arr, tmpArr);
count++;
int i = n - 1;
while (i >= 0) {
idxArr[i]++;
if (idxArr[i] == n) {
idxArr[i] = 0;
i--;
} else {
printIndirectionArr(idxArr, arr, tmpArr);
i = n - 1;
count++;
}
}
long during = (System.currentTimeMillis() - startTime); // during in milliseconds,
System.out.printf("input arr length: %d, total count: %d, during: %d ms\n", n, count, during);
return count;
}
/**
* Print cartesian power of array elements, via recursion, with raw int[] input.
* <p>
* Time complexity: O(1) for each output item, and O(n^n) overall.
*
* @param arr
* @return count of cartesian, or -1 if radix is out of range,
*/
public static <T> long cartesianPowerViaRecursion(int arr[]) {
int n = arr.length;
// check range of array length,
if (n < MIN_ARR_LEN || n > MAX_ARR_LEN) {
System.out.printf("input length [%d] is out of range [%d, %d]\n", n, MIN_ARR_LEN, MAX_ARR_LEN);
return -1;
}
long startTime = System.currentTimeMillis();
int tmpArr[] = Arrays.copyOf(arr, n);
long count = cartesianPowerViaRecursion(arr, tmpArr, 0);
long during = (System.currentTimeMillis() - startTime); // during in milliseconds,
System.out.printf("input arr length: %d, total count: %d, during: %d ms\n", n, count, during);
return count;
}
/**
* Print cartesian power of array elements, via recursion, the inner function, with raw int[] input.
*
* @param arr
* input array,
* @param tmpArr
* tmp array,
* @param t
* current index in tmp array,
* @return count of cartesian,
*/
private static <T> long cartesianPowerViaRecursion(int arr[], int tmpArr[], int t) {
int n = arr.length;
long count = 0;
if (t == n) {
printArr(tmpArr);
count++;
} else {
for (int i = 0; i < n; i++) {
tmpArr[t] = arr[i];
count += cartesianPowerViaRecursion(arr, tmpArr, t + 1);
}
}
return count;
}
/**
* Print cartesian power of array elements, via recursion.
* <p>
* Time complexity: O(1) for each output item, and O(n^n) overall.
*
* @param arr
* @return count of cartesian, or -1 if radix is out of range,
*/
public static <T> long cartesianPowerViaRecursion(T arr[]) {
int n = arr.length;
// check range of array length,
if (n < MIN_ARR_LEN || n > MAX_ARR_LEN) {
System.out.printf("input length [%d] is out of range [%d, %d]\n", n, MIN_ARR_LEN, MAX_ARR_LEN);
return -1;
}
long startTime = System.currentTimeMillis();
T tmpArr[] = Arrays.copyOf(arr, n);
long count = cartesianPowerViaRecursion(arr, tmpArr, 0);
long during = (System.currentTimeMillis() - startTime); // during in milliseconds,
System.out.printf("input arr length: %d, total count: %d, during: %d ms\n", n, count, during);
return count;
}
/**
* Print cartesian power of array elements, via recursion, the inner function.
*
* @param arr
* input array,
* @param tmpArr
* tmp array,
* @param t
* current index in tmp array,
* @return count of cartesian,
*/
private static <T> long cartesianPowerViaRecursion(T arr[], T tmpArr[], int t) {
int n = arr.length;
long count = 0;
if (t == n) {
printArr(tmpArr);
count++;
} else {
for (int i = 0; i < n; i++) {
tmpArr[t] = arr[i];
count += cartesianPowerViaRecursion(arr, tmpArr, t + 1);
}
}
return count;
}
/**
* Print int array, only when length <= limit.
*
* @param arr
* @return boolean, indicate whether printed,
*/
private static boolean printArr(int arr[]) {
if (arr.length > ARR_PRINT_LEN_LIMIT) {
return false;
}
System.out.println(Arrays.toString(arr));
return true;
}
/**
* Print array, only when length <= limit.
*
* @param arr
* @return boolean, indicate whether printed,
*/
private static <T> boolean printArr(T[] arr) {
if (arr.length > ARR_PRINT_LEN_LIMIT) {
return false;
}
System.out.println(Arrays.toString(arr));
return true;
}
/**
* Print indirection array, only when length <= limit.
*
* @param idxArr
* contain index mapping,
* @param arr
* @param tmpArr
* @return boolean, indicate whether printed,
*/
private static <T> boolean printIndirectionArr(int idxArr[], T[] arr, T[] tmpArr) {
if (arr.length > ARR_PRINT_LEN_LIMIT) {
return false;
}
fillArrFromIndex(idxArr, arr, tmpArr); // fill tmp array,
System.out.println(Arrays.toString(tmpArr));
return true;
}
/**
* Fill tmp array with elements from array, according to index mapping.
*
* @param idxArr
* contain index mapping,
* @param arr
* @param tmpArr
*/
private static <T> void fillArrFromIndex(int idxArr[], T[] arr, T[] tmpArr) {
for (int i = 0; i < idxArr.length; i++) {
tmpArr[i] = arr[idxArr[i]];
}
}
}
提示：
- 数组长度范围为
[2, 10]，避免运行过长。 - 只有当数组长度<=6时，才会打印详细输出，否则只打印摘要。
代码-测试用例
（所有测试用例都使用TestNG）
CartesianPowerRadixTest.java:
(测试用例-基数算法)
import org.testng.Assert;
import org.testng.annotations.Test;
/**
* CartesianPower radix - test.
*
* @author eric
* @date Oct 25, 2018 5:04:54 PM
*/
public class CartesianPowerRadixTest {
@Test
public void testOrderedNum() {
Integer arr[] = new Integer[] { 0, 1, 2 }; // len = 3,
Assert.assertEquals(CartesianPower.cartesianPowerViaRadix(arr), 27);
}
@Test
public void testRandomNum() {
Integer arr2[] = new Integer[] { 0, 2, 1 }; // len = 3,
Assert.assertEquals(CartesianPower.cartesianPowerViaRadix(arr2), 27);
}
@Test
public void testChar() {
Character charArr[] = new Character[] { 'a', 'b', 'c' }; // len = 3,
Assert.assertEquals(CartesianPower.cartesianPowerViaRadix(charArr), 27);
}
@Test
public void testObject() {
Object objectArr[] = new Object[] { 0, 'g', true }; // len = 3,
Assert.assertEquals(CartesianPower.cartesianPowerViaRadix(objectArr), 27);
}
@Test
public void testOutOfRange() {
Object tooShortArr[] = new Object[] { 1 }; // len = 1,
Assert.assertEquals(CartesianPower.cartesianPowerViaRadix(tooShortArr), -1);
Object tooLongArr[] = new Object[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30,
31, 32, 33, 34, 35, 36, 37, 38, 39 }; // len = 40,
Assert.assertEquals(CartesianPower.cartesianPowerViaRadix(tooLongArr), -1);
}
}
CartesianPowerIterationNTest.java:
(测试用例-迭代算法-输入长度为n，假设数组为int数组，从0开始增加1)
import org.testng.Assert;
import org.testng.annotations.Test;
/**
* CartesianPower iteration N - test.
*
* @author eric
* @date Oct 26, 2018 1:44:01 PM
*/
public class CartesianPowerIterationNTest {
@Test
public void testSmall() {
int len = 3;
Assert.assertEquals(CartesianPower.cartesianPowerViaIterationN(len), 27);
}
@Test
public void testLarge() {
int len = 9;
Assert.assertEquals(CartesianPower.cartesianPowerViaIterationN(len), 387420489);
}
@Test
public void testOutOfRange() {
int tooShortLen = CartesianPower.MIN_ARR_LEN - 1;
Assert.assertEquals(CartesianPower.cartesianPowerViaIterationN(tooShortLen), -1);
int tooLongLen = CartesianPower.MAX_ARR_LEN + 1;
Assert.assertEquals(CartesianPower.cartesianPowerViaIterationN(tooLongLen), -1);
}
}
CartesianPowerIterationArrTest.java:
(测试用例-用于迭代算法-输入数组是无顺序要求的任何类型)
import org.testng.Assert;
import org.testng.annotations.Test;
/**
* CartesianPower iteration array - test.
*
* @author eric
* @date Oct 26, 2018 2:48:50 PM
*/
public class CartesianPowerIterationArrTest {
@Test
public void testOrderedNum() {
Integer arr[] = new Integer[] { 0, 1, 2 }; // len = 3,
Assert.assertEquals(CartesianPower.cartesianPowerViaIteration(arr), 27);
}
@Test
public void testRandomNum() {
Integer arr2[] = new Integer[] { 0, 2, 1 }; // len = 3,
Assert.assertEquals(CartesianPower.cartesianPowerViaIteration(arr2), 27);
}
@Test
public void testChar() {
Character charArr[] = new Character[] { 'a', 'b', 'c' }; // len = 3,
Assert.assertEquals(CartesianPower.cartesianPowerViaIteration(charArr), 27);
}
@Test
public void testObject() {
Object objectArr[] = new Object[] { 0, 'g', true }; // len = 3,
Assert.assertEquals(CartesianPower.cartesianPowerViaIteration(objectArr), 27);
}
@Test
public void testLarge() {
Object arr[] = new Object[] { 1, 0, 2, 'c', 'a', 'b', true, false, null }; // len = 9,
Assert.assertEquals(CartesianPower.cartesianPowerViaIteration(arr), 387420489);
// Object arr2[] = new Object[] { 1, 0, 2, 'c', 'a', 'b', true, false, null, new Object() }; // len = 10,
// Assert.assertEquals(CartesianProduct.cartesianViaLoopArr(arr2), 10000000000L);
}
@Test
public void testOutOfRange() {
Object tooShortArr[] = new Object[] { 1 }; // len = 1,
Assert.assertEquals(CartesianPower.cartesianPowerViaIteration(tooShortArr), -1);
Object tooLongArr[] = new Object[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30,
31, 32, 33, 34, 35, 36, 37, 38, 39 }; // len = 40,
Assert.assertEquals(CartesianPower.cartesianPowerViaIteration(tooLongArr), -1);
}
}
CartesianPowerRecursiveRawTest.java:
(测试用例 - 对于递归算法 - 输入数组是 int[] 类型)
import org.testng.Assert;
import org.testng.annotations.Test;
/**
* CartesianPower recursion array - raw int[] input - test.
*
* @author eric
* @date Oct 27, 2018 4:09:18 AM
*/
public class CartesianPowerRecursiveRawTest {
@Test
public void testOrderedNum() {
int arr[] = new int[] { 0, 1, 2 }; // len = 3
Assert.assertEquals(CartesianPower.cartesianPowerViaRecursion(arr), 27);
}
@Test
public void testRandomNum() {
int arr2[] = new int[] { 0, 2, 1 }; // len = 3,
Assert.assertEquals(CartesianPower.cartesianPowerViaRecursion(arr2), 27);
}
@Test
public void testLarge() {
int arr[] = new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8 }; // len = 9,
Assert.assertEquals(CartesianPower.cartesianPowerViaRecursion(arr), 387420489);
// int arr2[] = new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }; // len = 10,
// Assert.assertEquals(CartesianPower.cartesianViaRecursion(arr2), 10000000000L);
}
@Test
public void testOutOfRange() {
int tooShortArr[] = new int[] { 1 }; // len = 1,
Assert.assertEquals(CartesianPower.cartesianPowerViaRecursion(tooShortArr), -1);
int tooLongArr[] = new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32,
33, 34, 35, 36, 37, 38, 39 }; // len = 40,
Assert.assertEquals(CartesianPower.cartesianPowerViaRecursion(tooLongArr), -1);
}
}
CartesianPowerRecursiveTest.java:
(测试用例 - 对于递归算法 - 输入数组是通用类型 T[])
import org.testng.Assert;
import org.testng.annotations.Test;
/**
* CartesianPower recursion array - test.
*
* @author eric
* @date Oct 26, 2018 11:45:27 PM
*/
public class CartesianPowerRecursiveTest {
@Test
public void testOrderedNum() {
Integer arr[] = new Integer[] { 0, 1, 2 };
Assert.assertEquals(CartesianPower.cartesianPowerViaRecursion(arr), 27);
}
@Test
public void testRandomNum() {
Integer arr2[] = new Integer[] { 0, 2, 1 }; // len = 3,
Assert.assertEquals(CartesianPower.cartesianPowerViaRecursion(arr2), 27);
}
@Test
public void testChar() {
Character charArr[] = new Character[] { 'a', 'b', 'c' }; // len = 3,
Assert.assertEquals(CartesianPower.cartesianPowerViaRecursion(charArr), 27);
}
@Test
public void testObject() {
Object objectArr[] = new Object[] { 0, 'g', true }; // len = 3,
Assert.assertEquals(CartesianPower.cartesianPowerViaRecursion(objectArr), 27);
}
@Test
public void testLarge() {
Object arr[] = new Object[] { 1, 0, 2, 'c', 'a', 'b', true, false, null }; // len = 9,
Assert.assertEquals(CartesianPower.cartesianPowerViaRecursion(arr), 387420489);
// Object arr2[] = new Object[] { 1, 0, 2, 'c', 'a', 'b', true, false, null, new Object() }; // len = 10,
// Assert.assertEquals(CartesianProduct.cartesianViaRecursion(arr2), 10000000000L);
}
@Test
public void testOutOfRange() {
Object tooShortArr[] = new Object[] { 1 }; // len = 1,
Assert.assertEquals(CartesianPower.cartesianPowerViaRecursion(tooShortArr), -1);
Object tooLongArr[] = new Object[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30,
31, 32, 33, 34, 35, 36, 37, 38, 39 }; // len = 40,
Assert.assertEquals(CartesianPower.cartesianPowerViaRecursion(tooLongArr), -1);
}
}