在给定字符串的排列排序列表中找到给定排列的索引

Question

我们有一个字符串和该字符串的一个排列。

例如，输入字符串为sandeep，其排列为psdenae。

找出给定排列在原始字符串的所有排列按字典序排序后的位置。

- sunmoon

---

好问题！你尝试了什么？ - Dr. belisarius

这是一个九年级课堂问题，不是一个好问题。 - Peter

非常相似的问题，它的答案中有一个实现：https://dev59.com/D2ct5IYBdhLWcg3wXsQy - Chronial

Answer 1

给定长度为n的字符串，如果所有字符都不同，则其全排列总数为n!，那么就不可能探索所有组合。

这个问题实际上类似于数学的排列组合问题。

在字典顺序排列中，找到单词“stack”的等级。

给出输入字符串为NILSU。假设要查找等级的单词是"SUNIL"。

现在按字母顺序排列单词"SUNIL"。结果是"I L N S U"。

现在取第一个字母，“I”。检查一下，“I”是不是“SUNIL”的第一个字母？不是的。以"I"开头的单词数为4！，因此我们知道"SUNIL"之前有4！个单词。

I = 4! = 24

现在看第二个字母，“L”。再次检查该字母是否在第一个位置？不是的。因此以"L"开头的单词数为4！。

L = 4! = 24

现在看“N”。它是我们想要的吗？不是的。再次写下以“N”开头的单词数，仍然是4！。

N = 4! = 24

现在看“S”。它是我们想要的吗？是的。现在从按字母顺序排列的单词中移除这个字母。现在变成了“I L N U”。

写下“S”，再次在列表中检查这个单词。我们想要的是“SI”吗？不是的。因此，以“SI”开头的单词数为3！。

[S]：I-> 3! = 6

如果我们想要 SL，那么选择 L 吗？不，所以有 3! 种可能。

[S]:L-> 3! = 6

如果我们想要 SN，那么选择 N 吗？不，所以有 3! 种可能。

[S]:N-> 3! = 6

如果我们想要 SU，那么选择 SU 吗？是的。从列表中删除字母 U，剩下 "I L N"。现在尝试 I。如果我们想要 SUI 吗？不，所以以 SUI 开头的单词数量为 2！。

[SU]:I-> 2! = 2 现在选择 L。我们想要 "SUL" 吗？不，以 SUL 开始的单词数量也为 2！。

[SU]:L-> 2! = 2

现在选择 N。我们想要 SUN 吗？是的，现在删除该字母，得到 "I L"。我们想要 "SUNI" 吗？是的，删除该字母后，唯一剩下的字母是 "L"。

现在选择 L。我们想要 SUNIL 吗？是的。SUNIL 是第一个选项，因此只有 1！[SUN][I][L] = 1 。

现在将所有数字相加。总和为：

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

因此，如果我们按字典顺序排列 SUNIL 中的字母，并计算可以创建的单词数，则 SUNIL 将位于第 95 个位置。

通过这种方法，您可以轻松解决这个问题。

- Algorithmist

---

对于包含重复单词的字符串，例如BOMBAY，如果我们想要找到BOAYBM的位置，我们只需要知道BOMBAY有总共6! / 2!种组合即可。 - Algorithmist

Answer 2

在 @Algorithmist 的答案基础上，结合他对自己答案的评论，并使用 this post 中讨论的原则处理重复字母时，我用 JavaScript 编写了以下算法，适用于所有基于字母的单词，即使有重复的字母实例。

