Joh*_*han 10 algorithm combinatorics
我正在研究免费代码营问题 - http://www.freecodecamp.com/challenges/bonfire-no-repeats-please
问题描述如下 -
返回没有重复连续字母的提供字符串的总排列数.例如,'aab'应该返回2,因为它有6个总排列,但只有2个没有相同的字母(在这种情况下为'a')重复.
我知道我可以通过编写一个创建每个排列的程序然后过滤掉重复字符的程序来解决这个问题.
但我有这种啃咬的感觉,我可以用数学方法解决这个问题.
第一个问题 - 我可以吗？
第二个问题 - 如果是,我可以使用什么公式？
详细说明 -
问题中给出的例子是"aab",该网站称有六种可能的排列,只有两种符合非重复字符标准:
aab aba baa aab aba baa
问题是每个角色都是独特的,所以也许"aab"可以更好地描述为"a1a2b"
该问题的测试如下(返回符合标准的排列数) -
"aab" should return 2
"aaa" should return 0
"abcdefa" should return 3600
"abfdefa" should return 2640
"zzzzzzzz" should return 0
我已经阅读了很多关于组合和排列的帖子,似乎正在为自己挖掘更深的洞.但我真的想尝试有效地解决这个问题,而不是通过一系列所有可能的排列来暴力破解.
我在math.stackexchange上发布了这个问题 - https://math.stackexchange.com/q/1410184/264492
解决只重复一个字符的情况的数学非常简单 - 字符总数减去可用空格数乘以重复字符.
但试图找出重复多个字符的实例的公式却让我望而却步.例如"abfdefa"
Lur*_*rai 15
这是一种数学方法,不需要检查所有可能的字符串.
让我们从这个字符串开始:
abfdefa
要找到解决方案,我们必须计算排列总数(没有限制),然后减去无效排列.
总的来说
我们必须填充多个位置,这等于原始字符串的长度.让我们将每个位置视为一个小盒子.所以,如果我们有
abfdefa
它有7个字符,有七个盒子可以填充.我们可以用7个字符中的任何一个填充第一个,第二个用剩余的6个中的任何一个填充,依此类推.所以排列的总数没有限制,是:
7*6*5*4*3*2*1 = 7!(= 5,040)
无效的豁免权
具有两个相等字符的任何排列都是无效的.让我们看看我们有多少人.为了计算它们,我们将考虑任何并排具有相同字符的字符将位于同一个框中.因为他们必须在一起,为什么不认为他们像"复合"字符？我们的示例字符串有两个重复的字符:'a'出现两次,'f'也出现两次.
带'aa'的排列数 现在我们只有六个盒子,因为其中一个将填充'aa':
6*5*4*3*2*1 = 6!
我们还必须考虑两个'a'可以自己置于2中!(因为我们有两个'a')方式.那么,两个'a'在一起的排列总数是:
6!*2!(= 1,440)
'ff'的排列数 当然,因为我们也有两个'f','ff'的排列数与'aa'的排列数相同:
6!*2!(= 1,440)
OVERLAPS
如果我们只重复了一个字符,则问题结束,最终结果将是TOTAL - INVALID排列.
但是,如果我们有多个重复字符,我们会将一些无效字符串计数两次或更多次.我们必须注意到,两个'a'在一起的一些排列也会有两个'f',反之亦然,所以我们需要添加它们.我们如何算他们？由于我们有两个重复的字符,我们将考虑两个"复合"框:一个用于出现'aa'而另一个用于'ff'(两个同时出现).所以现在我们必须填写5个方框:一个用'aa',另一个用'ff',3用剩余的'b','d'和'e'.此外,'aa'和'bb'中的每一个都可以在2中进行置换!方法.所以重叠的总数是:
5!*2!*2!(= 480)
最终解决方案
这个问题的最终解决方案是:
TOTAL - INVALID + OVERLAPS
那就是:
7! - (2*6!*2!)+(5!*2!*2!)= 5,040 - 2*1,440 + 480 = 2,640
这是一种思考方法，对我来说仍然有点复杂：减去不允许的邻居的可能性计数。
例如abfdefa：
There are 6 ways to place "aa" or "ff" between the 5! ways to arrange the other five
letters, so altogether 5! * 6 * 2, multiplied by their number of permutations (2).
Based on the inclusion-exclusion principle, we subtract those possibilities that include
both "aa" and "ff" from the count above: 3! * (2 + 4 - 1) choose 2 ways to place both
"aa" and "ff" around the other three letters, and we must multiply by the permutation
counts within (2 * 2) and between (2).
So altogether,
7! - (5! * 6 * 2 * 2 - 3! * (2 + 4 - 1) choose 2 * 2 * 2 * 2) = 2640
我使用多重组合的公式来计算将字母对放置在其余字母对之间的方法。
一种可能比暴力解决方案取得一些改进的通用方法是枚举将字母与重复交错的方法，然后乘以划分它们周围其余字母的方法，同时考虑到必须填充的空间。示例abfdefa可能看起来像这样：
afaf / fafa => (5 + 3 - 1) choose 3 // all ways to partition the rest
affa / faaf => 1 + 4 + (4 + 2 - 1) choose 2 // all three in the middle; two in the middle, one anywhere else; one in the middle, two anywhere else
aaff / ffaa => 3 + 1 + 1 // one in each required space, the other anywhere else; two in one required space, one in the other (x2)
最后，乘以排列计数，总共：
2 * 2! * 2! * 3! * ((5 + 3 - 1) choose 3 + 1 + 4 + (4 + 2 - 1) choose 2 + 3 + 1 + 1) = 2640