Dada una string, encuentre su rango entre todas sus permutaciones ordenadas lexicográficamente. Por ejemplo, el rango de «abc» es 1, el rango de «acb» es 2 y el rango de «cba» es 6.
Ejemplos:
Input : str[] = "acb" Output : Rank = 2 Input : str[] = "string" Output : Rank = 598 Input : str[] = "cba" Output : Rank = 6
Para simplificar, supongamos que la string no contiene ningún carácter duplicado.
Una solución simple es inicializar el rango como 1, generar todas las permutaciones en orden lexicográfico . Después de generar una permutación, verifique si la permutación generada es la misma que la string dada, si es igual, luego devuelva el rango, si no, incremente el rango en 1. La complejidad del tiempo de esta solución será exponencial en el peor de los casos. La siguiente es una solución eficiente.
Deje que la string dada sea «CADENA». En la string de entrada, ‘S’ es el primer carácter.
Hay un total de 6 caracteres y 4 de ellos son más pequeños que ‘S’.
¡Entonces puede haber 4 * 5! strings más pequeñas donde el primer carácter es más pequeño que ‘S’, como seguir a
R XXXXX
IXXXXX
NXXXXX
GXXXXX
Ahora corrijamos ‘S’ y encontremos las strings más pequeñas que comienzan con ‘S’.
Repita el mismo proceso para T, ¡la clasificación es 4*5! + 4*4! +…
Ahora corrija T y repita el mismo proceso para R, ¡el rango es 4*5! + 4*4! + 3*3! +…
Ahora corrija R y repita el mismo proceso para I, ¡el rango es 4*5! + 4*4! + 3*3! + 1*2! +…
Ahora arregla I y repite el mismo proceso para N, ¡el rango es 4*5! + 4*4! + 3*3! + 1*2! + 1*1! +…
Ahora corrija N y repita el mismo proceso para G, ¡el rango es 4*5! + 4*4! + 3*3! + 1*2! + 1*1! + 0*0!
Rango = 4*5! + 4*4! + 3*3! + 1*2! + 1*1! + 0*0! = 597
Tenga en cuenta que los cálculos anteriores encuentran el recuento de strings más pequeñas.
Por lo tanto, el rango de la string dada es el conteo de strings más pequeñas más 1.
El rango final = 1 + 597 = 598
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find lexicographic rank
// of a string
#include <bits/stdc++.h>
#include <string.h>
using namespace std;
// A utility function to find factorial of n
int fact(int n)
{
return (n <= 1) ? 1 : n * fact(n - 1);
}
// A utility function to count smaller characters on right
// of arr[low]
int findSmallerInRight(char* str, int low, int high)
{
int countRight = 0, i;
for (i = low + 1; i <= high; ++i)
if (str[i] < str[low])
++countRight;
return countRight;
}
// A function to find rank of a string in all permutations
// of characters
int findRank(char* str)
{
int len = strlen(str);
int mul = fact(len);
int rank = 1;
int countRight;
int i;
for (i = 0; i < len; ++i) {
mul /= len - i;
// count number of chars smaller than str[i]
// from str[i+1] to str[len-1]
countRight = findSmallerInRight(str, i, len - 1);
rank += countRight * mul;
}
return rank;
}
// Driver program to test above function
int main()
{
char str[] = "string";
cout << findRank(str);
return 0;
}
// This code is contributed
// by Akanksha Rai
C
// C program to find lexicographic rank
// of a string
#include <stdio.h>
#include <string.h>
// A utility function to find factorial of n
int fact(int n)
{
return (n <= 1) ? 1 : n * fact(n - 1);
}
// A utility function to count smaller characters on right
// of arr[low]
int findSmallerInRight(char* str, int low, int high)
{
int countRight = 0, i;
for (i = low + 1; i <= high; ++i)
if (str[i] < str[low])
++countRight;
return countRight;
}
// A function to find rank of a string in all permutations
// of characters
int findRank(char* str)
{
int len = strlen(str);
int mul = fact(len);
int rank = 1;
int countRight;
int i;
for (i = 0; i < len; ++i) {
mul /= len - i;
// count number of chars smaller than str[i]
// from str[i+1] to str[len-1]
countRight = findSmallerInRight(str, i, len - 1);
rank += countRight * mul;
}
return rank;
}
// Driver program to test above function
int main()
{
char str[] = "string";
printf("%d", findRank(str));
return 0;
}
Java
// Java program to find lexicographic rank
// of a string
import java.io.*;
import java.util.*;
class GFG {
// A utility function to find factorial of n
static int fact(int n)
{
return (n <= 1) ? 1 : n * fact(n - 1);
}
// A utility function to count smaller
// characters on right of arr[low]
static int findSmallerInRight(String str, int low,
int high)
{
int countRight = 0, i;
for (i = low + 1; i <= high; ++i)
if (str.charAt(i) < str.charAt(low))
++countRight;
return countRight;
}
// A function to find rank of a string in
// all permutations of characters
static int findRank(String str)
{
int len = str.length();
int mul = fact(len);
int rank = 1;
int countRight;
for (int i = 0; i < len; ++i) {
mul /= len - i;
// count number of chars smaller
// than str[i] from str[i+1] to
// str[len-1]
countRight = findSmallerInRight(str, i, len - 1);
rank += countRight * mul;
}
return rank;
}
// Driver program to test above function
public static void main(String[] args)
{
String str = "string";
System.out.println(findRank(str));
}
}
// This code is contributed by Nikita Tiwari.
Python3
# Python program to find lexicographic # rank of a string # A utility function to find factorial # of n def fact(n) : f = 1 while n >= 1 : f = f * n n = n - 1 return f # A utility function to count smaller # characters on right of arr[low] def findSmallerInRight(st, low, high) : countRight = 0 i = low + 1 while i <= high : if st[i] < st[low] : countRight = countRight + 1 i = i + 1 return countRight # A function to find rank of a string # in all permutations of characters def findRank (st) : ln = len(st) mul = fact(ln) rank = 1 i = 0 while i < ln : mul = mul // (ln - i) # count number of chars smaller # than str[i] from str[i + 1] to # str[len-1] countRight = findSmallerInRight(st, i, ln-1) rank = rank + countRight * mul i = i + 1 return rank # Driver program to test above function st = "string" print (findRank(st)) # This code is contributed by Nikita Tiwari.
C#
// C# program to find lexicographic rank
// of a string
using System;
class GFG {
// A utility function to find factorial of n
static int fact(int n)
{
return (n <= 1) ? 1 : n * fact(n - 1);
}
// A utility function to count smaller
// characters on right of arr[low]
static int findSmallerInRight(string str,
int low, int high)
{
int countRight = 0, i;
for (i = low + 1; i <= high; ++i)
if (str[i] < str[low])
++countRight;
return countRight;
}
// A function to find rank of a string in
// all permutations of characters
static int findRank(string str)
{
int len = str.Length;
int mul = fact(len);
int rank = 1;
int countRight;
for (int i = 0; i < len; ++i) {
mul /= len - i;
// count number of chars smaller
// than str[i] from str[i+1] to
// str[len-1]
countRight = findSmallerInRight(str,
i, len - 1);
rank += countRight * mul;
}
return rank;
}
// Driver program to test above function
public static void Main()
{
string str = "string";
Console.Write(findRank(str));
}
}
// This code is contributed nitin mittal.
PHP
<?php
// A utility function to find factorial of n
function fact($n)
{
return ($n <= 1) ? 1 :$n * fact($n - 1);
}
// A utility function to count smaller
// characters on right of arr[low]
function findSmallerInRight($str, $low, $high)
{
$countRight = 0;
for ($i = $low + 1; $i <= $high; ++$i)
if ($str[$i] < $str[$low])
++$countRight;
return $countRight;
}
// A function to find rank of a string
// in all permutations of characters
function findRank ($str)
{
$len = strlen($str);
$mul = fact($len);
$rank = 1;
for ($i = 0; $i < $len; ++$i)
{
$mul /= $len - $i;
// count number of chars smaller than
// str[i] from str[i+1] to str[len-1]
$countRight = findSmallerInRight($str, $i,
$len - 1);
$rank += $countRight * $mul ;
}
return $rank;
}
// Driver Code
$str = "string";
echo findRank($str);
// This code is contributed by ChitraNayal
?>
Javascript
<script>
// JavaScript program to find lexicographic rank
// A utility function to find factorial of n
function fact(n)
{
return (n <= 1) ? 1 : n * fact(n - 1);
}
// A utility function to count smaller
// characters on right of arr[low]
function findSmallerInRight(str, low, high)
{
let countRight = 0;
let i;
for(i = low + 1; i <= high; ++i)
if (str[i] < str[low])
++countRight;
return countRight;
}
// A function to find rank of a string
// in all permutations of characters
function findRank(str)
{
let len = (str).length;
let mul = fact(len);
let rank = 1;
let countRight;
let i;
for(i = 0; i < len; ++i)
{
mul /= len - i;
// count number of chars smaller than str[i]
// from str[i+1] to str[len-1]
countRight = findSmallerInRight(str, i, len - 1);
rank += countRight * mul;
}
return rank;
}
// Driver code
let str = "string";
document.write(findRank(str));
// This code is contributed by rohan07
</script>
Producción
598
La complejidad temporal de la solución anterior es O(n^2). Podemos reducir la complejidad del tiempo a O(n) creando una array auxiliar de tamaño 256. Consulte el siguiente código.
C++
// A O(n) solution for finding rank of string
#include <bits/stdc++.h>
using namespace std;
#define MAX_CHAR 256
// A utility function to find factorial of n
int fact(int n)
{
return (n <= 1) ? 1 : n * fact(n - 1);
}
// Construct a count array where value at every index
// contains count of smaller characters in whole string
void populateAndIncreaseCount(int* count, char* str)
{
int i;
for (i = 0; str[i]; ++i)
++count[str[i]];
for (i = 1; i < MAX_CHAR; ++i)
count[i] += count[i - 1];
}
// Removes a character ch from count[] array
// constructed by populateAndIncreaseCount()
void updatecount(int* count, char ch)
{
int i;
for (i = ch; i < MAX_CHAR; ++i)
--count[i];
}
// A function to find rank of a string in all permutations
// of characters
int findRank(char* str)
{
int len = strlen(str);
int mul = fact(len);
int rank = 1, i;
// all elements of count[] are initialized with 0
int count[MAX_CHAR] = { 0 };
// Populate the count array such that count[i]
// contains count of characters which are present
// in str and are smaller than i
populateAndIncreaseCount(count, str);
for (i = 0; i < len; ++i) {
mul /= len - i;
// count number of chars smaller than str[i]
// from str[i+1] to str[len-1]
rank += count[str[i] - 1] * mul;
// Reduce count of characters greater than str[i]
updatecount(count, str[i]);
}
return rank;
}
// Driver program to test above function
int main()
{
char str[] = "string";
cout << findRank(str);
return 0;
}
// This is code is contributed by rathbhupendra
C
// A O(n) solution for finding rank of string
#include <stdio.h>
#include <string.h>
#define MAX_CHAR 256
// A utility function to find factorial of n
int fact(int n)
{
return (n <= 1) ? 1 : n * fact(n - 1);
}
// Construct a count array where value at every index
// contains count of smaller characters in whole string
void populateAndIncreaseCount(int* count, char* str)
{
int i;
for (i = 0; str[i]; ++i)
++count[str[i]];
for (i = 1; i < MAX_CHAR; ++i)
count[i] += count[i - 1];
}
// Removes a character ch from count[] array
// constructed by populateAndIncreaseCount()
void updatecount(int* count, char ch)
{
int i;
for (i = ch; i < MAX_CHAR; ++i)
--count[i];
}
// A function to find rank of a string in all permutations
// of characters
int findRank(char* str)
{
int len = strlen(str);
int mul = fact(len);
int rank = 1, i;
// all elements of count[] are initialized with 0
int count[MAX_CHAR] = { 0 };
// Populate the count array such that count[i]
// contains count of characters which are present
// in str and are smaller than i
populateAndIncreaseCount(count, str);
for (i = 0; i < len; ++i) {
mul /= len - i;
// count number of chars smaller than str[i]
// from str[i+1] to str[len-1]
rank += count[str[i] - 1] * mul;
// Reduce count of characters greater than str[i]
updatecount(count, str[i]);
}
return rank;
}
// Driver program to test above function
int main()
{
char str[] = "string";
printf("%d", findRank(str));
return 0;
}
Java
// A O(n) solution for finding rank of string
class GFG {
static int MAX_CHAR = 256;
// A utility function to find factorial of n
static int fact(int n)
{
return (n <= 1) ? 1 : n * fact(n - 1);
}
// Construct a count array where value at every index
// contains count of smaller characters in whole string
static void populateAndIncreaseCount(int[] count, char[] str)
{
int i;
for (i = 0; i < str.length; ++i)
++count[str[i]];
for (i = 1; i < MAX_CHAR; ++i)
count[i] += count[i - 1];
}
// Removes a character ch from count[] array
// constructed by populateAndIncreaseCount()
static void updatecount(int[] count, char ch)
{
int i;
for (i = ch; i < MAX_CHAR; ++i)
--count[i];
}
// A function to find rank of a string in all permutations
// of characters
static int findRank(char[] str)
{
int len = str.length;
int mul = fact(len);
int rank = 1, i;
// all elements of count[] are initialized with 0
int count[] = new int[MAX_CHAR];
// Populate the count array such that count[i]
// contains count of characters which are present
// in str and are smaller than i
populateAndIncreaseCount(count, str);
for (i = 0; i < len; ++i) {
mul /= len - i;
// count number of chars smaller than str[i]
// from str[i+1] to str[len-1]
rank += count[str[i] - 1] * mul;
// Reduce count of characters greater than str[i]
updatecount(count, str[i]);
}
return rank;
}
// Driver code
public static void main(String args[])
{
char str[] = "string".toCharArray();
System.out.println(findRank(str));
}
}
// This code has been contributed by 29AjayKumar
Python3
# A O(n) solution for finding rank of string MAX_CHAR=256; # all elements of count[] are initialized with 0 count=[0]*(MAX_CHAR + 1); # A utility function to find factorial of n def fact(n): return 1 if(n <= 1) else (n * fact(n - 1)); # Construct a count array where value at every index # contains count of smaller characters in whole string def populateAndIncreaseCount(str): for i in range(len(str)): count[ord(str[i])]+=1; for i in range(1,MAX_CHAR): count[i] += count[i - 1]; # Removes a character ch from count[] array # constructed by populateAndIncreaseCount() def updatecount(ch): for i in range(ord(ch),MAX_CHAR): count[i]-=1; # A function to find rank of a string in all permutations # of characters def findRank(str): len1 = len(str); mul = fact(len1); rank = 1; # Populate the count array such that count[i] # contains count of characters which are present # in str and are smaller than i populateAndIncreaseCount(str); for i in range(len1): mul = mul//(len1 - i); # count number of chars smaller than str[i] # from str[i+1] to str[len-1] rank += count[ord(str[i]) - 1] * mul; # Reduce count of characters greater than str[i] updatecount(str[i]); return rank; # Driver code str = "string"; print(findRank(str)); # This is code is contributed by chandan_jnu
C#
// A O(n) solution for finding rank of string
using System;
class GFG {
static int MAX_CHAR = 256;
// A utility function to find factorial of n
static int fact(int n)
{
return (n <= 1) ? 1 : n * fact(n - 1);
}
// Construct a count array where value at every index
// contains count of smaller characters in whole string
static void populateAndIncreaseCount(int[] count, char[] str)
{
int i;
for (i = 0; i < str.Length; ++i)
++count[str[i]];
for (i = 1; i < MAX_CHAR; ++i)
count[i] += count[i - 1];
}
// Removes a character ch from count[] array
// constructed by populateAndIncreaseCount()
static void updatecount(int[] count, char ch)
{
int i;
for (i = ch; i < MAX_CHAR; ++i)
--count[i];
}
// A function to find rank of a string in all permutations
// of characters
static int findRank(char[] str)
{
int len = str.Length;
int mul = fact(len);
int rank = 1, i;
// all elements of count[] are initialized with 0
int[] count = new int[MAX_CHAR];
// Populate the count array such that count[i]
// contains count of characters which are present
// in str and are smaller than i
populateAndIncreaseCount(count, str);
for (i = 0; i < len; ++i) {
mul /= len - i;
// count number of chars smaller than str[i]
// from str[i+1] to str[len-1]
rank += count[str[i] - 1] * mul;
// Reduce count of characters greater than str[i]
updatecount(count, str[i]);
}
return rank;
}
// Driver code
public static void Main(String[] args)
{
char[] str = "string".ToCharArray();
Console.WriteLine(findRank(str));
}
}
/* This code contributed by PrinciRaj1992 */
PHP
<?php
// A O(n) solution for finding rank of string
$MAX_CHAR=256;
// A utility function to find factorial of n
function fact($n)
{
return ($n <= 1) ? 1 : $n * fact($n - 1);
}
// Construct a count array where value at every index
// contains count of smaller characters in whole string
function populateAndIncreaseCount(&$count, $str)
{
global $MAX_CHAR;
for ($i = 0; $i < strlen($str); ++$i)
++$count[ord($str[$i])];
for ($i = 1; $i < $MAX_CHAR; ++$i)
$count[$i] += $count[$i - 1];
}
// Removes a character ch from count[] array
// constructed by populateAndIncreaseCount()
function updatecount(&$count, $ch)
{
global $MAX_CHAR;
for ($i = ord($ch); $i < $MAX_CHAR; ++$i)
--$count[$i];
}
// A function to find rank of a string in all permutations
// of characters
function findRank($str)
{
global $MAX_CHAR;
$len = strlen($str);
$mul = fact($len);
$rank = 1;
// all elements of count[] are initialized with 0
$count=array_fill(0, $MAX_CHAR + 1, 0);
// Populate the count array such that count[i]
// contains count of characters which are present
// in str and are smaller than i
populateAndIncreaseCount($count, $str);
for ($i = 0; $i < $len; ++$i)
{
$mul = (int)($mul/($len - $i));
// count number of chars smaller than str[i]
// from str[i+1] to str[len-1]
$rank += $count[ord($str[$i]) - 1] * $mul;
// Reduce count of characters greater than str[i]
updatecount($count, $str[$i]);
}
return $rank;
}
// Driver code
$str = "string";
echo findRank($str);
// This is code is contributed by chandan_jnu
?>
Javascript
<script>
// A O(n) solution for finding rank of string
let MAX_CHAR = 256;
// A utility function to find factorial of n
function fact(n)
{
return (n <= 1) ? 1 : n * fact(n - 1);
}
// Construct a count array where value at every index
// contains count of smaller characters in whole string
function populateAndIncreaseCount(count,str)
{
let i;
for (i = 0; i < str.length; ++i)
++count[str[i].charCodeAt(0)];
for (i = 1; i < MAX_CHAR; ++i)
count[i] += count[i - 1];
}
// Removes a character ch from count[] array
// constructed by populateAndIncreaseCount()
function updatecount(count,ch)
{
let i;
for (i = ch.charCodeAt(0); i < MAX_CHAR; ++i)
--count[i];
}
// A function to find rank of a string in all permutations
// of characters
function findRank(str)
{
let len = str.length;
let mul = fact(len);
let rank = 1, i;
// all elements of count[] are initialized with 0
let count = new Array(MAX_CHAR);
for(let i = 0; i < count.length; i++)
{
count[i] = 0;
}
// Populate the count array such that count[i]
// contains count of characters which are present
// in str and are smaller than i
populateAndIncreaseCount(count, str);
for (i = 0; i < len; ++i) {
mul = Math.floor(mul/(len - i));
// count number of chars smaller than str[i]
// from str[i+1] to str[len-1]
rank += count[str[i].charCodeAt(0) - 1] * mul;
// Reduce count of characters greater than str[i]
updatecount(count, str[i]);
}
return rank;
}
// Driver code
let str= "string".split("");
document.write(findRank(str));
// This code is contributed by rag2127
</script>
Producción
598
Los programas anteriores no funcionan para caracteres duplicados. Para que funcionen para caracteres duplicados, encuentre todos los caracteres que son más pequeños (incluya los iguales esta vez también), haga lo mismo que arriba pero, esta vez divida el rango así formado por p! donde p es el conteo de ocurrencias del carácter repetido.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA