几个小时来，我一直在思考一个算法问题。问题的（奇特的）陈述如下：我们的花园只有一排花，你可以在串花园里看到这一排的内容。花园里的每个字代表一朵花。不同的文字代表不同的颜色。同一颜色的花看起来都一样你可以把花园里的花重新排列成你喜欢的任何顺序。（正式地说，你可以在你的花园里任意交换两朵花，而且你可以随意地多次交换。）你也被给予与花园相同长度的字符串禁止。你想将花园重新排列成一个新的字符串g，它将满足以下条件：相邻的两朵花不会有相同的颜色。形式上，对于每个有效的i，g[i]和g[i+1]必须不同。对于每个有效的i，g[i]不能等于禁止[i]。设x是满足上述所有条件的不同字符串g的个数，计算并返回这个数（x模10000000007）。举个例子来说明：X（“aaabb”、“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可以是我不是真的在寻找一个完整的解决方案。只是，如果你对我解决问题的方法有什么建议，我会非常感谢！ 最佳答案 我的做法是：你的“禁锢”线和“花园”一样长。这意味着给定一个由n个字符组成的字母表，每个位置g[i]最多可以有n-1个可能的字符（因为其中一个将被禁止）。这给了你一个仅受N限制的上界，如果这个上界小于模，可能会引起一些有趣的考虑，但是让我们继续前进。现在一个非常基本的方法是计算组合：如果花园是k个字符长，第一个项目g[0]将有n-1个可能性；第二个项目g[1]将有n-2个可能性，如果禁止[1]不同于g[0]，如果禁止[1]==g[0]。第三个字符G[2]也有N-2个可能性，这取决于禁止的[2]和G[1]等等。为了清楚起见：n-2来自于n-1可能性中的另一个可能性，必须删除另一个可能性，即字符串中该可能性前面的字符的值，除非该字符与当前位置的禁止字符匹配。所以，如果禁止的[i+1]总是不同于g[i]，那么你就有n-1*n-2*n-2*……*N-2，k次。这是你的下限。在上界和下界之间有一些字符串，例如禁止的[i+1]只在第二个位置等于g[i]；在第二个位置等于g[i]；在第三个位置等于g[i]；所以你的字符串数目是：N-1 * N-2 * N-2 * N-2 ... KN-1 * N-1 * N-2 * N-2 ... KN-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有多大，即你的花园有多大：）也就是说，假设我正确地理解了这个问题。关于string - 给定一个字符串，计算没有重复(和禁止的字符)的字符串排列数目，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/36959417/
