在給定字符串排列的排序列表中查找給定排列的索引

Question

我們給出了字符串和字符串的排列。

例如，輸入字符串sandeep和排列psdenae。

在原始字符串排列的排序列表中查找給定排列的位置。

Answer 1

給定長度爲n的字符串的排列總數爲n！（如果所有字符都不相同），因此無法探索所有組合。

這個問題實際上是像數學P &Ç問題

查找排列字典順序這個詞的時候「堆棧」的行列。

鑑於輸入字符串作爲NILSU 就拿我們必須找到軍銜一個字。以「SUNIL」爲例。

現在按字母順序排列「SUNIL」的字母。

它會的。 「I L N S U」。

現在拿第一個字母。它的「我」。現在檢查，是字母「我」 「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嗎？因此，可以用SI開始形成的詞的數目將是3！

[S]：I-> 3！ = 6

Go for L. is we want SL？不，所以它會是3 !.

[S]：L-> 3！ = 6

轉到N.是我們想要SN？ No.

[S]：N-> 3！ = 6

前往SU。這是我們想要的嗎？是。從列表中刪除字母U並且 然後它將是「I L N」。現在試試我們是不是想要SUI？所以可以形成從SUI開始的字數 2！

[SU]：I-> 2！ = 2現在去L.我們是否想要「SUL」。因此，以SUL開頭的 單詞的數目將爲2 !.

[SU]：L-> 2！ = 2

現在去爭取N.是否我們想要SUN？是的，現在刪除那封信。而這個 將是「I L」。我們想要「SUNI」嗎？是。刪除那封信。剩下的唯一 字母是「L」。

現在去找L.我們想要SUNIL嗎？是。 SUNIL是第一個選項，所以我們有1個！ [SUN] [I] [L] = 1！ = 1

現在添加我們得到的全部數字。總和將是。

24 + 24 + 24 + 6 + 6 + 6 + 2 + 2 + 1 = 95。

所以字SUNIL將在第95個位置，如果我們計數，可以使用被創建的話SUNIL的字母按字典順序排列。

因此通過這種方法可以很容易地解決這個問題。

Answer 2

我對問題的解決方法是對給定的排列進行排序。 字符串中字符的插入次數將給我們排列的排序列表中的位置。

Answer 3

一個低效率的解決方案將是先後找到先前的排列，直到你到達一個不能被置換的字符串。達到此狀態所需的排列數是原始字符串的位置。

但是，如果您使用組合語言，則可以更快地實現解決方案。如果字符串長度超過12，以前的解決方案將產生非常慢的輸出。

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

建設關@Algorithmist的回答，他到他的回答評論，使用this post討論的原則時，有重複的字母，我做在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.log，則應該能夠看到它如何使用上述鏈接的S.O.中的公式。帖子。