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

Question

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

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

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

Answer 1

给定长度为 n 的字符串的排列总数将为 n! （如果所有字符都不同），因此不可能探索所有组合。

这道题其实就像数学P& C 题

求单词“stack”按字典顺序排列时的排名。

给定输入字符串 NILSU
取一个单词，我们要找到它的排名。以“SUNIL”为例。

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

一定会的。 “ILNS U”。

现在取出第一个字母。是“我”。现在检查一下，是字母“I”吗？
“SUNIL”的第一个字母？序号 可以组成的单词数
从 I will be 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

去苏。这是我们想要的吗？是的。从列表中删除字母 U 并
那么它将是“IL N”。现在尝试一下，我们想要 SUI 吗？不，所以这个数字
从SUI开始可以组成的单词数为2！

[SU]：我-> 2！ = 2 现在选择 L。我们想要“SUL”吗？没有，所以数量
以 SUL 开头的单词将为 2！。

[SU]:L-> 2！ = 2

现在选择 N。我们想要 SUN 吗？是的，现在删除该字母。还有这个
将是“I L”。我们想要“SUNI”吗？是的。删除那封信。唯一的
左边的字母是“L”。

现在去找 L。我们要 SUNIL 吗？是的。 SUNIL 是第一个选择，所以
我们有 1！ [太阳][I][L] = 1！ = 1

现在将我们得到的整数相加。总和将为。

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

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

因此通过这个方法你可以很轻松的解决这个问题。

Answer 2

构建@Algorithmist的答案以及他对答案的评论，并使用这篇文章中讨论的原则是重复的字母，我在 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，您应该能够看到它如何使用上面链接的 SO 帖子中的公式。

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;
}  

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;
        }

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

Answer 5

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

Answer 6

一个低效的解决方案是连续查找先前的排列，直到到达无法再排列的字符串。达到此状态所需的排列数就是原始字符串的位置。

但是，如果您使用组合数学，您可以更快地获得解决方案。如果字符串长度超过 12，前面的解决方案将产生非常慢的输出。