Dada una array , arr[] que consta de N elementos distintos, la tarea es contar las posibles permutaciones de la array dada que se pueden generar y que satisfacen las siguientes propiedades:
- Las dos mitades deben estar ordenadas.
- arr[i] debe ser menor que arr[N / 2 + i]
Nota: N siempre es par y la indexación comienza desde 0 .
Ejemplos:
Entrada: arr[] = {10, 20, 30, 40}
Salida: 2
Explicación:
Las posibles permutaciones de la array dada que satisfacen las condiciones dadas son: {{10, 20, 30, 40}, {10, 30, 20 , 40}}.
Por lo tanto, la salida requerida es 2.Entrada: arr[] = {1, 2}
Salida: 1
Enfoque : siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos cntPerm para almacenar el recuento de permutaciones de la array dada que satisfacen la condición dada.
- Encuentra el valor del coeficiente binomial de 2N C N usando la siguiente fórmula:
= [{N × (N – 1) × …………. × (N – R + 1)} / {(R × (R – 1) × ….. × 1)}]
- Finalmente, calcula el número catalán = 2N C N / (N + 1) e imprímelo como la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to get the value
// of binomial coefficient
int binCoff(int N, int R)
{
// Stores the value of
// binomial coefficient
int res = 1;
if (R > (N - R)) {
// Since C(N, R)
// = C(N, N - R)
R = (N - R);
}
// Calculate the value
// of C(N, R)
for (int i = 0; i < R; i++) {
res *= (N - i);
res /= (i + 1);
}
return res;
}
// Function to get the count of
// permutations of the array
// that satisfy the condition
int cntPermutation(int N)
{
// Stores count of permutations
// of the array that satisfy
// the given condition
int cntPerm;
// Stores the value of C(2N, N)
int C_2N_N = binCoff(2 * N, N);
// Stores the value of
// catalan number
cntPerm = C_2N_N / (N + 1);
// Return answer
return cntPerm;
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 3, 4 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << cntPermutation(N / 2);
return 0;
}
Java
// Java Program to implement
// the above approach
import java.io.*;
class GFG{
// Function to get the value
// of binomial coefficient
static int binCoff(int N,
int R)
{
// Stores the value of
// binomial coefficient
int res = 1;
if (R > (N - R))
{
// Since C(N, R)
// = C(N, N - R)
R = (N - R);
}
// Calculate the value
// of C(N, R)
for (int i = 0; i < R; i++)
{
res *= (N - i);
res /= (i + 1);
}
return res;
}
// Function to get the count of
// permutations of the array
// that satisfy the condition
static int cntPermutation(int N)
{
// Stores count of permutations
// of the array that satisfy
// the given condition
int cntPerm;
// Stores the value of C(2N, N)
int C_2N_N = binCoff(2 * N, N);
// Stores the value of
// catalan number
cntPerm = C_2N_N / (N + 1);
// Return answer
return cntPerm;
}
// Driver Code
public static void main (String[] args)
{
int arr[] = {1, 2, 3, 4};
int N = arr.length;
System.out.println(cntPermutation(N / 2));
}
}
// This code is contributed by sanjoy_62
Python3
# Python3 program to implement # the above approach # Function to get the value # of binomial coefficient def binCoff(N, R): # Stores the value of # binomial coefficient res = 1 if (R > (N - R)): # Since C(N, R) # = C(N, N - R) R = (N - R) # Calculate the value # of C(N, R) for i in range(R): res *= (N - i) res //= (i + 1) return res # Function to get the count of # permutations of the array # that satisfy the condition def cntPermutation(N): # Stores count of permutations # of the array that satisfy # the given condition # Stores the value of C(2N, N) C_2N_N = binCoff(2 * N, N) # Stores the value of # catalan number cntPerm = C_2N_N // (N + 1) # Return answer return cntPerm # Driver Code if __name__ == '__main__': arr = [ 1, 2, 3, 4 ] N = len(arr) print(cntPermutation(N // 2)) # This code is contributed by mohit kumar 29
C#
// C# Program to implement
// the above approach
using System;
class GFG{
// Function to get the value
// of binomial coefficient
static int binCoff(int N,
int R)
{
// Stores the value of
// binomial coefficient
int res = 1;
if (R > (N - R))
{
// Since C(N, R)
// = C(N, N - R)
R = (N - R);
}
// Calculate the value
// of C(N, R)
for (int i = 0; i < R; i++)
{
res *= (N - i);
res /= (i + 1);
}
return res;
}
// Function to get the count of
// permutations of the array
// that satisfy the condition
static int cntPermutation(int N)
{
// Stores count of permutations
// of the array that satisfy
// the given condition
int cntPerm;
// Stores the value of C(2N, N)
int C_2N_N = binCoff(2 * N, N);
// Stores the value of
// catalan number
cntPerm = C_2N_N / (N + 1);
// Return answer
return cntPerm;
}
// Driver Code
public static void Main(String[] args)
{
int []arr = {1, 2, 3, 4};
int N = arr.Length;
Console.WriteLine(cntPermutation(N / 2));
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// javascript Program to implement
// the above approach
// Function to get the value
// of binomial coefficient
function binCoff(N , R) {
// Stores the value of
// binomial coefficient
var res = 1;
if (R > (N - R)) {
// Since C(N, R)
// = C(N, N - R)
R = (N - R);
}
// Calculate the value
// of C(N, R)
for (i = 0; i < R; i++) {
res *= (N - i);
res /= (i + 1);
}
return res;
}
// Function to get the count of
// permutations of the array
// that satisfy the condition
function cntPermutation(N) {
// Stores count of permutations
// of the array that satisfy
// the given condition
var cntPerm;
// Stores the value of C(2N, N)
var C_2N_N = binCoff(2 * N, N);
// Stores the value of
// catalan number
cntPerm = C_2N_N / (N + 1);
// Return answer
return cntPerm;
}
// Driver Code
var arr = [ 1, 2, 3, 4 ];
var N = arr.length;
document.write(cntPermutation(N / 2));
// This code contributed by umadevi9616
</script>
Producción
2
Complejidad de Tiempo : O(N)
Espacio Auxiliar : O(1)
Publicación traducida automáticamente
Artículo escrito por shashanktrivedi02 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA