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

Nos dan una cuerda y una permutación de la cuerda.

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.

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

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

Encuentra el rango de la palabra “stack” cuando está ordenado en orden de diccionario.

Dada la cadena de entrada como NILSU Tómese una palabra en la que tenemos que encontrar el rango. Tome “SUNIL” por ejemplo.

Ahora arregle la letra de “SUNIL” en orden alfabético.

Será. “ILNSU”.

Ahora toma la primera letra. Es”. Ahora compruebe, ¿la letra “I” es la primera letra de “SUNIL”? No. ¡El número de palabras que se pueden formar a partir de I será de 4 !, ¡así que sabemos que habrá 4! palabras antes de “SUNIL”.

I = 4! = 24

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

L = 4! = 24

Ahora ve por “N”. ¿Es esto lo que queremos? No. ¡Escriba el número de palabras que se pueden formar comenzando con “N”, una vez más 4!

N = 4! = 24

Ahora ve por “S”. es esto lo que queremos? Sí. Ahora elimine la letra de la palabra ordenada alfabéticamente. Ahora será “ILNU”

Escribe S y revisa la palabra una vez más en la lista. ¿Queremos SI? No. Entonces el número de palabras se puede formar comenzando con SI será 3!

[S]: I-> 3! = 6

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

[S]: L-> 3! = 6

Ve por N. es que queremos SN? No.

[S]: N-> 3! = 6

Ir por SU. ¿Es esto lo que queremos? Sí. Corta la letra U de la lista y luego será “ILN”. 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. entonces el número de palabras que comienzan con SUL será 2 !.

[SU]: L-> 2! = 2

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

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

Ahora agrega los números enteros que obtenemos. La sum será.

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

Entonces la palabra SUNIL estará en la posición 95 si contamos las palabras que se pueden crear usando las letras de SUNIL ordenadas en orden de diccionario.

Por lo tanto, a través de este método podrías resolver este problema bastante fácilmente.

Basándome en la respuesta de @Agorgormist, y su comentario a su respuesta, y utilizando el principio discutido en esta publicación para cuando hay letras repetidas, 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 comenté 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 utilizando su consola de herramientas de desarrollo y agrega algunos console.logs, debería poder ver cómo usa la fórmula en la publicación SO anteriormente vinculada.

Traté de 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; } 

Un poco tarde pero solo como referencia … Puede usar este código C # directamente.

Funcionará pero …

Lo único importante es que, por lo general, debe tener valores únicos como su conjunto inicial. De lo contrario, no tienes n! permutaciones. Tienes algo más (menos de n!). Tengo una pequeña duda de cualquier uso útil cuando el artículo podría ser duplicados.

 using System; using System.Collections.Generic; namespace WpfPermutations { public class PermutationOuelletLexico3 { // ************************************************************************ private T[] _sortedValues; private bool[] _valueUsed; public readonly long MaxIndex; // long to support 20! or less // ************************************************************************ public PermutationOuelletLexico3(T[] sortedValues) { if (sortedValues.Length <= 0) { throw new ArgumentException("sortedValues.Lenght should be greater than 0"); } _sortedValues = sortedValues; Result = new T[_sortedValues.Length]; _valueUsed = new bool[_sortedValues.Length]; MaxIndex = Factorial.GetFactorial(_sortedValues.Length); } // ************************************************************************ public T[] Result { get; private set; } // ************************************************************************ ///  /// Return the permutation relative to the index received, according to /// _sortedValues. /// Sort Index is 0 based and should be less than MaxIndex. Otherwise you get an exception. ///  ///  /// The result is written in property: Result public void GetValuesForIndex(long sortIndex) { int size = _sortedValues.Length; if (sortIndex < 0) { throw new ArgumentException("sortIndex should be greater or equal to 0."); } if (sortIndex >= MaxIndex) { throw new ArgumentException("sortIndex should be less than factorial(the lenght of items)"); } for (int n = 0; n < _valueUsed.Length; n++) { _valueUsed[n] = false; } long factorielLower = MaxIndex; for (int index = 0; index < size; index++) { long factorielBigger = factorielLower; factorielLower = Factorial.GetFactorial(size - index - 1); // factorielBigger / inverseIndex; int resultItemIndex = (int)(sortIndex % factorielBigger / factorielLower); int correctedResultItemIndex = 0; for(;;) { if (! _valueUsed[correctedResultItemIndex]) { resultItemIndex--; if (resultItemIndex < 0) { break; } } correctedResultItemIndex++; } Result[index] = _sortedValues[correctedResultItemIndex]; _valueUsed[correctedResultItemIndex] = true; } } // ************************************************************************ ///  /// Calc the index, relative to _sortedValues, of the permutation received /// as argument. Returned index is 0 based. ///  ///  ///  public long GetIndexOfValues(T[] values) { int size = _sortedValues.Length; long valuesIndex = 0; List valuesLeft = new List(_sortedValues); for (int index = 0; index < size; index++) { long indexFactorial = Factorial.GetFactorial(size - 1 - index); T value = values[index]; int indexCorrected = valuesLeft.IndexOf(value); valuesIndex = valuesIndex + (indexCorrected * indexFactorial); valuesLeft.Remove(value); } return valuesIndex; } // ************************************************************************ } } 

Mi enfoque del 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.

Una solución ineficiente sería encontrar sucesivamente las permutaciones previas 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 combinatoria, puede lograr la solución más rápido. La solución anterior producirá un rendimiento muy lento si la longitud de la cuerda excede 12.