Java：从输入字符串数组生成 nCr 数组并返回它

Question

我想从输入数组返回所有可能组合的完整数组。我想生成 n 选择 k 组合，其中 k=1 到 n。到目前为止我一直非常不成功。

static void combinationUtil(String[] arr, String data[], int start, int end, int index, int r, float[][] info) {

        // Current combination is ready to be printed, print it

        strat newStrat = new strat(0, 0, 0, null);

        if (index == r) {

            //THIS IS WHERE THE COMBINATION I WANT APPEARS

            return;

        }

        for (int i = start; i <= end && end - i + 1 >= r - index; i++) {

            data[index] = arr[i];

            combinationUtil(arr, data, i + 1, end, index + 1, r, info);

        }

        return;

    }

public static void getCombinations(String[] arr, int n, int r, float[][] info) {

        String[] data = new String[r];

        combinationUtil(arr, data, 0, n - 1, 0, r, info);

    }

public static void main(String[] args) throws IOException, InterruptedException {

        //Array I want to get all k 1:n combinations of

        String[] array = { "TST1", "TST2", "TST3"} 

        //start a timer because that's always fun

        long startTime = System.nanoTime();

        //cycle through all 'pick k values'

        for (int i = 1; i < 8; i++) {

            getCombinations(array, n, i, info);

        }

        //Math's up. How Long did that take?

        long endTime = System.nanoTime();

        //IDEALLY PRINT THE COMBINATIONAL ARRAY HERE

        System.out.println(Arrays.deepToString(_____));

        //Don't forget to print the time ;)

        System.out.println("Duration: "+(endTime - startTime)+" ns");

    }

我已经尝试了所有我能想到的方法和谷歌。从将“data”数组传递给函数，将其与其先前的自身连接，将旧数组复制到新数组，其中最新索引是最新的“data”，ArrayLists，Stacks，.push()，.add() ，获取可能组合的总数并将它们插入到全局数组索引中...什么都没有...我被烧毁了..当然理想情况下结果将如下所示：

[["TST1"], ["TST2"], ["TST3"], ["TST1", "TST2"], ["TST1", "TST3"], ["TST2", "TST3"], ["TST1", "TST2", "TST3"]

此时甚至可以添加一点

"It is done. Go. Be happy!"

上面的代码工作得很好，但组合只出现在combinationUtil()中，而不是我想在main()中使用累积结果的地方。那么，我到底做错了什么？

Answer 1

您想要计算大小为 n 的数组中 r 元素的可能组合。你可以试试这个代码。我将该函数称为 nCr（不确定这是否是我们要解决的问题的正确数学符号）public static void main(String[] args) {&nbsp; &nbsp; String[] array2 = { "TST1", "TST2", "TST3"};&nbsp; &nbsp; List<List<String>> l = new ArrayList<>();&nbsp; &nbsp; for (var i: Arrays.asList(0, 1, 2, 3)) {&nbsp; &nbsp; &nbsp; &nbsp; l.addAll(nCr(array2, i));&nbsp; &nbsp; }&nbsp; &nbsp; System.out.println(l);}private static List<List<String>> nCr(String[] array, int r) {&nbsp; &nbsp; List<List<String>> result = new ArrayList<>();&nbsp; &nbsp; if (r == 0) return result;&nbsp; &nbsp; if (r == 1) return nC1(array);&nbsp; &nbsp; for (int i = 0; i < array.length - r + 1; i++) {&nbsp; &nbsp; &nbsp; &nbsp; List<List<String>> result2 = nCr(&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Arrays.copyOfRange(array, i + 1, array.length),&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; r - 1);&nbsp; &nbsp; &nbsp; &nbsp; for (var x: result2 ) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; x.add(array[i]);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; result.add(x);&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; return result;}private static List<List<String>> nC1(String[] array) {&nbsp; &nbsp; List<List<String>> l = new ArrayList<>();&nbsp; &nbsp; for (var x: array) {&nbsp; &nbsp; &nbsp; &nbsp; l.add(new ArrayList<>(Arrays.asList(x)));&nbsp; &nbsp; }&nbsp; &nbsp; return l;}输出：[[TST1], [TST2], [TST3], [TST2, TST1], [TST3, TST1], [TST3, TST2], [TST3, TST2, TST1]]