algorithm - 笛卡尔幂 - 通过递归

Question

原题在这里:Cartesian power (a special Cartesian product) -- choose elements from array, in repeatable style

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

我想知道是否有一个递归解决方案，类似于来自以下链接的解决方案，它使用递归打印排列: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 静态/非静态等):

编辑:制作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);
      }
}

Working Python代码:

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