java - 生成比数组长度更长的所有可能组合

Question

我需要从字符串数组/ArrayList 构建长度为 L 的每个组合，其中 L 大于数组长度

我目前有一个递归方法(不是我自己创建的)，它会生成 String[] 的每个组合，只要这些组合比 Array 短。

示例/伪代码:

input (2, {A,B,C}) 
returns {AA, AB, AC, BA, BC, CB, CA}

截至目前，如果请求的组合长度(示例中为 2)大于数组长度(4、5、6... 而不是 2)，递归方法会发出甜蜜的 ArrayIndexOutOfBounds 错误。

我需要的是一种方法(递归或非递归)，它会返回数组的每个组合，无论这些组合是否比数组本身长。通过向数组添加更多字母并祈祷我的手指会更好，还是有合法的方法来完成此操作？谢谢!

这是我一直在使用的方法。如果你知道功劳在哪里，请说出来，这不是我自己的创作。

public class bizzBam
{
    // Driver method to test below methods
    public static void main(String[] args) {
        System.out.println("First Test");
        String set1[] = {"a", "b","c"};
        printAllKLength(set1, pointX);
    }

    // The method that prints all possible strings of length k.  It is
    //  mainly a wrapper over recursive function printAllKLengthRec()
    static void printAllKLength(String set[], int k) {
        int n = set.length+2;
        printAllKLengthRec(set, "", n, k);
    }

    // The main recursive method to print all possible strings of length k
    static void printAllKLengthRec(String set[], String prefix, int n, int length) {

        // Base case: k is 0, print prefix
        if (length == 0) {
            System.out.println(prefix);
            return;
        }

        // One by one add all characters from set and recursively
        // call for k equals to k-1
        for (int i = 0; i < n; ++i) {

            // Next character of input added
            String newPrefix = prefix + set[i];

            // k is decreased, because we have added a new character
            printAllKLengthRec(set, newPrefix, n, length - 1);
        }
    }
}

(编辑忘了说:) 至少对于这个算法，如果“PointX”大于输入数组的长度，它将返回索引超出范围。

Answer 1

严格来说，这些是排列而不是组合。您正在生成从一组 n 个候选者中选择的 k 个元素的所有排列，并进行替换(或重复)。会有n^k种这样的排列。

这是一个非递归的解决方案。

public class Permutations
{
    public static void main(String[] args)
    {
        permutationsKN(new String[]{"a",  "b",  "c"}, 4);
    }

    static void permutationsKN(String[] arr, int k)
    {
        int n = arr.length;

        int[] idx = new int[k];
        String[] perm = new String[k];

        while (true)
        {
            for(int i=0; i<k; i++) perm[i] = arr[idx[i]];           
            System.out.println(String.join("", perm));

            // generate the next permutation
            int i = idx.length - 1;
            for (; i >= 0; i--)
            {
                idx[i]++;
                if (idx[i] < n) break;                  
                idx[i] = 0;
            }

            // if the first index wrapped around then we're done
            if (i < 0) break;               
        }
    }
}