function anagramPosition(string) {
  var index = 1;
  var remainingLetters = string.length - 1;
  var frequencies = {};
  var splitString = string.split("");
  var sortedStringLetters = string.split("").sort();

  sortedStringLetters.forEach(function(val, i) {
    if (!frequencies[val]) {
      frequencies[val] = 1;
    } else {
      frequencies[val]++;
    }
  })

  function factorial(coefficient) {
    var temp = coefficient;
    var permutations = coefficient;
    while (temp-- > 2) {
      permutations *= temp;
    }
    return permutations;
  }

  function getSubPermutations(object, currentLetter) {
    object[currentLetter]--;
    var denominator = 1;
    for (var key in object) {
      var subPermutations = factorial(object[key]);
      subPermutations !== 0 ? denominator *= subPermutations : null;
    }
    object[currentLetter]++;
    return denominator;
  }

  var splitStringIndex = 0;
  while (sortedStringLetters.length) {
    for (var i = 0; i < sortedStringLetters.length; i++) {
      if (sortedStringLetters[i] !== splitString[splitStringIndex]) {
        if (sortedStringLetters[i] !== sortedStringLetters[i+1]) {
          var permutations = factorial(remainingLetters);
          index += permutations / getSubPermutations(frequencies, sortedStringLetters[i]);
        } else {
          continue;
        }
      } else {
        splitStringIndex++;
        frequencies[sortedStringLetters[i]]--;
        sortedStringLetters.splice(i, 1);
        remainingLetters--;
        break;
      }
    }
  }
  return index;
}

anagramPosition("ARCTIC") // => 42

我没有对代码进行评论，但我尽可能使变量名有解释性。如果您将其通过调试器处理，并使用开发工具控制台添加一些console.logs，您应该能够看到它如何使用上面链接的S.O.帖子中的公式。

- Salman Oskooi

Answer 3

我尝试在js中实现这个。对于没有重复字母的字符串，它可以工作，但是否则我会得到错误的计数。这是我的代码：

function x(str) {
var sOrdinata = str.split('').sort()
console.log('sOrdinata = '+ sOrdinata)
var str = str.split('')
console.log('str = '+str)
console.log('\n')
var pos = 1;

for(var j in str){
//console.log(j)

for(var i in sOrdinata){
if(sOrdinata[i]==str[j]){
  console.log('found, position: '+ i)
  sOrdinata.splice(i,1)
  console.log('Nuovo sOrdinata = '+sOrdinata)
  console.log('\n')
  break;
}
else{
  //calculate number of permutations
  console.log('valore di j: '+j)

  //console.log('lunghezza stringa da permutare: '+str.slice(~~j+1).length);
  if(str.slice(j).length >1 ){sub = str.slice(~~j+1)}else {sub = str.slice(j)}
  console.log('substring to be used for permutation: '+ sub)

  prep = nrepC(sub.join(''))
  console.log('prep = '+prep)

  num = factorial(sub.length)
  console.log('num = '+num)

  den = denom(prep)
  console.log('den = '+ den)

  pos += num/den
  console.log(num/den)
  console.log('\n')
 }
 }
}
console.log(pos)
return pos
}



/* ------------ functions used by main --------------- */ 

function nrepC(str){
var obj={}
var repeats=[]
var res= [];

for(x = 0, length = str.length; x < length; x++) {
var l = str.charAt(x)
obj[l] = (isNaN(obj[l]) ? 1 : obj[l] + 1);
}
//console.log(obj)

for (var i in obj){
if(obj[i]>1) res.push(obj[i])
}
if(res.length==0){res.push(1); return res}
else return res
}

function num(vect){
var res =  1

}


function denom(vect){
var res = 1
for(var i in vect){
res*= factorial(vect[i])
}
return res
}


function factorial (n){
if (n==0 || n==1){
return 1;
}
return factorial(n-1)*n;
}  

- daymos

Answer 4

有点晚了，但仅供参考... 你可以直接使用这个 C# 代码。

它能够工作，但是...

唯一重要的事情是通常情况下，你的起始集合应该是唯一的值。否则，你将没有 n！种排列。你会得到其他结果（少于 n!）。如果项目可能是重复的，我有一点怀疑任何有用的用途。

using System;
using System.Collections.Generic;

