Encontrar la clasificación de una palabra (permutaciones) con letras duplicadas

Estoy publicando esto aunque ya se ha publicado mucho sobre esta pregunta. No quería publicar como respuesta ya que no está funcionando. La respuesta a esta publicación ( Encontrar el rango de la cadena dada en la lista de todas las permutaciones posibles con Duplicados ) no funcionó para mí.

Así que probé esto (que es una comstackción de código que he plagiado y mi bash de lidiar con las repeticiones). Los casos que no se repiten funcionan bien. BOOKKEEPER genera 83863, no el 10743 deseado.

(La función factorial y la matriz de contador de letras “repeticiones” funcionan correctamente. No publiqué para ahorrar espacio).

while (pointer != length) { if (sortedWordChars[pointer] != wordArray[pointer]) { // Swap the current character with the one after that char temp = sortedWordChars[pointer]; sortedWordChars[pointer] = sortedWordChars[next]; sortedWordChars[next] = temp; next++; //For each position check how many characters left have duplicates, //and use the logic that if you need to permute n things and if 'a' things //are similar the number of permutations is n!/a! int ct = repeats[(sortedWordChars[pointer]-64)]; // Increment the rank if (ct>1) { //repeats? System.out.println("repeating " + (sortedWordChars[pointer]-64)); //In case of repetition of any character use: (n-1)!/(times)! //eg if there is 1 character which is repeating twice, //x* (n-1)!/2! int dividend = getFactorialIter(length - pointer - 1); int divisor = getFactorialIter(ct); int quo = dividend/divisor; rank += quo; } else { rank += getFactorialIter(length - pointer - 1); } } else { pointer++; next = pointer + 1; } } 

Nota: esta respuesta es para clasificaciones basadas en 1, como se especifica implícitamente por ejemplo. Aquí hay algo de Python que funciona al menos para los dos ejemplos proporcionados. El hecho clave es que suffixperms * ctr[y] // ctr[x] es el número de permutaciones cuya primera letra es y del sufijo length- (i + 1) de perm .

 from collections import Counter def rankperm(perm): rank = 1 suffixperms = 1 ctr = Counter() for i in range(len(perm)): x = perm[((len(perm) - 1) - i)] ctr[x] += 1 for y in ctr: if (y < x): rank += ((suffixperms * ctr[y]) // ctr[x]) suffixperms = ((suffixperms * (i + 1)) // ctr[x]) return rank print(rankperm('QUESTION')) print(rankperm('BOOKKEEPER')) 

Versión de Java:

 public static long rankPerm(String perm) { long rank = 1; long suffixPermCount = 1; java.util.Map charCounts = new java.util.HashMap(); for (int i = perm.length() - 1; i > -1; i--) { char x = perm.charAt(i); int xCount = charCounts.containsKey(x) ? charCounts.get(x) + 1 : 1; charCounts.put(x, xCount); for (java.util.Map.Entry e : charCounts.entrySet()) { if (e.getKey() < x) { rank += suffixPermCount * e.getValue() / xCount; } } suffixPermCount *= perm.length() - i; suffixPermCount /= xCount; } return rank; } 

Cambio de permutaciones:

 from collections import Counter def unrankperm(letters, rank): ctr = Counter() permcount = 1 for i in range(len(letters)): x = letters[i] ctr[x] += 1 permcount = (permcount * (i + 1)) // ctr[x] # ctr is the histogram of letters # permcount is the number of distinct perms of letters perm = [] for i in range(len(letters)): for x in sorted(ctr.keys()): # suffixcount is the number of distinct perms that begin with x suffixcount = permcount * ctr[x] // (len(letters) - i) if rank <= suffixcount: perm.append(x) permcount = suffixcount ctr[x] -= 1 if ctr[x] == 0: del ctr[x] break rank -= suffixcount return ''.join(perm) 

Si utilizamos las matemáticas, la complejidad bajará y podrá encontrar el rango más rápido. Esto será particularmente útil para grandes cadenas. (más detalles se pueden encontrar aquí )

Sugerir definir programáticamente el enfoque que se muestra aquí (captura de pantalla adjunta a continuación) enter image description here dada a continuación)

@Dvaid Einstat, esto fue realmente útil. Me llevó un MOMENTO averiguar lo que estabas haciendo ya que todavía estoy aprendiendo mi primer idioma (C #). Lo traduje a C # y pensé que también daría esa solución, ya que esta lista me ayudó mucho.

¡Gracias!

 using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; using System.Text.RegularExpressions; namespace CsharpVersion { class Program { //Takes in the word and checks to make sure that the word //is between 1 and 25 charaters inclusive and only //letters are used static string readWord(string prompt, int high) { Regex rgx = new Regex("^[a-zA-Z]+$"); string word; string result; do { Console.WriteLine(prompt); word = Console.ReadLine(); } while (word == "" | word.Length > high | rgx.IsMatch(word) == false); result = word.ToUpper(); return result; } //Creates a sorted dictionary containing distinct letters //initialized with 0 frequency static SortedDictionary Counter(string word) { char[] wordArray = word.ToCharArray(); int len = word.Length; SortedDictionary count = new SortedDictionary(); foreach(char c in word) { if(count.ContainsKey(c)) { } else { count.Add(c, 0); } } return count; } //Creates a factorial function static int Factorial(int n) { if (n <= 1) { return 1; } else { return n * Factorial(n - 1); } } //Ranks the word input if there are no repeated charaters //in the word static Int64 rankWord(char[] wordArray) { int n = wordArray.Length; Int64 rank = 1; //loops through the array of letters for (int i = 0; i < n-1; i++) { int x=0; //loops all letters after i and compares them for factorial calculation for (int j = i+1; j wordArray[j]) { x++; } } rank = rank + x * (Factorial(n - i - 1)); } return rank; } //Ranks the word input if there are repeated charaters //in the word static Int64 rankPerm(String word) { Int64 rank = 1; Int64 suffixPermCount = 1; SortedDictionary counter = Counter(word); for (int i = word.Length - 1; i > -1; i--) { char x = Convert.ToChar(word.Substring(i,1)); int xCount; if(counter[x] != 0) { xCount = counter[x] + 1; } else { xCount = 1; } counter[x] = xCount; foreach (KeyValuePair e in counter) { if (e.Key < x) { rank += suffixPermCount * e.Value / xCount; } } suffixPermCount *= word.Length - i; suffixPermCount /= xCount; } return rank; } static void Main(string[] args) { Console.WriteLine("Type Exit to end the program."); string prompt = "Please enter a word using only letters:"; const int MAX_VALUE = 25; Int64 rank = new Int64(); string theWord; do { theWord = readWord(prompt, MAX_VALUE); char[] wordLetters = theWord.ToCharArray(); Array.Sort(wordLetters); bool duplicate = false; for(int i = 0; i< theWord.Length - 1; i++) { if(wordLetters[i] < wordLetters[i+1]) { duplicate = true; } } if(duplicate) { SortedDictionary counter = Counter(theWord); rank = rankPerm(theWord); Console.WriteLine("\n" + theWord + " = " + rank); } else { char[] letters = theWord.ToCharArray(); rank = rankWord(letters); Console.WriteLine("\n" + theWord + " = " + rank); } } while (theWord != "EXIT"); Console.WriteLine("\nPress enter to escape.."); Console.Read(); } } } 

Diría que la publicación de David (la respuesta aceptada) es súper genial. Sin embargo, me gustaría mejorarlo aún más por la velocidad. El lazo interno está tratando de encontrar pares de orden inverso, y para cada orden inverso, intenta contribuir al incremento de rango. Si utilizamos una estructura de mapa ordenada (árbol de búsqueda binaria o BST) en ese lugar, podemos simplemente hacer un recorrido inorden desde el primer nodo (abajo a la izquierda) hasta que scope el carácter actual en la BST, en lugar de atravesarlo por el todo mapa (BST). En C ++, std :: map es perfecto para la implementación de BST. El siguiente código reduce las iteraciones necesarias en el ciclo y elimina la verificación if.

 long long rankofword(string s) { long long rank = 1; long long suffixPermCount = 1; map m; int size = s.size(); for (int i = size - 1; i > -1; i--) { char x = s[i]; m[x]++; for (auto it = m.begin(); it != m.find(x); it++) rank += suffixPermCount * it->second / m[x]; suffixPermCount *= (size - i); suffixPermCount /= m[x]; } return rank; } 

Si hay k caracteres distintos, el carácter i ^ th se repite n_i veces, luego el número total de permutaciones viene dado por

  (n_1 + n_2 + ..+ n_k)! ------------------------------------------------ n_1! n_2! ... n_k! 

que es el coeficiente multinomial.
Ahora podemos usar esto para calcular el rango de una permutación dada de la siguiente manera:

Considera el primer personaje (a la izquierda). dicen que fue el r ^ th en el orden de los caracteres ordenados.

Ahora bien, si reemplaza el primer carácter por cualquiera de los caracteres 1,2,3, …, (r-1) ^ th y considera todas las permutaciones posibles, cada una de estas permutaciones precederá a la permutación dada. El número total se puede calcular usando la fórmula anterior.

Una vez que calcule el número del primer personaje, arregle el primer carácter y repita el mismo con el segundo carácter, y así sucesivamente.

Aquí está la implementación de C ++ para su pregunta

 #include using namespace std; int fact(int f) { if (f == 0) return 1; if (f <= 2) return f; return (f * fact(f - 1)); } int solve(string s,int n) { int ans = 1; int arr[26] = {0}; int len = n - 1; for (int i = 0; i < n; i++) { s[i] = toupper(s[i]); arr[s[i] - 'A']++; } for(int i = 0; i < n; i++) { int temp = 0; int x = 1; char c = s[i]; for(int j = 0; j < c - 'A'; j++) temp += arr[j]; for (int j = 0; j < 26; j++) x = (x * fact(arr[j])); arr[c - 'A']--; ans = ans + (temp * ((fact(len)) / x)); len--; } return ans; } int main() { int i,n; string s; cin>>s; n=s.size(); cout << solve(s,n); return 0; }