0

我试图在可能的排列列表中找到给定字符串的等级。我试图提出一个解决方案，试图找到所有可能的排列，为它们分配一个等级，然后显示它。

但是当字符串的长度不断增加时，这会大大降低性能。所以想知道是否有人能想到一个有效的解决方案来解决这个问题..

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')

小提琴

4

2 回答 2

2

当然：如果输入字符串是以"cab". c 开头的字符串可以获得的最低排名是多少？

c 注意它前面的字符串。

abc
acb
bac
bca

因此，以 c 开头的字符串具有最小等级 5。这只是输入字符串中按字典顺序出现在 c 之前的字符数。（按顺序 a、b、c、d、e、f...）所以我们有 2.Each以字母开头的单词可以有2个单词。
下一个字母是“a”？
以“ca”开头的单词可以获得的最低排名是多少？
5
为什么？
“a”是我们可以用剩余的字母填充第二个位置的最佳方式。
第三个元素“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);
 }
于 2013-07-11T18:49:39.843 回答
0

https://en.wikipedia.org/wiki/Permutation#Numbering_permutations中有关于如何将 n 个对象的排列转换为 0..n!-1 范围内的数字的解释，它接着说“将连续的自然数转换为阶乘数字系统会按字典顺序生成这些序列（就像任何混合基数系统的情况一样），如果使用 Lehmer 代码解释，则进一步将它们转换为排列可以保留字典顺序“所以我会尝试进行此数字转换，看看它是否会根据您的定义产生与您需要的排名相关的东西。

于 2013-07-11T18:55:27.220 回答