algorithm - 唯一排列 - 有异常(exception)

Question

我刚做了一个测验，它有一个问题是我强行逼出来的……但我确信有一个“数学”公式可以“解决”它。

字符串的排列

假设您有一个字符串“abcdef”...计算该字符串的所有唯一排列。对于具有所有唯一选项的字符串，这很简单:Length Factoral。所以6! = 720 种独特的组合。

唯一排列

现在，当您添加重复项时...您取阶乘，然后除以唯一字母的乘积:“aaabbb”=> 6!/(3! * 3!) => 720/36 => 20 个独特的组合。

唯一排列，排除

难倒我的部分:

您有一个字符串，可能包含重复数据...除了现在，排除以空格(或点，以便可见)开头的排列:

"aa.bb" => "aabb." is a valid permutation... ".aabb" is not. 
"aa.bb.cc" => "aa..bbcc" valid permutation. ".aabbcc." not valid. "..aabbcc" is not valid
"a.." => has one valid permutation: "a.."... the others are all duplicates or start with spaces.

我的解决方案

我的解决方案 - 蛮力 - 是创建排列...并手动排除以空格开头的排列...如果我没记错的话，O(N!)。

我知道它与阶乘和空格数有关。但最终的答案让我望而却步。

我应该能够获取长度，除以计数...然后计算以空格开头的不同数字并减去它。

Answer 1

您将第一个字符划分为一个单独的案例:该字符的选择较少。这会更改计算分子的第一个因子。例如，aa.bb.cc 的第一个字符只有 6 个选择，而不是 8 个。因此，计算是

8! / (2! 2! 2! 2!)   -- four duplicates

现在

(6 * 7!) / (2! 2! 2! 2!)   -- we still have four duplicates