找到一个给定的排列的索引在给定的字符串的排列的排序列表 [英] Find the index of a given permutation in the sorted list of the permutations of a given string

问题描述

我们正在给一个字符串，字符串的置换。

We're given a string and a permutation of the string.

例如，输入字符串桑迪普和置换 psdenae 。

For example, an input string sandeep and a permutation psdenae.

查找在给定的排列中的原始字符串的排列的排序列表中的位置。

Find the position of the given permutation in the sorted list of the permutations of the original string.

推荐答案

长度为n的定字符串的置换总数将 N！（如果所有的字符是不同的），因此，它不可能探索所有组合

The total number of permutation of a given string of length n would be n! (if all characters are different), thus it would not be possible to explore all the combinations.

这个问题其实就像数学P＆放大器; ç问题

This question is actually like the mathematics P & C question

查找单词栈的等级时，排列的字典顺序。的

Find the rank of the word "stack" when arranged in dictionary order.

由于输入的字符串作为NILSU 以一个词，我们必须找到军衔。以SUNIL为例。

Given the input string as NILSU Take a word which we have to find the rank. Take "SUNIL" for example.

现在安排SUNIL按字母顺序排列的字母。

Now arrange the letter of "SUNIL" in alphabetical order.

这将是。 I L N 2 S U。

It will be. "I L N S U".

现在取第一个字母。它的我。现在检查，是字母I的   SUNIL的第一个字母？号可形成的字数   开始我会在4 !,所以我们知道会有4！话   SUNIL。

Now take the first letter. Its "I". Now check, is the letter "I" the first letter of "SUNIL"? No. The number of words that can be formed starting with I will be 4!, so we know that there will be 4! words before "SUNIL".

我= 4！ = 24

I = 4! = 24

现在去的第二个字母。其的L。现在检查一次，如果这   信中，我们希望在第一的位置？号所以词的数目可以是   形成了以L将是4！

Now go for the second letter. Its "L". Now check once again if this letter we want in first position? No. So the number of words can be formed starting with "L" will be 4!.

L = 4！ = 24

L = 4! = 24

现在去为N。这是我们想要的吗？号记下的单词数   可以形成以N时，再次4！

Now go for "N". Is this we want? No. Write down the number of words can be formed starting with "N", once again 4!

N = 4！ = 24

N = 4! = 24

现在去为S。难道这就是我们想要的吗？是。现在，请从信   在按字母顺序排列的单词。现在将我L N U

Now go for "S". Is this what we want? Yes. Now remove the letter from the alphabetically ordered word. It will now be "I L N U"

写S和在列表中再次检查该单词。是我们要SI？没有。   所以可以形成的字的数量开始的SI将3！

Write S and check the word once again in the list. Is we want SI? No. So the number of words can be formed starting with SI will be 3!

[S]：I-> 3！ = 6

[S]:I-> 3! = 6

去L.是我们要SL？号因此，这将是3！

Go for L. is we want SL? No. So it will be 3!.

[S]：1-> 3！ = 6

[S]:L-> 3! = 6

去N.是我们要SN？没有。

Go for N. is we want SN? No.

[S]：N-> 3！ = 6

[S]:N-> 3! = 6

去苏。这是我们想要的吗？是。从列表中剪下字母U和   那么这将是I L N。现在尝试一，是我们要SUI？没有。所以数   的话，可以形成从隋开始将是2！

Go for SU. Is this we want? Yes. Cut the letter U from the list and then it will be "I L N". Now try I. is we want SUI? No. So the number of words can be formed which starts from SUI will be 2!

[苏]：I-> 2！ = 2现在去L.我们是否希望SUL。号这样的数   开始SUL话会2！

[SU]:I-> 2! = 2 Now go for L. Do we want "SUL". No. so the number of words starting with SUL will be 2!.

[苏]：1-> 2！ = 2

[SU]:L-> 2! = 2

现在去北是我们要阳光下？是的，现在取出那封信。和这个   将I L。难道我们要SUNI？是。取出那封信。唯一   信左侧为L。

Now go for N. Is we want SUN? Yes, now remove that letter. and this will be "I L". Do we want "SUNI"? Yes. Remove that letter. The only letter left is "L".

现在去L.难道我们要SUNIL？是。 SUNIL是第一选择，所以   我们有1！ [太阳] [I] [1] = 1！ = 1

Now go for L. Do we want SUNIL? Yes. SUNIL were the first options, so we have 1!. [SUN][I][L] = 1! = 1

现在加上我们得到的整数。总和会。

Now add the whole numbers we get. The sum will be.

24 + 24 + 24 + 6 + 6 + 6 + 2 + 2 + 1 = 95

24 + 24 + 24 + 6 + 6 + 6 + 2 + 2 + 1 = 95.

所以，这个词SUNIL将在第95的位置，如果再算上排列字典顺序，可以使用SUNIL的字母来创建的话。

So the word SUNIL will be at 95th position if we count the words that can be created using the letters of SUNIL arranged in dictionary order.

因此，通过这种方法可以解决这个问题很容易。

这篇关于找到一个给定的排列的索引在给定的字符串的排列的排序列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！