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

现在几个小时我一直在对付算法问题。给定一个字符串，计算没有重复（和禁止字符）的字符串排列的数目

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

我们的花园有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，所以它真的在复杂度上爆炸。

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

来源

2016-04-30 Giuseppe Rossini

你想*计算*这样的安排的数量，或者你想*生成*他们？前者更容易。 –

我正在努力计算，但我仍然无法考虑一个好的（性能明智的）解决方案：/ –

http://stackoverflow.com/questions/25285792/generate-all-permutations-ofa-a- list-without-adjacent-equal-elements/32366585＃32366585 – m69

我会按如下方式处理：'禁止'字符串与'花园'一样长。这意味着给定一个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有多大，即花园有多大:)

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

来源

2016-04-30 22:54:35 lorenzog

如果我的理解正确，那么您认为禁止在字母表中包含字符，但情况并非总是如此。在我给出的例子中，G =“aaabbb”和forbid =“cccccc”。 –

而且，我无法为我的字母表插入无限制的字母。例如，在同一个例子中，字母表是“ab”，但是我可以处理3个“a”和3个“b”s –

@GiuseppeRossini那么你如何验证'对于每个有效的i，G [i]不能等于禁止[i]'？而且，有限数量的字母进一步降低了可能性（将其视为无重复的组合） – lorenzog

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

回答

相关问题