算法生成的字符串和它们的子列表的排列 [英] Algorithm to generate permutations of a list of strings and their substrings

问题描述

该算法已逃离我有一段时间了。比方说，我给了字符串cccaatt。我试图产生重复的字母每串的所有可能的变化。例如，cccaatt作为输入，将返回：

This algorithm has been escaping me for some time now. Lets say I'm given the string "cccaatt". I'm trying to generate all the possible variations of each substring of repeated letters. EG, "cccaatt" as an input would return:

猫， CATT， CAAT， caatt， CCAT， CCATT， CCAAT， ccaatt， cccat， cccatt， cccaat， cccaatt

cat, catt, caat, caatt, ccat, ccatt, ccaat, ccaatt, cccat, cccatt, cccaat, cccaatt

结果的顺序并不重要，只要它返回所有的人。一般情况下，输入字符串，包括反复封的G组，每组k_n字母。

The order of the results does not matter, so long as it returns all of them. Generally, the input is a string, consisting of g groups of repeated letters, each group k_n letters long.

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

My intuition is that this is a recursive algorithm, but the exact structure of it has been difficult to understand.

推荐答案

如果您存储每个字母的字母表和最大事件（如在评论中赫然提到的），你可以这样做：

If you store the alphabet and maximum occurrences of each letter (as awesomely mentioned in the comments) you can do this:

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);
        } 
    }

}

这篇关于算法生成的字符串和它们的子列表的排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！