Найти индекс данной перестановки в отсортированном списке перестановок данной строки

Общее количество перестановок заданной строки длины n будет равно n! (если все символы разные), поэтому исследовать все комбинации будет невозможно.

Этот вопрос на самом деле похож на вопрос P&C по математике.

Найти ранг слова "стек" в словарном порядке.

Учитывая входную строку как NILSU. Возьмем слово, которому мы должны найти ранг. Возьмем, к примеру, "САНИЛ".

Теперь расположите букву «SUNIL» в алфавитном порядке.

Это будет. "И Л Н С У".

Теперь возьмите первую букву. Его «я». Теперь проверьте, является ли буква «I» первой буквой слова «SUNIL»? Нет. Количество слов, которые можно составить, начиная с I, будет равно 4!, поэтому мы знаем, что их будет 4! слова перед "SUNIL".

I = 4! = 24

Теперь приступайте ко второму письму. Его "Л". Теперь еще раз проверьте, нужна ли эта буква на первой позиции? Нет. Таким образом, количество слов, которые можно составить, начиная с «L», будет равно 4!

L = 4! = 24

Теперь идите на «Н». Этого мы хотим? Нет. Запишите, сколько слов можно составить, начиная с «N», еще раз 4!

N = 4! = 24

Теперь идите на «S». Это то, чего мы хотим? да. Теперь удалите букву из слова в алфавитном порядке. Теперь это будет "I L N U"

Напишите S и еще раз проверьте слово в списке. Мы хотим СИ? Нет. Таким образом, количество слов, которые можно составить, начиная с SI, будет равно 3!

[S]:I-> 3! = 6

Перейти на L. Мы хотим SL? Нет. Значит будет 3!.

[S]:L-> 3! = 6

Перейти на N. Мы хотим SN? Нет.

[S]:N-> 3! = 6

Иди на СУ. Этого мы хотим? да. Вырежьте букву 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. Мы хотим SUNIL? да. SUNIL были первыми вариантами, так что у нас 1!. [СОЛНЦЕ][I][L] = 1! = 1

Теперь сложим целые числа, которые у нас получились. Сумма будет.

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

Таким образом, слово SUNIL будет на 95-й позиции, если мы подсчитаем слова, которые можно составить, используя буквы SUNIL, расположенные в словарном порядке.

Таким образом, с помощью этого метода вы могли бы довольно легко решить эту проблему.

Создание ответа @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, вы сможете увидеть, как он использует формулу в приведенной выше ссылке S.O. Почта.

Я пытался реализовать это в 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;
}  

Немного поздно, но просто для справки... Вы можете использовать этот код 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;
        }

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

Мой подход к проблеме - сортировать данную перестановку. Количество перестановок символов в строке даст нам позицию перестановки в отсортированном списке перестановок.

Неэффективным решением будет последовательный поиск предыдущих перестановок, пока вы не достигнете строки, которую больше нельзя переставлять. Количество перестановок, необходимых для достижения этого состояния, равно положению исходной строки.

Однако, если вы используете комбинаторику, вы можете найти решение быстрее. Предыдущее решение будет производить очень медленный вывод, если длина строки превышает 12.