java - 打印给定长度的所有可能的字符串

Question

Given a string of alphabets and a number k, write a function to print all of the combinations of length k of these alphabets.

The string does not contain duplicate alphabets.

Input: { 'a', 'b', 'd', 's', 'e' }

Expected output: abd, abs, abe, ads, ade, bds, bde, bse, dse

我正在使用递归。

基本情况是当 int k 为 0 时，返回前缀。

如果不满足基本情况，则逐步添加字符数组中的所有字符并递归调用k = k - 1。

// Recursive method used to print all possible strings of length k, given a set of characters.
private static void printAllCombinations(char[] alphabet, String prefix, int n, int k) {
    // Base case: k is 0,
    // print prefix.
    if (k == 0) {
        System.out.print(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 + alphabet[i];

        // k is decreased, because
        // we have added a new character.
        printAllCombinations(alphabet, newPrefix, n, k - 1);
    }
}

实际输出:aaa aab aad aas aae aba abb abd abs abe ada adb add ads ade asa asb asd ass ase aea aeb aed aes aee baa bab bad bas bae bba bbb bbd bbs bbe bda bdb bdd bds bde bsa bsb bsd bss bse bea beb bed bes bee daa dab dad das dae dba dbb dbd dbs dbe dda ddb ddd dds dde ​​dsa dsb dsd dss dse dea deb ded des dee saa sab sad sas sae sba sbb sbd sbs sbe sda sdb sdd sds sde ssa ssb ssd sss sse sea seb sed ses see eaa eab ead eas eae eba ebb ebd ebs ebe edb eds ede esa esb esd ess ees eeb eed ees eee

我可以采取哪些不同的方式来实现所需的输出？

我知道我的函数 printAllCombinations 实际上正在正常工作。我只是不明白如何才能获得所需的输出。

Answer 1

您可以使用 n 来跟踪您在数组 alphabets 中的当前位置。

public static void printAllCombinations(char[] alphabet, int k) {
    printAllCombinations(alphabet, "", 0, k);
}
private static void printAllCombinations(char[] alphabet, String prefix, int n, int k) {
    if (k == 0) { //base case unchanged
        System.out.print(prefix + " ");
        return;
    }
    for (int i = n; i < alphabet.length; i++) { //loop only from n to end of array
        String newPrefix = prefix + alphabet[i];

        printAllCombinations(alphabet, newPrefix, i + 1, k - 1);
    }
}

输出:abd abs abe ads ade ase bds bde bse dse

如果你想在除第一个元素之外的每个元素之前使用逗号，那么你可以将你的基本情况更改为:

if (k == 0) {
    if (n > prefix.length()) {
        System.out.print(", ");
    }
    System.out.print(prefix);
    return;
}

将输出:abd, abs, abe, ads, ade, ase, bds, bde, bse, dse