Dada una array arr[] de tamaño N , que representa el número de bolas de cada uno de los N colores distintos, la tarea es encontrar la probabilidad de distribuir todas las bolas en dos cajas, de modo que ambas cajas contengan el mismo número de bolas de colores distintos . pelotas.
Ejemplos:
Entrada: arr[] = {1, 1}, N = 2
Salida: 1.00000
Explicación: Las dos formas posibles de distribuirlas son las siguientes:
Poner la bola del tipo de color 0 en el 1er cuadro y la bola del tipo de color 1 en la 2da caja.
Coloque el color del 1er tipo en la 1ra casilla y el color del 0º tipo en la 2da casilla.
Por lo tanto, la probabilidad es igual a (2/2) = 1.00000Entrada: arr[] = {2, 1, 1}, N = 3
Salida: 0,66667
Enfoque: La idea es usar combinatoria y retroceso para resolver el problema. El problema planteado se puede resolver con base en las siguientes observaciones:
- Supongamos que X es el número total de formas de distribuir K bolas en dos mitades iguales.
- Se puede observar que X es lo mismo que escoger K/2 bolas de entre las K bolas, que es igual a K C (K/2).
- El número total de formas de distribuir las bolas de modo que ambas cajas contengan el mismo número de bolas y el mismo número de colores distintos totales, digamos Y , se puede calcular usando Backtracking , eligiendo j bolas del arr[i] y colocándolo en una casilla por cada 0 ≤ i < N y j ≤ arr[i] , y coloca las bolas restantes en la otra casilla.
- Por lo tanto, la probabilidad requerida es Y/X.
Siga los pasos a continuación para resolver el problema:
- Calcula la suma de todos los elementos presentes en el arreglo arr[] en una variable, digamos K.
- Imprime 0 si K es un número impar.
- Calcule el número de formas de seleccionar K/2 bolas y guárdelo en una variable, digamos X.
- Defina una función recursiva , diga validPermutations(pos, usedBalls, box1, box2) y realice los siguientes pasos:
- Defina el caso base: si usedBalls es igual a K/2 , devuelva 1 si box1 = box2 . De lo contrario, devuelve 0 .
- Si pos ≥ N , devuelve 0 .
- Ahora, inicialice una variable, digamos res , para almacenar el número de formas de distribuir las bolas restantes.
- Iterar sobre el rango [0, arr[pos]]:
- Asigne box1 y box2 a las variables, digamos newbox1 y newbox2 respectivamente.
- Incremente newbox1 en uno si j > 0 y newbox2 , si j < arr[pos] .
- Ahora, actualice res como res = res + arr[pos] C j * validPermutations(pos+1, usedBalls+j, newbox1, newbox2).
- Devuelve el valor de res .
- Llame a la función validPermutations(0, 0, 0, 0) y guárdela en una variable, digamos Y.
- Finalmente, imprima el resultado obtenido como Y/X .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Stores the count of
// distinct colors in box1
static int box1 = 0;
// Stores the count of
// distinct colors in box2
static int box2 = 0;
static int fact[11];
// Function to calculate NcR
long comb(int n, int r)
{
long res = fact[n] / fact[r];
res /= fact[n - r];
return res;
}
// Function to calculate factorial of N
void factorial(int N)
{
// Base Case
fact[0] = 1;
// Iterate over the range [1, N]
for(int i = 1; i <= N; i++)
fact[i] = fact[i - 1] * i;
}
// Function to calculate total number
// of possible distributions which
// satisfies the given conditions
long validPermutations(int n, int balls[],
int usedBalls,
int i, int M)
{
// If used balls is equal to K/2
if (usedBalls == n)
{
// If box1 is equal to box2
return box1 == box2 ? 1 : 0;
}
// Base condition
if (i >= M)
return 0;
// Stores the number of ways of
// distributing remaining balls without
// including the current balls in box1
long res = validPermutations(n, balls,
usedBalls,
i + 1, M);
// Increment box1 by one
box1++;
// Iterate over the range [1, balls[i]]
for(int j = 1; j <= balls[i]; j++)
{
// If all the balls goes to box1,
// then decrease box2 by one
if (j == balls[i])
box2--;
// Total number of ways of
// selecting j balls
long combinations = comb(balls[i], j);
// Increment res by total number of valid
// ways of distributing the remaining balls
res += combinations * validPermutations(n, balls,
usedBalls + j,
i + 1, M);
}
// Decrement box1 by one
box1--;
// Increment box2 by 1
box2++;
return res;
}
// Function to calculate the required probability
double getProbability(int balls[], int M)
{
// Calculate factorial from [1, 10]
factorial(10);
// Assign all distinct balls to second box
box2 = M;
// Total number of balls
int K = 0;
// Calculate total number of balls
for(int i = 0; i < M; i++)
K += balls[i];
// If K is an odd number
if (K % 2 == 1)
return 0;
// Total ways of distributing the balls
// in two equal halves
long all = comb(K, K / 2);
// Required number of ways
long validPermutation = validPermutations(K / 2, balls,
0, 0, M);
// Return the required probability
return (double)validPermutation / all;
}
// Driver Code
int main()
{
int arr[] = { 2, 1, 1 };
int N = 4;
int M = sizeof(arr) / sizeof(arr[0]);
// Print the result
cout << (getProbability(arr, M));
return 0;
}
// This code is contributed by ukasp
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG {
// Stores the count of
// distinct colors in box1
static int box1 = 0;
// Stores the count of
// distinct colors in box2
static int box2 = 0;
static int[] fact = new int[11];
// Function to calculate the required probability
public static double getProbability(int[] balls)
{
// Calculate factorial from [1, 10]
factorial(10);
// Assign all distinct balls to second box
box2 = balls.length;
// Total number of balls
int K = 0;
// Calculate total number of balls
for (int i = 0; i < balls.length; i++)
K += balls[i];
// If K is an odd number
if (K % 2 == 1)
return 0;
// Total ways of distributing the balls
// in two equal halves
long all = comb(K, K / 2);
// Required number of ways
long validPermutations = validPermutations(K / 2, balls, 0, 0);
// Return the required probability
return (double)validPermutations / all;
}
// Function to calculate total number
// of possible distributions which
// satisfies the given conditions
static long validPermutations(int n, int[] balls,
int usedBalls, int i)
{
// If used balls is equal to K/2
if (usedBalls == n) {
// If box1 is equal to box2
return box1 == box2 ? 1 : 0;
}
// Base condition
if (i >= balls.length)
return 0;
// Stores the number of ways of
// distributing remaining balls without
// including the current balls in box1
long res = validPermutations(n, balls, usedBalls, i + 1);
// Increment box1 by one
box1++;
// Iterate over the range [1, balls[i]]
for (int j = 1; j <= balls[i]; j++) {
// If all the balls goes to box1,
// then decrease box2 by one
if (j == balls[i])
box2--;
// Total number of ways of
// selecting j balls
long combinations = comb(balls[i], j);
// Increment res by total number of valid
// ways of distributing the remaining balls
res += combinations * validPermutations(n, balls,
usedBalls + j, i + 1);
}
// Decrement box1 by one
box1--;
// Increment box2 by 1
box2++;
return res;
}
// Function to calculate factorial of N
static void factorial(int N)
{
// Base Case
fact[0] = 1;
// Iterate over the range [1, N]
for (int i = 1; i <= N; i++)
fact[i] = fact[i - 1] * i;
}
// Function to calculate NcR
static long comb(int n, int r)
{
long res = fact[n] / fact[r];
res /= fact[n - r];
return res;
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 2, 1, 1 };
int N = 4;
// Print the result
System.out.println(getProbability(arr));
}
}
Python3
# Python3 program for the above approach # Stores the count of # distinct colors in box1 box1 = 0 # Stores the count of # distinct colors in box2 box2 = 0 fact = [0 for i in range(11)] # Function to calculate the required probability def getProbability(balls): global box1, box2, fact # Calculate factorial from [1, 10] factorial(10) # Assign all distinct balls to second box box2 = len(balls) # Total number of balls K = 0 # Calculate total number of balls for i in range(len(balls)): K += balls[i] # If K is an odd number if (K % 2 == 1): return 0 # Total ways of distributing the balls # in two equal halves all = comb(K, K // 2) # Required number of ways validPermutation = validPermutations( K // 2, balls, 0, 0) # Return the required probability return validPermutation / all # Function to calculate total number # of possible distributions which # satisfies the given conditions def validPermutations(n, balls, usedBalls, i): global box1, box2, fact # If used balls is equal to K/2 if (usedBalls == n): # If box1 is equal to box2 if (box1 == box2): return 1 else: return 0 # Base condition if (i >= len(balls)): return 0 # Stores the number of ways of # distributing remaining balls without # including the current balls in box1 res = validPermutations(n, balls, usedBalls, i + 1) # Increment box1 by one box1 += 1 # Iterate over the range [1, balls[i]] for j in range(1, balls[i] + 1): # If all the balls goes to box1, # then decrease box2 by one if (j == balls[i]): box2 -= 1 # Total number of ways of # selecting j balls combinations = comb(balls[i], j) # Increment res by total number of valid # ways of distributing the remaining balls res += combinations * validPermutations(n, balls, usedBalls + j, i + 1) # Decrement box1 by one box1 -= 1 # Increment box2 by 1 box2 += 1 return res # Function to calculate factorial of N def factorial(N): global box1, box2, fact # Base Case fact[0] = 1 # Iterate over the range [1, N] for i in range(1, N + 1): fact[i] = fact[i - 1] * i # Function to calculate NcR def comb(n, r): global box1, box2, fact res = fact[n] // fact[r] res //= fact[n - r] return res # Driver Code arr = [ 2, 1, 1 ] N = 4 print(getProbability(arr)) # This code is contributed by avanitrachhadiya2155
C#
// C# program for the above approach
using System;
public class GFG
{
// Stores the count of
// distinct colors in box1
static int box1 = 0;
// Stores the count of
// distinct colors in box2
static int box2 = 0;
static int[] fact = new int[11];
// Function to calculate the required probability
public static double getProbability(int[] balls)
{
// Calculate factorial from [1, 10]
factorial(10);
// Assign all distinct balls to second box
box2 = balls.Length;
// Total number of balls
int K = 0;
// Calculate total number of balls
for (int i = 0; i < balls.Length; i++)
K += balls[i];
// If K is an odd number
if (K % 2 == 1)
return 0;
// Total ways of distributing the balls
// in two equal halves
long all = comb(K, K / 2);
// Required number of ways
long validPermutationss = validPermutations((K / 2), balls, 0, 0);
// Return the required probability
return (double)validPermutationss / all;
}
// Function to calculate total number
// of possible distributions which
// satisfies the given conditions
static long validPermutations(int n, int[] balls,
int usedBalls, int i)
{
// If used balls is equal to K/2
if (usedBalls == n)
{
// If box1 is equal to box2
return box1 == box2 ? 1 : 0;
}
// Base condition
if (i >= balls.Length)
return 0;
// Stores the number of ways of
// distributing remaining balls without
// including the current balls in box1
long res = validPermutations(n, balls, usedBalls, i + 1);
// Increment box1 by one
box1++;
// Iterate over the range [1, balls[i]]
for (int j = 1; j <= balls[i]; j++)
{
// If all the balls goes to box1,
// then decrease box2 by one
if (j == balls[i])
box2--;
// Total number of ways of
// selecting j balls
long combinations = comb(balls[i], j);
// Increment res by total number of valid
// ways of distributing the remaining balls
res += combinations * validPermutations(n, balls,
usedBalls + j, i + 1);
}
// Decrement box1 by one
box1--;
// Increment box2 by 1
box2++;
return res;
}
// Function to calculate factorial of N
static void factorial(int N)
{
// Base Case
fact[0] = 1;
// Iterate over the range [1, N]
for (int i = 1; i <= N; i++)
fact[i] = fact[i - 1] * i;
}
// Function to calculate NcR
static long comb(int n, int r)
{
long res = fact[n] / fact[r];
res /= fact[n - r];
return res;
}
// Driver Code
public static void Main(String[] args)
{
int[] arr = { 2, 1, 1 };
int N = 4;
// Print the result
Console.WriteLine(getProbability(arr));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program for the above approach
// Stores the count of
// distinct colors in box1
var box1 = 0;
// Stores the count of
// distinct colors in box2
var box2 = 0;
var fact = Array(11);
// Function to calculate NcR
function comb(n, r)
{
var res = fact[n] / fact[r];
res /= fact[n - r];
return res;
}
// Function to calculate factorial of N
function factorial(N)
{
// Base Case
fact[0] = 1;
// Iterate over the range [1, N]
for(var i = 1; i <= N; i++)
fact[i] = fact[i - 1] * i;
}
// Function to calculate total number
// of possible distributions which
// satisfies the given conditions
function validPermutations(n, balls,usedBalls, i, M)
{
// If used balls is equal to K/2
if (usedBalls == n)
{
// If box1 is equal to box2
return box1 == box2 ? 1 : 0;
}
// Base condition
if (i >= M)
return 0;
// Stores the number of ways of
// distributing remaining balls without
// including the current balls in box1
var res = validPermutations(n, balls,
usedBalls,
i + 1, M);
// Increment box1 by one
box1++;
// Iterate over the range [1, balls[i]]
for(var j = 1; j <= balls[i]; j++)
{
// If all the balls goes to box1,
// then decrease box2 by one
if (j == balls[i])
box2--;
// Total number of ways of
// selecting j balls
var combinations = comb(balls[i], j);
// Increment res by total number of valid
// ways of distributing the remaining balls
res += combinations * validPermutations(n, balls,
usedBalls + j,
i + 1, M);
}
// Decrement box1 by one
box1--;
// Increment box2 by 1
box2++;
return res;
}
// Function to calculate the required probability
function getProbability(balls, M)
{
// Calculate factorial from [1, 10]
factorial(10);
// Assign all distinct balls to second box
box2 = M;
// Total number of balls
var K = 0;
// Calculate total number of balls
for(var i = 0; i < M; i++)
K += balls[i];
// If K is an odd number
if (K % 2 == 1)
return 0;
// Total ways of distributing the balls
// in two equal halves
var all = comb(K, K / 2);
// Required number of ways
var validPermutation = validPermutations(K / 2, balls,
0, 0, M);
// Return the required probability
return validPermutation / all;
}
// Driver Code
var arr = [2, 1, 1];
var N = 4;
var M = arr.length;
// Print the result
document.write(getProbability(arr, M));
</script>
Producción:
0.6666666666666666
Complejidad temporal: O(N!)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por rohit2sahu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA