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

Question

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

Например, входная строка sandeep и перестановка psdenae.

Найти положениеперестановка в отсортированном списке перестановок исходной строки.

Answer 1

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

Этот вопрос на самом деле похож на вопрос о математике и учете

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

Задана входная строка как NILSU Поверьте на слово, которое мы должны найти. Возьмите, например, «СУНИЛ».

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

Будет. "I L N S U".

Теперь возьмите первую букву. Это «я». Теперь проверьте, является ли буква "я" первая буква "СУНИЛ"? Количество слов, которые могут быть сформированы начиная с меня будет 4 !, поэтому мы знаем, что будет 4! слова до "СУНИЛ".

Я = 4! = 24

Теперь перейдите ко второй букве. Это "L". Теперь проверьте еще раз, если это письмо мы хотим в первой позиции? Так что количество слов может быть сформировано, начиная с "L" будет 4!.

L = 4! = 24

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

N = 4! = 24

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

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

[S]: I-> 3! = 6

Перейти на Л. Мы хотим SL? Нет. Так будет 3!.

[S]: L-> 3! = 6

Иди за Н., хотим ли мы СН? Нет.

[S]: N-> 3! = 6

Перейти на SU. Это мы хотим? Да. Вырежьте букву U из списка и тогда это будет "Я L N". Теперь попробуйте я. Мы хотим SUI? Так что число слов может быть сформировано, который начинается с SUI будет 2!

[SU]: I-> 2! = 2 Теперь перейдите к L. Мы хотим, чтобы "SUL". № так что количество слова, начинающиеся с SUL, будут 2!.

[SU]: L-> 2! = 2

Теперь перейдите к N. Мы хотим СОЛНЦЕ? Да, теперь удалите это письмо. и это будет "Я L". Мы хотим "SUNI"? Да. Удалить это письмо. Единственный буква слева - "L".

Теперь перейдите к L. Мы хотим SUNIL? Да. SUNIL были первыми вариантами, поэтому у нас есть 1! [СОЛНЦЕ] [Я] [Л] = 1! = 1

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

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

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

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

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

Слишком поздно, но просто для справки ... Вы можете напрямую использовать этот код C #.

Это будет работать, но ...

Единственное, что важно, это то, что обычно у вас должны быть уникальные значения в качестве начального набора. В противном случае у вас нет! Перестановки. У вас есть что-то еще (меньше, чем п!). Я немного сомневаюсь в каком-либо полезном использовании, когда предмет может быть повторяющимся.

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 4

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

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

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

Answer 6

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