笛卡尔幂 - 通过递归

Question

原题在这里：

老问题中已经有答案通过迭代给出了解决方案。

我想知道是否有递归解决方案，类似于以下 link 的解决方案，它打印递归排列：https://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/

目前我写了如下程序，还不正确，有帮助吗？

代码 - 实现

CartesianPowerRecursive.java:

import java.util.Arrays;

/**
 * Print cartesian power of array elements, by recursion.
 * 
 * @author eric
 * @date Oct 13, 2018 12:28:10 PM
 */
public class CartesianPowerRecursive {
    public static int cartesianPower(int arr[]) {
        int tmpArr[] = Arrays.copyOf(arr, arr.length);
        return cartesianPower(arr, tmpArr, 0, 0);
    }

    private static int cartesianPower(int arr[], int tmpArr[], int n, int m) {
        // FIXME ... not correct yet,

        int counter = 0;
        for (int i = n; i < arr.length; i++) {
            for (int j = m; j < arr.length; j++) {
                tmpArr[j] = arr[i];
                counter += cartesianPower(arr, tmpArr, n, j + 1);
            }
        }

        if (m == arr.length - 1) {
            counter++;
            System.out.println(Arrays.toString(tmpArr));
        }

        return counter;
    }
}

代码-测试用例

（通过 TestNG）

CartesianPowerRecursiveTest.java:

import org.testng.Assert;
import org.testng.annotations.Test;

/**
 * CartesianPowerRecursive test.
 * 
 * @author eric
 * @date Oct 26, 2018 11:45:27 PM
 */
public class CartesianPowerRecursiveTest {
    @Test
    public void test() {
        int arr[] = new int[] { 0, 1, 2 };
        Assert.assertEquals(CartesianPowerRecursive.cartesianPower(arr), 27);
    }
}

Answer 1

递归的方法很简单。伪代码（不确定如何处理 Java static/non-static 等）：

编辑：制作 if (m < 0)

public static void cartesianPower(int arr[], int tmpArr[], int n, int m){
    if (m < 0)
       System.out.println(Arrays.toString(tmpArr));
    else
      for (int i = 0; i < n; i++) {
        tmpArr[m] = arr[i];
        cartesianPower(arr, tmpArr, n, m - 1);
      }
}

WorkingPython代码：

def cartesianPower(arr, tmpArr, n, m):
    if (m < 0):
        print(tmpArr)
    else:
        for i in range(n):
            tmpArr[m] = arr[i]
            cartesianPower(arr, tmpArr, n, m - 1)

arr = [0,1,2]
tmpArr = [0,0,0]
cartesianPower(arr, tmpArr, len(arr), len(arr) - 1)

Version with lexicographic ordering

笛卡尔幂 - 通过递归

Cartesian power - via recursion

algorithm

math

recursion

permutation

cartesian-product

代码 - 实现

代码-测试用例