Декартова сила - через рекурсию

Question

Оригинальный вопрос здесь: Декартова сила (специальный декартовский продукт) - выберите элементы из массива, в повторяемом стиле

В старом вопросе уже есть ответы, которые далирешение с помощью итерации.

Мне интересно, существует ли рекурсивное решение, аналогичное решению по следующей ссылке, которое печатает перестановки с рекурсией: 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);
      }
}

Рабочий Код 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)

Версия с лексикографическим порядком