Поиск ранга данной строки в списке всех возможных перестановок

Question

Я пытаюсь найти ранг данной строки в списке возможных перестановок. Я попытался найти решение, которое пытается найти все возможные перестановки, присвоить им ранг и затем отобразить его.

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

function permute(str) { 
    // Sort the string 
    var arr = []; 
    for (var i = 0; i < str.length; i++) arr.push(str[i]); 
    var sortedString = arr.sort().join(''), 
     // Length of the string 
     length = str.length, 
     used = []; 
    // Create a boolean array for length of the string 
    while (length--) used.push(false); 
    // String buffer that holds the current string 
    var out = ''; 
    // Call the function 
    doPermute(sortedString, str, out, used, str.length, 0); 
} 
var count = 0; 

function doPermute(inp, givenString, out, used, length, level) { 
    // Only if length of the string equal to current level print it 
    // That is permutation length is eqaul to string length 
    if (level == length) { 
     count++; 
     //console.log('Perm :: ' + out + ' -- ' + count); 
     if (out === givenString) { 
      var pp = 'Rank of :: ' + out + ' -- ' + count; 
      $('div').append('<p>' + pp + '</p>'); 
     } 
     return; 
    } 
    for (var i = 0; i < length; ++i) { 
     // If variable used continue 
     if (used[i]) continue; 
     // Append the current char in loop 
     out += inp[i]; 
     // set variable to true 
     used[i] = true; 
     // Call the function again 
     doPermute(inp, givenString, out, used, length, level + 1); 
     // Set it to false as the variable can be reused 
     used[i] = false; 
     // remove the last character of the buffer 
     out = out.slice(0, out.length - 1) 
    } 
} 

permute('dbcarf') 

Fiddle

Answer 1

Конечно: если входной строки "cab". Что самый низкий ранг, что строка, начиная с С может получить?

c Обратите внимание на строки, которые перед ним.

abc 
acb 
bac 
bca 

Так строка, начиная с с имеет минимальный ранг 5.This является только количество символов в строке ввода, которые приходят лексически до того с. (В порядке а, б, в, г, д, е ...) Итак, у нас есть 2. Каждое слово, начинающееся с буквы, может иметь 2 слова.
Следующее письмо - «a»?
Что такое минимальный ранг, который может получить слово, начинающееся с «ca»?
Почему?
«а» - это лучший способ заполнить второе место остальными буквами.
И то же самое касается третьего элемента «b».
Так ранг «кабины» 5.

В общем. (Предполагая, что нет дубликатов, хотя это не намного сложнее)

var W; //input string 
var C[26]; 
var rank = 1; 
for (var i = 0; i < W.length; i++) C[W[i] - 'a']++; 
for (var i = 0; i < W.length; i++) { 
    //How many characters which are not used, that come before current character 
    var count = 0; 
    for (var j = 0; j < 26; j++) { 
     if (j == (W[i] - 'a')) break; 
     if (C[j] > 0) count++; 
    } 
    C[W[i] - 'a'] = 0; 
    rank += count * fact(W.length - i - 1); 
} 

Answer 2

Существует объяснение в https://en.wikipedia.org/wiki/Permutation#Numbering_permutations о том, как преобразовать перестановка на n объектов на число в диапазоне 0..n! -1, и далее говорится, что «Преобразование последовательных натуральных чисел в систему факториалов производит эти последовательности в лексикографическом порядке (как в случае с любым смешанным числом радиуса система), и дальнейшее их преобразование в перестановки сохраняет лексикографическое упорядочение при условии, что интервал перевода Lehmer tation используется «Итак, я бы попытался сделать это преобразование чисел и посмотреть, создает ли оно что-то, относящееся к рангу, которое вам нужно, по вашему определению.