Найти индекс данной перестановки в отсортированном списке перестановок заданной строки
Нам предоставляется строка и перестановка строки.
Например, строка ввода sandeep
и перестановка psdenae
.
Найти позицию данной перестановки в отсортированном списке перестановок исходной строки.
Ответы
Ответ 1
Общее число перестановок заданной строки длины n будет n! (если все символы различны), поэтому было бы невозможно изучить все комбинации.
Этот вопрос на самом деле похож на вопрос математики P и C
Найдите ранг слова "стек", если он упорядочен в порядке словаря.
Учитывая входную строку как NILSU
Возьмите слово, которое мы должны найти в ранге. Возьмите, например, "SUNIL".
Теперь расположите букву "SUNIL" в алфавитном порядке.
Это будет. "I L N S U".
Теперь возьмите первую букву. Его "я". Теперь проверьте, есть ли буква "I" первая буква "SUNIL"? Нет. Количество слов, которые могут быть сформированы начиная с меня будет 4!, поэтому мы знаем, что будет 4! слова перед "SUNIL".
I = 4!= 24
Теперь перейдите к второй букве. Его "L" . Теперь проверьте еще раз, если это письмо, которое мы хотим на первом месте? Нет. Таким образом, количество слов может быть, начинающийся с "L" , будет 4!.
L = 4!= 24
Теперь перейдите к "N". Мы этого хотим? Нет. Запишите количество слов может быть сформировано начиная с "N", еще раз 4!
N = 4!= 24
Теперь перейдите к "S". Это то, чего мы хотим? Да. Теперь удалите письмо из алфавитно упорядоченное слово. Теперь это будет "I L N U"
Напишите S и снова проверьте слово в списке. Мы хотим СИ? Нет. Таким образом, число слов может быть сформировано начиная с SI будет 3!
[S]: I- > 3!= 6
Go для L. мы хотим SL? Нет. Так что это будет 3!.
[S]: L- > 3!= 6
Переходим на N., мы хотим SN? Нет.
[S]: N- > 3!= 6
Перейдите к SU. Мы этого хотим? Да. Вырежьте букву U из списка и то это будет "I L N". Теперь попробуй, я хочу, чтобы SUI? Нет. Так что число слов, которые начинаются с SUI, будет 2!
[SU]: I- > 2!= 2 Теперь иди за Л. Мы хотим "СУЛЬ". Нет, поэтому число слова, начинающиеся с SUL, будут равны 2!.
[SU]: L- > 2!= 2
Теперь иди за Н. Мы хотим СОЛНЦЕ? Да, теперь удалите это письмо. и это будет "I L". Мы хотим "SUNI"? Да. Удалите эту букву. Единственный буква слева - "L" .
Теперь иди для Л. Мы хотим СОЛНЦЕ? Да. SUNIL были первыми вариантами, поэтому у нас есть 1!. [SUN] [I] [L] = 1!= 1
Теперь добавьте все числа, которые мы получаем. Сумма будет.
24 + 24 + 24 + 6 + 6 + 6 + 2 + 2 + 1 = 95.
Таким образом, слово SUNIL будет на 95-й позиции, если мы посчитаем слова, которые могут быть созданы с использованием букв SUNIL, упорядоченных в порядке словаря.
Таким образом, благодаря этому методу вы могли бы легко решить эту проблему.
Ответ 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, вы сможете увидеть, как он использует формулу в вышеописанном S.O. пост.
Ответ 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;
}
Ответ 4
Мой подход к проблеме - это сортировка данной перестановки.
Количество подстановок символов в строке даст нам положение pemutation в отсортированном списке перестановок.
Ответ 5
Неэффективным решением было бы последовательно находить предыдущие перестановки до тех пор, пока вы не достигнете строки, которая больше не может быть переделана. Количество перестановок, необходимых для достижения этого состояния, - это позиция исходной строки.
Однако, если вы используете комбинаторика, вы можете быстрее достичь решения. Предыдущее решение будет выдавать очень медленный вывод, если длина строки превышает 12.