给定一个字符串，计算没有重复(和禁止字符)的字符串的排列数。

Question

几个小时以来，我一直在努力解决算法问题。

关于这个问题的(想像力的)陈述如下：

我们的花园包含一行flowers.You，给出了字符串花园中行的当前内容。花园里的每个字代表一朵花。不同的字符表示相同颜色的不同colors.Flowers，看起来都是一样的。你可以把花园里的花重新排列成你喜欢的任何顺序。(在形式上，你可以在你的花园里任意交换两朵花，你可以随意地交换很多次。)您还将获得一个与garden.You希望将花园重新排列为新字符串G的长度相同的字符串，该字符串将满足以下条件：

没有两个相邻的花会有相同的color.Formally，因为每一个有效的i，Gi和Gi +1必须不同。对于每一个有效的i，Gi不能等于禁止。设X是满足给定above.Compute所有条件的不同字符串G的数目，并返回数字(X模1,000,000,007)。

为了澄清一个例子: X("aaabbb"，"cccccc") =2 ("ababab“和"bababa")

我一直在计算字符串中有多少字母(示例中为'a'->3，'b'->4 )，然后递归地计算不同的可能性(如果有重复或禁止的字母，则跳过)。这几条线上的东西：

using Map = std::map < char, size_t > ;
Map hist; 
std::string forbid;

size_t countRecursive(std::string s, size_t len)
{
    if (len == 0)
        return 1;

    size_t curPos = s.size() ;
    size_t count(0);

    for (auto &p : hist) {
        auto key = p.first;

        if (hist[key] == 0) continue;
        if (forbid[curPos] == key) continue;
        if (curPos > 0 && s[curPos - 1] == key) continue;

        hist[key]--;            
        count += countRecursive(s + key, len - 1);
        hist[key]++;
    }


    return count;
}

在此之前初始化了hist和forbid。然而，这似乎是n！既然n可以是<= 15，那么它的复杂性就会急剧增加。

我并不是真的在寻找一个完整的解决方案。只是，如果你对我应该如何处理这个问题有任何建议，我会非常感激的！

Answer 1

我的做法如下:你的“禁止”字符串和“花园”一样长。这意味着，给定N个字符的字母表，Gi的每个位置最多可以有N-1个可能的字符(因为其中一个将被禁止)。这给出了一个仅受N限制的上界，如果这个界小于模，它可能会引起一些有趣的考虑，但让我们继续前进。

现在，一个非常基本的方法是计算组合:如果花园是K字符长，第一项G将有N1可能性；第二项G1将有N-2可能性，如果forbidden1不同于G，N-1如果forbidden1 == G。第三个字符G2也有N-2可能性，取决于forbidden2和G1等等。

为了清晰起见: N-2来自于N-1可能性的事实，必须删除另一个可能性，即字符串中它前面的字符的值，除非该字符与当前位置的禁止字符匹配。

所以如果forbiddeni+1和Gi总是不同的话，你有N-1 * N-2 * N-2 *.* N-2，K次。这是你的下界。

在上下界之间有许多字符串，例如，forbiddeni+1仅对第二个位置等于Gi；对于第二个和第三个位置，等等。所以字符串的数目是：

N-1 * N-2 * N-2 * N-2 ... K
N-1 * N-1 * N-2 * N-2 ... K
N-1 * N-1 * N-1 * N-2 ... K

等等，直到你有一个字符串，其中每个字符可以有N-1的可能性。

换句话说，

N-1 * (N-2)^K-1
(N-1)^2 * (N-2)^K-2
(N-1)^3 * (N-2)^K-3

你能有多少根这样的弦？这取决于K有多大，即你的花园有多大:)

也就是说，假设我正确理解了这个问题。