给定一个字符串，计算没有重复（和禁止字符）的字符串排列的数目

Question

现在几个小时我一直在对付算法问题。

问题的（花式）声明如下：

我们的花园有flowers.You单一行中给出该行的当前内容在String花园。花园里的每个角色代表一朵花。不同的字符代表不同的颜色。相同颜色的花朵看起来都一样。你可以按你喜欢的顺序重新排列花园里的花朵。 （正式的，你可以在你的花园里换掉任何两朵花，而且你可以任意多次这样做）。你还得到一个和花园一样长的字符串禁止。你想把花园重新排列成一个新的字符串G，以下条件：

没有两个相邻的花会有相同的颜色。正常情况下，对于每个有效的i，G [i]和G [i + 1]必须不同。 对于每个有效的i，G [i]不能等于禁止[i]。 设X是满足上述所有条件的不同字符串G的数量。计算并返回数字（X取模1,000,000,0007）。

只是为了用一个例子阐明：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个字符的字母表，每个位置G [i]最多可以有N-1个可能的字符（因为其中一个将被禁止）。这给了你一个仅受N限制的上界。如果这个界限小于模数，它可能会引起一些有趣的考虑，但让我们继续前进。

现在一个非常基本的方法是计算组合：如果花园长度为K个字符，则第一个项目G [0]将具有N-1个可能性;如果禁止[1]与G [0]不同，则第二个G [1]将具有N-2个可能性，如果禁止[1] == G [0]则N-1可能。取决于禁止的[2]和G [1]，第三个字符G [2]也将具有N-2个可能性，以此类推。为了清楚起见：N-2来自N-1可能性的事实，必须删除另一个字符串中前面的字符的值，除非这样的字符匹配当前的禁止字符位置。因此，如果禁止[i + 1]总是与G [i]不同，那么您有N-1 * N-2 * N-2 * ... * N-2，K次。这是你的下限。

现在在上下边界之间有多个字符串，例如，禁止[i + 1]仅在第二个位置等于G [i];第二和第三;等等所以你的字符串的号码是：

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有多大，即花园有多大:)

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