sun*_*oon 19 algorithm permutation
我们给了一个字符串和字符串的排列.
例如,输入字符串sandeep和排列psdenae.
在原始字符串的排列的排序列表中查找给定排列的位置.
Alg*_*ist 32
给定长度为n的字符串的排列总数为n!(如果所有字符都不同),则无法探索所有组合.
这个问题实际上就像数学P&C问题
按字典顺序排列时,查找单词"stack"的排名.
给定输入字符串为NILSU取一个单词,我们必须找到排名.以"SUNIL"为例.
现在按字母顺序排列"SUNIL"字母.
这将是."ILNS U".
现在拿第一个字母.它的"我".现在检查一下,字母"我"是"SUNIL"的第一个字母？不可以.从I开始可以形成的单词数量为4!,所以我们知道会有4个!在"SUNIL"之前的单词.
我= 4!= 24
现在去找第二封信.它的"L".现在再次检查这封信我们想要的第一个位置？不.所以从"L"开始形成的单词数量将为4!
L = 4!= 24
现在去"N".这是我们要的吗？编号.记下可以用"N"开头形成的字数,再次4!
N = 4!= 24
现在去"S".这是我们想要的吗？是.现在从字母顺序的单词中删除该字母.它现在将是"ILN U"
写入S并在列表中再次检查单词.我们想要SI吗？不.所以从SI开始可以形成的单词数量为3!
[S]:I-> 3!= 6
去L ..我们想要SL吗？不,所以它将是3!
[S]:L-> 3!= 6
去N.我们想要SN吗？没有.
[S]:N-> 3!= 6
去SU吧.这是我们要的吗？是.从列表中剪下字母U,然后它将是"IL N".现在试试I.我们想要SUI吗？不.所以可以形成从SUI开始的单词数量为2!
[SU]:I-> 2!= 2现在去L.我们想要"SUL".不,所以以SUL开头的单词数量为2!
[SU]:L-> 2!= 2
现在去N.我们想要SUN吗？是的,现在删除那封信.这将是"我L".我们想要"SUNI"吗？是.删除那封信.剩下的唯一字母是"L".
现在去找L.我们想要SUNIL吗？是.SUNIL是第一选择,所以我们有1个![SUN] [I] [L] = 1!= 1
现在添加我们得到的整数.总和将是.
24 + 24 + 24 + 6 + 6 + 6 + 2 + 2 + 1 = 95.
因此,如果我们计算可以使用以字典顺序排列的SUNIL字母创建的单词,那么单词SUNIL将位于第95位.
因此,通过这种方法,您可以很容易地解决这个问题.