Dada una array arr[] de enteros, la tarea es encontrar el recuento de permutación de la array de modo que la permutación sea en orden creciente, es decir, arr[0] ≤ arr[1] ≤ arr[2] ≤ … ≤ arr[n – 1] .
Ejemplos:
Entrada: arr[] = {1, 2, 1}
Salida: 2
1, 1, 2 y 1, 1, 2 son las únicas permutaciones válidas.
Entrada: arr[] = {5, 4, 4, 5}
Salida: 4
Enfoque: La secuencia debe ser no descendente, es decir , arr[0] ≤ arr[1] ≤ arr[2] ≤ … ≤ arr[n – 1] .
Primero, ordene la array y luego concéntrese en el bloque donde todos los elementos son iguales, ¡ya que estos elementos se pueden reorganizar en P! formas donde P es el tamaño de ese bloque.
Permutar ese bloque no violará la condición dada. Ahora, busque todos los bloques donde todos los elementos sean iguales y multiplique la respuesta de ese bloque individual por la respuesta final para obtener el recuento total de permutaciones posibles.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define N 20
// To store the factorials
int fact[N];
// Function to update fact[] array
// such that fact[i] = i!
void pre()
{
// 0! = 1
fact[0] = 1;
for (int i = 1; i < N; i++) {
// i! = i * (i - 1)!
fact[i] = i * fact[i - 1];
}
}
// Function to return the count
// of possible permutations
int CountPermutation(int a[], int n)
{
// To store the result
int ways = 1;
// Sort the array
sort(a, a + n);
// Initial size of the block
int size = 1;
for (int i = 1; i < n; i++) {
// Increase the size of block
if (a[i] == a[i - 1]) {
size++;
}
else {
// Update the result for
// the previous block
ways *= fact[size];
// Reset the size to 1
size = 1;
}
}
// Update the result for
// the last block
ways *= fact[size];
return ways;
}
// Driver code
int main()
{
int a[] = { 1, 2, 4, 4, 2, 4 };
int n = sizeof(a) / sizeof(a[0]);
// Pre-calculating factorials
pre();
cout << CountPermutation(a, n);
return 0;
}
Java
//Java implementation of the approach
import java.util.Arrays;
import java.io.*;
class GFG
{
static int N = 20;
// To store the factorials
static int []fact=new int[N];
// Function to update fact[] array
// such that fact[i] = i!
static void pre()
{
// 0! = 1
fact[0] = 1;
for (int i = 1; i < N; i++)
{
// i! = i * (i - 1)!
fact[i] = i * fact[i - 1];
}
}
// Function to return the count
// of possible permutations
static int CountPermutation(int a[], int n)
{
// To store the result
int ways = 1;
// Sort the array
Arrays.sort(a);
// Initial size of the block
int size = 1;
for (int i = 1; i < n; i++)
{
// Increase the size of block
if (a[i] == a[i - 1])
{
size++;
}
else
{
// Update the result for
// the previous block
ways *= fact[size];
// Reset the size to 1
size = 1;
}
}
// Update the result for
// the last block
ways *= fact[size];
return ways;
}
// Driver Code
public static void main (String[] args)
{
int a[] = { 1, 2, 4, 4, 2, 4 };
int n = a.length;
// Pre-calculating factorials
pre();
System.out.println (CountPermutation(a, n));
}
}
// This code is contributed by Sachin
Python3
# Python3 implementation of the approach N = 20 # To store the factorials fact = [0] * N; # Function to update fact[] array # such that fact[i] = i! def pre() : # 0! = 1 fact[0] = 1; for i in range(1, N): # i! = i * (i - 1)! fact[i] = i * fact[i - 1]; # Function to return the count # of possible permutations def CountPermutation(a, n): # To store the result ways = 1; # Sort the array a.sort(); # Initial size of the block size = 1; for i in range(1, n): # Increase the size of block if (a[i] == a[i - 1]): size += 1; else : # Update the result for # the previous block ways *= fact[size]; # Reset the size to 1 size = 1; # Update the result for # the last block ways *= fact[size]; return ways; # Driver code if __name__ == "__main__" : a = [ 1, 2, 4, 4, 2, 4 ]; n = len(a); # Pre-calculating factorials pre(); print(CountPermutation(a, n)); # This code is contributed by AnkitRai01
C#
// C# implementation of the approach
using System;
class GFG
{
static int N = 20;
// To store the factorials
static int []fact = new int[N];
// Function to update fact[] array
// such that fact[i] = i!
static void pre()
{
// 0! = 1
fact[0] = 1;
for (int i = 1; i < N; i++)
{
// i! = i * (i - 1)!
fact[i] = i * fact[i - 1];
}
}
// Function to return the count
// of possible permutations
static int CountPermutation(int []a, int n)
{
// To store the result
int ways = 1;
// Sort the array
Array.Sort(a);
// Initial size of the block
int size = 1;
for (int i = 1; i < n; i++)
{
// Increase the size of block
if (a[i] == a[i - 1])
{
size++;
}
else
{
// Update the result for
// the previous block
ways *= fact[size];
// Reset the size to 1
size = 1;
}
}
// Update the result for
// the last block
ways *= fact[size];
return ways;
}
// Driver Code
static public void Main ()
{
int []a = { 1, 2, 4, 4, 2, 4 };
int n = a.Length;
// Pre-calculating factorials
pre();
Console.Write(CountPermutation(a, n));
}
}
// This code is contributed by Sachin.
Javascript
<script>
// Javascript implementation of the approach
const N = 20;
// To store the factorials
let fact = new Array(N);
// Function to update fact[] array
// such that fact[i] = i!
function pre()
{
// 0! = 1
fact[0] = 1;
for (let i = 1; i < N; i++) {
// i! = i * (i - 1)!
fact[i] = i * fact[i - 1];
}
}
// Function to return the count
// of possible permutations
function CountPermutation(a, n)
{
// To store the result
let ways = 1;
// Sort the array
a.sort();
// Initial size of the block
let size = 1;
for (let i = 1; i < n; i++) {
// Increase the size of block
if (a[i] == a[i - 1]) {
size++;
}
else {
// Update the result for
// the previous block
ways *= fact[size];
// Reset the size to 1
size = 1;
}
}
// Update the result for
// the last block
ways *= fact[size];
return ways;
}
// Driver code
let a = [ 1, 2, 4, 4, 2, 4 ];
let n = a.length;
// Pre-calculating factorials
pre();
document.write(CountPermutation(a, n));
</script>
Producción:
12
Complejidad de tiempo: O(N * logN)