代码之家 › 专栏 › 技术社区 › Eric

笛卡尔幂-通过递归

cartesian-product permutation recursion math algorithm

Eric · 技术社区 · 7 年前

最初的问题是: 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/

目前我已经写了以下程序,这是不正确的还没有,任何帮助?

代码-实现

CartesianPower递归.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;
    }
}

代码-测试用例

(通过测试

CartesianPower递归测试.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);
    }
}

1 回复 | 直到 7 年前

MBo 7 年前

递归方法非常简单。伪代码(不确定如何处理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

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