namespace WpfPermutations
{
    public class PermutationOuelletLexico3<T>
    {
        // ************************************************************************
        private T[] _sortedValues;

        private bool[] _valueUsed;

        public readonly long MaxIndex; // long to support 20! or less 

        // ************************************************************************
        public PermutationOuelletLexico3(T[] sortedValues)
        {
            if (sortedValues.Length <= 0)
            {
                throw new ArgumentException("sortedValues.Lenght should be greater than 0");
            }

            _sortedValues = sortedValues;
            Result = new T[_sortedValues.Length];
            _valueUsed = new bool[_sortedValues.Length];

            MaxIndex = Factorial.GetFactorial(_sortedValues.Length);
        }

        // ************************************************************************
        public T[] Result { get; private set; }

        // ************************************************************************
        /// <summary>
        /// Return the permutation relative to the index received, according to 
        /// _sortedValues.
        /// Sort Index is 0 based and should be less than MaxIndex. Otherwise you get an exception.
        /// </summary>
        /// <param name="sortIndex"></param>
        /// <returns>The result is written in property: Result</returns>
        public void GetValuesForIndex(long sortIndex)
        {
            int size = _sortedValues.Length;

            if (sortIndex < 0)
            {
                throw new ArgumentException("sortIndex should be greater or equal to 0.");
            }

            if (sortIndex >= MaxIndex)
            {
                throw new ArgumentException("sortIndex should be less than factorial(the lenght of items)");
            }

            for (int n = 0; n < _valueUsed.Length; n++)
            {
                _valueUsed[n] = false;
            }

            long factorielLower = MaxIndex;

            for (int index = 0; index < size; index++)
            {
                long factorielBigger = factorielLower;
                factorielLower = Factorial.GetFactorial(size - index - 1);  //  factorielBigger / inverseIndex;

                int resultItemIndex = (int)(sortIndex % factorielBigger / factorielLower);

                int correctedResultItemIndex = 0;
                for(;;)
                {
                    if (! _valueUsed[correctedResultItemIndex])
                    {
                        resultItemIndex--;
                        if (resultItemIndex < 0)
                        {
                            break;
                        }
                    }
                    correctedResultItemIndex++;
                }

                Result[index] = _sortedValues[correctedResultItemIndex];
                _valueUsed[correctedResultItemIndex] = true;
            }
        }

        // ************************************************************************
        /// <summary>
        /// Calc the index, relative to _sortedValues, of the permutation received
        /// as argument. Returned index is 0 based.
        /// </summary>
        /// <param name="values"></param>
        /// <returns></returns>
        public long GetIndexOfValues(T[] values)
        {
            int size = _sortedValues.Length;
            long valuesIndex = 0;

            List<T> valuesLeft = new List<T>(_sortedValues);

            for (int index = 0; index < size; index++)
            {
                long indexFactorial = Factorial.GetFactorial(size - 1 - index);

                T value = values[index];
                int indexCorrected = valuesLeft.IndexOf(value);
                valuesIndex = valuesIndex + (indexCorrected * indexFactorial);
                valuesLeft.Remove(value);
            }
            return valuesIndex;
        }

        // ************************************************************************
    }
}

- Eric Ouellet

Answer 5

我的解决问题的方法是对给定的排列进行排序。 字符串中字符的交换次数将给出排列在排列的排序列表中的位置。

- sunmoon

---

如果你只想使用冒泡排序，那么你就大错特错了。一个长度为10的字符串有10!种排列方式（假设所有字符都不同）。最多需要90次交换来对一个长度为10的字符串进行排序。 - Shamim Hafiz - MSFT

Answer 6

一种低效的解决方法是连续查找之前的排列，直到达到不能再进行排列的字符串。需要查找的排列次数即为原始字符串的位置。

然而，如果使用组合数学，可以更快地得出答案。如果字符串长度超过12，前面的方法会产生非常慢的输出。

- Shamim Hafiz - MSFT