Dadas dos arrays de tamaño n y m. La tarea es encontrar la cantidad de formas en que podemos fusionar los arreglos dados en un arreglo tal que el orden de los elementos de cada arreglo no cambie.
Ejemplos:
Input : n = 2, m = 2 Output : 6 Let first array of size n = 2 be [1, 2] and second array of size m = 2 be [3, 4]. So, possible merged array of n + m elements can be: [1, 2, 3, 4] [1, 3, 2, 4] [3, 4, 1, 2] [3, 1, 4, 2] [1, 3, 4, 2] [3, 1, 2, 4] Input : n = 4, m = 6 Output : 210
La idea es utilizar el concepto de combinatoria. Supongamos que tenemos dos arreglos A{a1, a2, …., am} y B{b1, b2, …., bn} que tienen m y n elementos respectivamente y ahora tenemos que fusionarlos sin perder su orden.
Después de la fusión, sabemos que el número total de elementos será (m + n) elemento después de la fusión. Entonces, ahora solo necesitamos las formas de elegir m lugares de (m + n) donde colocará el elemento de la array A en su orden real, que es m + n C n .
Después de colocar m elemento de la array A, quedarán n espacios, que pueden ser llenados por los n elementos de la array B en su orden real.
Por lo tanto, el número total de formas de fusionar dos arrays de modo que su orden en la array fusionada sea el mismo es m + n C n
A continuación se muestra la implementación de este enfoque:
C++
// CPP Program to find number of ways
// to merge two array such that their
// order in merged array is same
#include <bits/stdc++.h>
using namespace std;
// function to find the binomial coefficient
int binomialCoeff(int n, int k)
{
int C[k + 1];
memset(C, 0, sizeof(C));
C[0] = 1; // nC0 is 1
for (int i = 1; i <= n; i++) {
// Compute next row of pascal triangle
// using the previous row
for (int j = min(i, k); j > 0; j--)
C[j] = C[j] + C[j - 1];
}
return C[k];
}
// function to find number of ways
// to merge two array such that their
// order in merged array is same
int numOfWays(int n, int m)
{
return binomialCoeff(m + n, m);
}
// Driven Program
int main()
{
int n = 2, m = 2;
cout << numOfWays(n, m) << endl;
return 0;
}
Java
// Java Program to find number of ways
// to merge two array such that their
// order in merged array is same
import java.io.*;
class GFG {
// function to find the binomial
// coefficient
static int binomialCoeff(int n, int k)
{
int C[] = new int[k + 1];
// memset(C, 0, sizeof(C));
C[0] = 1; // nC0 is 1
for (int i = 1; i <= n; i++) {
// Compute next row of pascal
// triangle using the previous
// row
for (int j = Math.min(i, k);
j > 0; j--)
C[j] = C[j] + C[j - 1];
}
return C[k];
}
// function to find number of ways
// to merge two array such that their
// order in merged array is same
static int numOfWays(int n, int m)
{
return binomialCoeff(m + n, m);
}
// Driven Program
public static void main (String[] args)
{
int n = 2, m = 2;
System.out.println(numOfWays(n, m));
}
}
// This code is contributed by anuj_67.
Python3
# Python 3 Program to find number of ways # to merge two array such that their # order in merged array is same # function to find the binomial coefficient def binomialCoeff(n, k): C = [0 for i in range(k + 1)] C[0] = 1 for i in range(1, n + 1, 1): # Compute next row of pascal # triangle using the previous row j = min(i, k) while(j > 0): C[j] = C[j] + C[j - 1] j -= 1 return C[k] # function to find number of ways # to merge two array such that their # order in merged array is same def numOfWays(n, m): return binomialCoeff(m + n, m) # Driver Code if __name__ == '__main__': n = 2 m = 2 print(numOfWays(n, m)) # This code is contributed by # Sahil_shelangia
C#
// C# Program to find number of ways
// to merge two array such that their
// order in merged array is same
using System;
class GFG {
// function to find the binomial
// coefficient
static int binomialCoeff(int n, int k)
{
int []C = new int[k + 1];
// memset(C, 0, sizeof(C));
C[0] = 1; // nC0 is 1
for (int i = 1; i <= n; i++) {
// Compute next row of pascal
// triangle using the previous
// row
for (int j = Math.Min(i, k);
j > 0; j--)
C[j] = C[j] + C[j - 1];
}
return C[k];
}
// function to find number of ways
// to merge two array such that their
// order in merged array is same
static int numOfWays(int n, int m)
{
return binomialCoeff(m + n, m);
}
// Driven Program
public static void Main ()
{
int n = 2, m = 2;
Console.WriteLine(numOfWays(n, m));
}
}
// This code is contributed by anuj_67.
PHP
<?php
// PHP Program to find number of ways
// to merge two array such that their
// order in merged array is same
// function to find the binomial coefficient
function binomialCoeff($n, $k)
{
$C = array($k + 1);
for($i=0; $i < count($C); $i++)
$C[$i] = 0;
$C[0] = 1; // nC0 is 1
for ( $i = 1; $i <= $n; $i++) {
// Compute next row of pascal triangle
// using the previous row
for ( $j = min($i, $k); $j > 0; $j--)
$C[$j] = $C[$j] + $C[$j - 1 ];
}
return $C[$k];
}
// function to find number of ways
// to merge two array such that their
// order in merged array is same
function numOfWays( $n, $m)
{
return binomialCoeff($m + $n, $m);
}
$n = 2; $m = 2;
echo numOfWays($n, $m);
//This code is contributed by Rajput-Ji.
?>
Javascript
<script>
// Javascript Program to find number of ways
// to merge two array such that their
// order in merged array is same
// function to find the binomial
// coefficient
function binomialCoeff(n, k)
{
let C = new Array(k + 1);
C.fill(0);
// memset(C, 0, sizeof(C));
C[0] = 1; // nC0 is 1
for (let i = 1; i <= n; i++) {
// Compute next row of pascal
// triangle using the previous
// row
for (let j = Math.min(i, k); j > 0; j--)
C[j] = C[j] + C[j - 1];
}
return C[k];
}
// function to find number of ways
// to merge two array such that their
// order in merged array is same
function numOfWays(n, m)
{
return binomialCoeff(m + n, m);
}
let n = 2, m = 2;
document.write(numOfWays(n, m));
// This code is contributed by divyeshrabadiya07.
</script>
Producción:
6
Podemos resolver el problema anterior en tiempo lineal usando la implementación en tiempo lineal del coeficiente binomial .