置换不含重复字符 [英] Permutations excluding repeated characters

问题描述

我工作的一个免费的code阵营的问题 - 的 HTTP：//www.free$c$ccamp.com/challenges/bonfire-no-repeats-please

I'm working on a Free Code Camp problem - http://www.freecodecamp.com/challenges/bonfire-no-repeats-please

问题说明如下 -

返回提供串的总排列数即   没有连续重复字母。例如，AAB应当   返回2，因为它有6个总排列，但只有2人不   具有相同的信（在这种情况下，'a'）的重复

Return the number of total permutations of the provided string that don't have repeated consecutive letters. For example, 'aab' should return 2 because it has 6 total permutations, but only 2 of them don't have the same letter (in this case 'a') repeating.

我知道我可以通过编写创建的每个置换，然后筛选出那些有重复字符的程序解决这个问题。

I know I can solve this by writing a program that creates every permutation and then filters out the ones with repeated characters.

但我有这种剧痛的感觉，我可以用数学方法解决这个问题。

But I have this gnawing feeling that I can solve this mathematically.

第一个问题，然后 - ？我可以

First question then - Can I?

第二个问题 - ？如果是的话，我可以用什么公式

Second question - If yes, what formula could I use?

要进一步阐述 -

在问题给出的例子是AAB该网站上说有六个可能的排列，只有两个会议非重复字符的标准：

The example given in the problem is "aab" which the site says has six possible permutations, with only two meeting the non-repeated character criteria:

AAB ABA BAA AAB ABA BAA

aab aba baa aab aba baa

这个问题将每个字符作为唯一的，这样也许AAB能更好地被描述为a1a2b

The problem sees each character as unique so maybe "aab" could better be described as "a1a2b"

是测试针对此问题如下（返回满足条件排列的数量） -

The tests for this problem are as follows (returning the number of permutations that meet the criteria)-

"aab" should return 2
"aaa" should return 0
"abcdefa" should return 3600
"abfdefa" should return 2640
"zzzzzzzz" should return 0

我已经经历了很多后大约组合数学和排列的阅读，只是似乎挖掘自己更深的一个洞。但我真的想尝试所有可能的排列组合阵列来解决这一问题有效，而不是蛮力。

I have read through a lot of post about Combinatorics and Permutations and just seem to be digging a deeper hole for myself. But I really want to try to resolve this problem efficiently rather than brute force through an array of all possible permutations.

我贴这个问题上math.stackexchange - <一个href="http://math.stackexchange.com/q/1410184/264492">http://math.stackexchange.com/q/1410184/264492

I posted this question on math.stackexchange - http://math.stackexchange.com/q/1410184/264492

要解决只有一个字符重复的情况下，数学是pretty的小事 - 字符的总数减去可用空间乘以重复的字符数的阶乘

The maths to resolve the case where only one character is repeated is pretty trivial - Factorial of total number of characters minus number of spaces available multiplied by repeated characters.

• 在AAB= 3！ - 2！ * 2！ = 2
• 在abcdefa= 7！ - 6！ * 2！ = 3600

但是，试图找出公式，其中多个字符重复已躲避我的实例。例如abfdefa

But trying to figure out the formula for the instances where more than one character is repeated has eluded me. e.g. "abfdefa"

推荐答案

下面是去想它的一种方式，它仍然似乎有点复杂，我：减去的可能性计数不允许的邻居

Here's one way to think about it, which still seems a bit complicated to me: subtract the count of possibilities with disallowed neighbors.

例如 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

我用多集的组合的各种方法把信的计数公式其他地区之间的对。

I used the formula for multiset combinations for the count of ways to place the letter pairs between the rest.

这可能实现一些改进的蛮力溶液A一般化的方法是列举与重复交织字母的方式和然后乘以方式进行分区周围的其余部分，考虑到必须填写的空间。本例中， abfdefa ，可能是这个样子：

A generalizable way that might achieve some improvement over the brute force solution is to enumerate the ways to interleave the letters with repeats and then multiply by the ways to partition the rest around them, taking into account the spaces that must be filled. The example, abfdefa, might look something like this:

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)

最后，通过置换数量增多，所以干脆：

Finally, multiply by the permutation counts, so altogether:

2 * 2! * 2! * 3! * ((5 + 3 - 1) choose 3 + 1 + 4 + (4 + 2 - 1) choose 2 + 3 + 1 + 1) = 2640

这篇关于置换不含重复字符的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！