Nos dan una string que tiene solo letras en minúsculas. La tarea es averiguar el número total de permutaciones distintas que esa string puede generar.
Ejemplos:
C++
// C++ program to find number of distinct
// permutations of a string.
#include<bits/stdc++.h>
using namespace std;
const int MAX_CHAR = 26;
// Utility function to find factorial of n.
int factorial(int n)
{
int fact = 1;
for (int i = 2; i <= n; i++)
fact = fact * i;
return fact;
}
// Returns count of distinct permutations
// of str.
int countDistinctPermutations(string str)
{
int length = str.length();
int freq[MAX_CHAR];
memset(freq, 0, sizeof(freq));
// finding frequency of all the lower case
// alphabet and storing them in array of
// integer
for (int i = 0; i < length; i++)
if (str[i] >= 'a')
freq[str[i] - 'a']++;
// finding factorial of number of appearances
// and multiplying them since they are
// repeating alphabets
int fact = 1;
for (int i = 0; i < MAX_CHAR; i++)
fact = fact * factorial(freq[i]);
// finding factorial of size of string and
// dividing it by factorial found after
// multiplying
return factorial(length) / fact;
}
// Driver code
int main()
{
string str = "fvvfhvgv";
printf("%d", countDistinctPermutations(str));
return 0;
}
Java
// Java program to find number of distinct
// permutations of a string.
public class GFG {
static final int MAX_CHAR = 26;
// Utility function to find factorial of n.
static int factorial(int n)
{
int fact = 1;
for (int i = 2; i <= n; i++)
fact = fact * i;
return fact;
}
// Returns count of distinct permutations
// of str.
static int countDistinctPermutations(String str)
{
int length = str.length();
int[] freq = new int[MAX_CHAR];
// finding frequency of all the lower case
// alphabet and storing them in array of
// integer
for (int i = 0; i < length; i++)
if (str.charAt(i) >= 'a')
freq[str.charAt(i) - 'a']++;
// finding factorial of number of appearances
// and multiplying them since they are
// repeating alphabets
int fact = 1;
for (int i = 0; i < MAX_CHAR; i++)
fact = fact * factorial(freq[i]);
// finding factorial of size of string and
// dividing it by factorial found after
// multiplying
return factorial(length) / fact;
}
// Driver code
public static void main(String args[])
{
String str = "fvvfhvgv";
System.out.println(countDistinctPermutations(str));
}
}
// This code is contributed by Sumit Ghosh
Python3
# Python program to find number of distinct # permutations of a string. MAX_CHAR = 26 # Utility function to find factorial of n. def factorial(n) : fact = 1; for i in range(2, n + 1) : fact = fact * i; return fact # Returns count of distinct permutations # of str. def countDistinctPermutations(st) : length = len(st) freq = [0] * MAX_CHAR # finding frequency of all the lower # case alphabet and storing them in # array of integer for i in range(0, length) : if (st[i] >= 'a') : freq[(ord)(st[i]) - 97] = freq[(ord)(st[i]) - 97] + 1; # finding factorial of number of # appearances and multiplying them # since they are repeating alphabets fact = 1 for i in range(0, MAX_CHAR) : fact = fact * factorial(freq[i]) # finding factorial of size of string # and dividing it by factorial found # after multiplying return factorial(length) // fact # Driver code st = "fvvfhvgv" print (countDistinctPermutations(st)) # This code is contributed by Nikita Tiwari.
C#
// C# program to find number of distinct
// permutations of a string.
using System;
public class GFG {
static int MAX_CHAR = 26;
// Utility function to find factorial of n.
static int factorial(int n)
{
int fact = 1;
for (int i = 2; i <= n; i++)
fact = fact * i;
return fact;
}
// Returns count of distinct permutations
// of str.
static int countDistinctPermutations(String str)
{
int length = str.Length;
int[] freq = new int[MAX_CHAR];
// finding frequency of all the lower case
// alphabet and storing them in array of
// integer
for (int i = 0; i < length; i++)
if (str[i] >= 'a')
freq[str[i] - 'a']++;
// finding factorial of number of appearances
// and multiplying them since they are
// repeating alphabets
int fact = 1;
for (int i = 0; i < MAX_CHAR; i++)
fact = fact * factorial(freq[i]);
// finding factorial of size of string and
// dividing it by factorial found after
// multiplying
return factorial(length) / fact;
}
// Driver code
public static void Main(String []args)
{
String str = "fvvfhvgv";
Console.Write(countDistinctPermutations(str));
}
}
// This code is contributed by parashar.
Javascript
<script>
// Javascript program to find number of distinct
// permutations of a string.
let MAX_CHAR = 26;
// Utility function to find factorial of n.
function factorial(n)
{
let fact = 1;
for (let i = 2; i <= n; i++)
fact = fact * i;
return fact;
}
// Returns count of distinct permutations
// of str.
function countDistinctPermutations(str)
{
let length = str.length;
let freq = new Array(MAX_CHAR);
freq.fill(0);
// finding frequency of all the lower case
// alphabet and storing them in array of
// integer
for (let i = 0; i < length; i++)
if (str[i].charCodeAt() >= 'a'.charCodeAt())
freq[str[i].charCodeAt() - 'a'.charCodeAt()]++;
// finding factorial of number of appearances
// and multiplying them since they are
// repeating alphabets
let fact = 1;
for (let i = 0; i < MAX_CHAR; i++)
fact = fact * factorial(freq[i]);
// finding factorial of size of string and
// dividing it by factorial found after
// multiplying
return parseInt(factorial(length) / fact, 10);
}
let str = "fvvfhvgv";
document.write(countDistinctPermutations(str));
// This code is contributed by vaibhavrabadiya117.
</script>
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