生成字符串列表及其子字符串的排列的算法

Question

我已经逃避这个算法一段时间了。假设我得到了字符串“cccaatt”。我正在尝试生成重复字母的每个子串的所有可能变体。 EG，“cccaatt”作为输入将返回:

猫， 猫， 猫， 猫, 猫猫， ccatt, ccaat, ccaatt, 猫猫, CCAT， 关注, 访问权限

结果的顺序无关紧要，只要返回所有结果即可。一般来说，输入是一个字符串，由g组重复的字母组成，每组k_n个字母长。

我的直觉是这是一个递归算法，但它的确切结构一直难以理解。

Answer 1

如果您存储字母表和每个字母的最大出现次数(正如评论中提到的那样)，您可以这样做:

function variations(letter_type, current string) {
    if (letter_type is in the alphabet) {
        while (string has fewer than the max amount of that letter) {
            add one of that letter to current string
            variations(next letter, current string)
        }
    } else {
        print current string // since there are no more letters to add
    }
}

在 Java 中:

public class Variations {

    static String[] alphabet = {"c","a","t"};
    static int[] maximums = {3, 2, 2};

    public static void main(String[] args) {
        variations(0, "");
    }

    public static void variations(int letter_type, String curr) {
        if (letter_type < alphabet.length) {
            for (int i = 1; i <= maximums[letter_type]; i++) {
            curr += alphabet[letter_type];
            variations(letter_type+1, curr);
            }
        } else {
            System.out.println(curr);
        } 
    }

}