从有序的字符序列递归生成有序子串？

Question

得到答案后编辑

这里有一些很好的答案 我喜欢Josh,因为它非常聪明并且使用C++.但是我决定接受Dave的答案,因为它的简单性和递归性.我对它们进行了测试,它们都产生了相同的正确结果(尽管顺序不同).再次感谢大家.

---

假设我有一个字符串s chars s [0]:s [N]并且每个char s [i] <= s [i + 1]例如字符串

aaacdddghzz

我想生成子串的所有组合,同时保持字符之间的相同关系.

所以例如我会得到

a
aa
aaa
ad
aad
aaad
add
aadd
aaadd
addd
aaddd
aaaddd
d
dd
ddd
.
.
.
ac
aac
.
.
.
acdddghzz
aacdddghzz
aaacdddghzz

但不是

ca
hdz
...etc

现在我知道如何计算出有多少种组合.您可以创建字符串中字母频率的直方图.所以在上面的例子中就是这样

对于字符串aaacdddghzz

a=3
d=3
c=1
g=1
h=1
z=2

而公式是(a+1)(c+1)(d+1)(g+1)(h+1)(z+1) = 4*4*2*2*2*3 = 384.有384个子串保持s [i] <= s [i + 1]的关系.

所以问题是如何递归生成这些384子串？实际上,迭代方法也同样好,也许更好,因为具有许多唯一字符的大字符串可能导致堆栈溢出.这听起来像是作业,但事实并非如此.我想出这样的算法是没用的.我使用C++但伪代码会很好.

Answer 1

Ryan Shaw回答上面的答案:

而不是以二进制计数,根据每个字母的数量计算基数中的每个数字.例如:

a d c g h z
3 3 1 1 1 2

伯爵:

0 0 0 0 0 0
0 0 0 0 0 1
0 0 0 0 0 2
0 0 0 0 1 0
0 0 0 0 1 1 
0 0 0 0 1 2
0 0 0 1 0 0
...
0 0 0 1 1 2
0 0 1 0 0 0
...
0 0 1 1 1 2
0 1 0 0 0 0 
...
0 3 1 1 1 2
1 0 0 0 0 0
...
3 3 1 1 1 2

并且您已经枚举了所有可能的子集,没有重复.对于这些输出中的任何一个,字符串只是循环遍历数字并输出指定的每个字母的数量.

1 2 0 0 1 1 => addhz
3 0 0 0 1 2 => aaahzz

和代码:

void GetCounts(const string &source, vector<char> &characters, vector<int> &counts)
{
    characters.clear();
    counts.clear();

    char currentChar = 0;
    for (string::const_iterator iSource = source.begin(); iSource != source.end(); ++iSource)
    {
        if (*iSource == currentChar)
            counts.back()++;
        else
        {
            characters.push_back(*iSource);
            counts.push_back(1);
            currentChar = *iSource;
        }
    }
}

bool Advance(vector<int> &current, const vector<int> &max)
{
    if (current.size() == 0)
        return false;

    current[0]++;
    for (size_t index = 0; index < current.size() - 1 && current[index] > max[index]; ++index)
    {
        current[index] = 0;
        current[index + 1]++;
    }
    if (current.back() > max.back())
        return false;
    return true;
}

string ToString(const vector<int> &current, const vector<char> &characters)
{
    string result;
    for (size_t index = 0; index < characters.size(); ++index)
        for (int i = 0; i < current[index]; ++i)
            result += characters[index];
    return result;
}

int main() { 
    vector<int> max;
    vector<char> characters;

    GetCounts("aaadddcghzz", characters, max);

    vector<int> current(characters.size(), 0);
    int index = 1;
    while (Advance(current, max))
    {
        cout << index++ << ":" << ToString(current, characters) << endl;
    }
}