किसी दिए गए स्ट्रिंग

Question

के क्रमपरिवर्तन की क्रमबद्ध सूची में दिए गए क्रमपरिवर्तन की अनुक्रमणिका खोजें हमें स्ट्रिंग और स्ट्रिंग का क्रमपरिवर्तन दिया गया है।

उदाहरण के लिए, एक इनपुट स्ट्रिंग sandeep और क्रमपरिवर्तन psdenae।

मूल स्ट्रिंग के क्रमपरिवर्तन की क्रमबद्ध सूची में दिए गए क्रमपरिवर्तन की स्थिति पाएं।

Answer 1

लंबाई एन की दी गई स्ट्रिंग के क्रमपरिवर्तन की कुल संख्या n होगी! (यदि सभी वर्ण अलग हैं), तो इस तरह सभी संयोजनों का पता लगाना संभव नहीं होगा।

यह सवाल वास्तव में गणित पी & सी सवाल

शब्द "ढेर" जब शब्दकोश क्रम में व्यवस्थित के पद का पता लगाएं की तरह है।

इनपुट स्ट्रिंग को देखते हुए के रूप में NILSU एक शब्द है जो हम रैंक खोजने के लिए ले लो। उदाहरण के लिए "सुनील" लें।

अब वर्णमाला क्रम में "सुनील" का पत्र व्यवस्थित करें।

यह होगा। "आई एल एन एस यू"।

अब पहला अक्षर लें। इसका "मैं"। अब जांचें, क्या पत्र "I" "सुनील" का पहला अक्षर है? नहीं। के साथ शुरू होने वाले शब्दों की संख्या 4 होगी, इसलिए हम जानते हैं कि 4 होगा! "सुनील" से पहले शब्द।

I = 4! = 24

अब दूसरे अक्षर के लिए जाएं। इसका "एल"। अब एक बार फिर से जांचें यदि यह पत्र जो हम पहली स्थिति में चाहते हैं? नहीं। इसलिए शब्दों की संख्या हो सकती है जो "एल" से शुरू होकर 4 हो जाएगी!

एल = 4! = 24

अब "एन" के लिए जाएं। क्या हम चाहते हैं? नहीं। शब्दों की संख्या लिखें, "एन" से शुरू होकर, एक बार फिर 4!

एन = 4! = 24

अब "एस" के लिए जाएं। क्या यही है जो हमें चाहिए? हाँ। अब वर्णमाला क्रमबद्ध शब्द से पत्र हटा दें।अब यह "आई एल एन यू"

एस लिखें और सूची में एक बार फिर से शब्द की जांच करें। क्या हम एसआई चाहते हैं? सं। तो एसआई के साथ शुरू होने वाले शब्दों की संख्या 3 हो जाएगी!

[एस]: I-> 3! = 6

एल के लिए जाएं। क्या हम एसएल चाहते हैं? नहीं तो यह 3 होगा!

[एस]: एल-> 3! = 6

एन के लिए जाएं क्या हम एसएन चाहते हैं? संख्या

[एस]: एन-> 3! = 6

एसयू के लिए जाएं। क्या हम चाहते हैं? हाँ। सूची यू को अक्षर से हटाएं और फिर यह "आई एल एन" होगा। अब कोशिश करें। क्या हम एसयूआई चाहते हैं? नहीं। इसलिए शब्दों का गठन किया जा सकता है जो एसयूआई से शुरू होता है 2 होगा!

[एसयू]: I-> 2! = 2 अब एल के लिए जाओ। क्या हम "एसयूएल" चाहते हैं। नहीं। इसलिए एसयूएल से शुरू होने वाले शब्दों की संख्या 2 होगी!

[एसयू]: एल-> 2! = 2

अब एन के लिए जाएं। क्या हम सूर्य चाहते हैं? हाँ, अब उस पत्र को हटा दें। और यह "आई एल" होगा। क्या हम "सुनी" चाहते हैं? हाँ। उस पत्र को हटा दें। केवल पत्र शेष "एल" है।

अब एल के लिए जाएं। क्या हम सुनील चाहते हैं? हाँ। सुनील पहले विकल्प थे, इसलिए हमारे पास 1 है! [सूर्य] [मैं] [एल] = 1! = 1

अब हमें मिलने वाली पूरी संख्या जोड़ें। योग होगा।

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

तो शब्द सुनील 95 वें स्थान पर हो सकता है अगर ऐसे शब्द हैं जो का उपयोग कर बनाया जा सकता है गिनती शब्दकोश आदेश में व्यवस्थित सुनील के पत्र।

इस प्रकार इस विधि के माध्यम से आप इस समस्या को आसानी से हल कर सकते हैं।

Answer 2

समस्या का मेरा दृष्टिकोण दिया गया क्रमपरिवर्तन क्रमबद्ध है। स्ट्रिंग में वर्णों के स्वैपिंग की संख्या हमें क्रमपरिवर्तन की क्रमबद्ध सूची में क्रमपरिवर्तन की स्थिति प्रदान करेगी।

Answer 3

एक अक्षम समाधान तब तक पिछली क्रमिकता को तब तक खोजना होगा जब तक आप उस स्ट्रिंग तक नहीं पहुंच जाते जिसे अब अनुमति नहीं दी जा सकती है। इस राज्य तक पहुंचने के लिए किए गए क्रमिक क्रम की संख्या मूल स्ट्रिंग की स्थिति है।

हालांकि, यदि आप संयोजक का उपयोग करते हैं तो आप समाधान को तेज़ी से प्राप्त कर सकते हैं। पिछला समाधान स्ट्रिंग लम्बाई से अधिक होने पर बहुत धीमी आउटपुट उत्पन्न करेगा 12.

Answer 4

मैंने इसे जेएस में लागू करने की कोशिश की। यह स्ट्रिंग के लिए काम करता है जिसमें दोहराए गए अक्षरों नहीं हैं लेकिन मुझे गलत गिनती मिलती है। यहाँ मेरी कोड है:

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.logs में फेंकते हैं तो आपको यह देखने में सक्षम होना चाहिए कि यह उपरोक्त लिंक एसओ में सूत्र का उपयोग कैसे करता है। पद।