Encuentra el índice de una permutación dada en la lista ordenada de las permutaciones de una cadena dada

Question

Nos da una cadena y una permutación de la cadena. Por ejemplo, una cadena de entrada sandeep y una permutación psdenae.

Encuentra la posición de la permutación dada en la lista ordenada de las permutaciones de la cadena original.

Answer 1

El número total de permutación de una cadena dada de longitud n sería n! (si todos los caracteres son diferentes), por lo tanto, no sería posible explorar todas las combinaciones.

Esta pregunta es en realidad como la pregunta de las matemáticas P & C

Encontrar el rango de la palabra "pila" cuando se organizó con el fin diccionario.

Teniendo en cuenta la cadena de entrada como Nilsu Tome una palabra que tenemos que encontrar la fila. Tome "SUNIL" por ejemplo.

Ahora organice la letra de "SUNIL" en orden alfabético.

Será. "I L N S U".

Ahora tome la primera letra. Es". Ahora compruebe, ¿la letra "I" es la primera letra de "SUNIL" ? No. La cantidad de palabras que se pueden formar comenzando con I will be 4, ¡así que sabemos que habrá 4! palabras antes de "SUNIL".

I = 4! = 24

Ahora ve por la segunda letra. Soy yo". Ahora compruebe una vez más si esta carta queremos en primera posición? No. Entonces el número de palabras puede ser formado comenzando con "L" será 4 !.

L = 4! = 24

Ahora vaya por "N". ¿Es esto lo que queremos? No. Escriba el número de palabras se puede formar a partir de "N", una vez más 4!

N = 4! = 24

Ahora vaya por "S". es esto lo que queremos? Sí. Ahora elimine la letra de la palabra ordenada alfabéticamente.Ahora será "I L N U"

Escriba S y verifique la palabra una vez más en la lista. ¿Queremos SI? No. ¡De modo que el número de palabras que se puede formar a partir de SI será 3!

[S]: I-> 3! = 6

Ir para L. es que queremos SL? No. Entonces será 3 !.

[S]: L-> 3! = 6

Ir para N. es que queremos SN? No.

[S]: N-> 3! = 6

Vaya para SU. ¿Es esto lo que queremos? Sí. Corta la letra U de la lista y y luego será "I L N". Ahora inténtalo. ¿Queremos SUI? No. Entonces, se puede formar el número de palabras que comienza desde SUI será 2!

[SU]: I-> 2! = 2 Ahora ve por L. ¿Queremos "SUL"? No. por lo que el número de palabras que comienzan con SUL será 2 !.

[SU]: L-> 2! = 2

Ahora ve a N. ¿Queremos SUN? Sí, ahora quita esa letra. y este será "I L". ¿Queremos "SUNI"? Sí. Eliminar esa letra. La única letra que queda es "L".

Ahora vamos por L. ¿Queremos SUNIL? Sí. SUNIL fueron las primeras opciones, así que tenemos 1 !. [SUN] [I] [L] = 1! = 1

Ahora agregue los números enteros que obtenemos. La suma será.

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

Así que la palabra SUNIL estará en la posición 95ª si contamos las palabras que pueden ser creadas usando la cartas de SUNIL arregladas en orden de diccionario.

Por lo tanto, a través de este método podría resolver este problema con bastante facilidad.

Answer 2

Mi enfoque al problema es ordenar la permutación dada. El número de modificaciones de los caracteres en la cadena nos dará la posición de la pemutación en la lista ordenada de permutaciones.

Answer 3

Una solución ineficiente sería encontrar sucesivamente las permutaciones anteriores hasta llegar a una cadena que ya no se puede permutar. El número de permutaciones necesarias para alcanzar este estado es la posición de la cadena original.

Sin embargo, si usa la combinatoria, puede lograr la solución más rápido. La solución anterior producirá una salida muy lenta si la longitud de la cadena excede 12.

Answer 4

Intenté implementar esto en js. Funciona para cadenas que no tienen letras repetidas pero de lo contrario recibo una cuenta equivocada. Aquí está mi código:

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

Construido a partir respuesta @Algorithmist 's, y su comentario a su respuesta, y utilizando el principio discutido en this post para las cartas cuando no se repiten, hice el siguiente algoritmo en JavaScript que funciona para todas las palabras basadas en letras incluso con instancias de letras repetidas.

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 

No he comentado el código pero intenté hacer que los nombres de las variables fueran lo más explicativos posible. Si lo ejecuta a través de un proceso de depuración usando su consola de herramientas de desarrollo y agrega algunos console.logs, debería poder ver cómo usa la fórmula en el S.O. enviar.