我刚刚做了一个测验,其中有一个我强行提出的问题......但我确信有一个“数学”公式可以“解决”它。
字符串的排列
假设您有一个字符串“abcdef”...计算该字符串的所有唯一排列。对于具有所有唯一选项的字符串,这很简单:长度因子。所以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!)。
我知道这与阶乘和空格数有关。但最终的答案却让我无法理解。
我应该能够获取长度,除以计数...并计算以空格开头的不同数字并减去它。
最佳答案
您将第一个字符划分为单独的情况:该字符的选择较少。这会更改计算分子的第一个因子。例如,aa.bb.cc
第一个字符只有 6 个选择,而不是 8 个。因此,计算结果为
8! / (2! 2! 2! 2!) -- four duplicates
现在
(6 * 7!) / (2! 2! 2! 2!) -- we still have four duplicates
关于algorithm - 独特的排列 - 有异常(exception),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/45471604/