Dado un número entero N que representa el número de caramelos rojos y azules y una array mat[][] de tamaño N * N , donde mat[i][j] = 1 representa la existencia de un par entre el i – ésimo caramelo rojo y el j -ésimo caramelo azul, la tarea es encontrar el número de formas de seleccionar N pares de caramelos de modo que cada par contenga distintos caramelos de diferentes colores.
Ejemplos:
Entrada: N = 2, mat[][] = { { 1, 1 }, { 1, 1 } }
Salida: 2
Explicación:
Las formas posibles de seleccionar N (= 2) pares de dulces son { { (1, 1) , (2, 2) }, { (1, 2), (2, 1) } }.
Por lo tanto, la salida requerida es 2.Entrada: N = 3, mat[][] = { { 0, 1, 1 }, { 1, 0, 1 }, { 1, 1, 1 } } Salida: 3 Explicación: Formas posibles de seleccionar
N (
=
3 ) los pares de dulces son: { { (1, 2), (2, 1), (3, 3) }, { (1, 2), (2, 3), (3, 1) }, { (1 , 3), (2, 1), (3, 2) } }
Por lo tanto, la salida requerida es 2.
Enfoque ingenuo: el enfoque más simple para resolver este problema es generar todas las permutaciones posibles de N pares que contengan caramelos distintos de diferentes colores. Finalmente, imprima el conteo obtenido.
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++14 program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to count ways to select N distinct // pairs of candies with different colours int numOfWays(vector<vector<int>> a, int n, int i, set<int> &blue) { // If n pairs are selected if (i == n) return 1; // Stores count of ways // to select the i-th pair int count = 0; // Iterate over the range [0, n] for(int j = 0; j < n; j++) { // If pair (i, j) is not included if (a[i][j] == 1 && blue.find(j) == blue.end()) { blue.insert(j); count += numOfWays(a, n, i + 1, blue); blue.erase(j); } } return count; } // Driver Code int main() { int n = 3; vector<vector<int>> mat = { { 0, 1, 1 }, { 1, 0, 1 }, { 1, 1, 1 } }; set<int> mpp; cout << (numOfWays(mat, n, 0, mpp)); } // This code is contributed by mohit kumar 29
Java
// Java program to implement // the above approach import java.io.*; import java.lang.*; import java.util.*; class GFG{ // Function to count ways to select N distinct // pairs of candies with different colours static int numOfWays(int a[][], int n, int i, HashSet<Integer> blue) { // If n pairs are selected if (i == n) return 1; // Stores count of ways // to select the i-th pair int count = 0; // Iterate over the range [0, n] for(int j = 0; j < n; j++) { // If pair (i, j) is not included if (a[i][j] == 1 && !blue.contains(j)) { blue.add(j); count += numOfWays(a, n, i + 1, blue); blue.remove(j); } } return count; } // Driver Code public static void main(String[] args) { int n = 3; int mat[][] = { { 0, 1, 1 }, { 1, 0, 1 }, { 1, 1, 1 } }; HashSet<Integer> mpp = new HashSet<>(); System.out.println((numOfWays(mat, n, 0, mpp))); } } // This code is contributed by Kingash
Python3
# Python3 program to implement # the above approach # Function to count ways to select N distinct # pairs of candies with different colours def numOfWays(a, n, i = 0, blue = []): # If n pairs are selected if i == n: return 1 # Stores count of ways # to select the i-th pair count = 0 # Iterate over the range [0, n] for j in range(n): # If pair (i, j) is not included if mat[i][j] == 1 and j not in blue: count += numOfWays(mat, n, i + 1, blue + [j]) return count # Driver Code if __name__ == "__main__": n = 3 mat = [ [0, 1, 1], [1, 0, 1], [1, 1, 1] ] print(numOfWays(mat, n))
C#
// C# program to implement // the above approach using System; using System.Collections.Generic; class GFG{ // Function to count ways to select N distinct // pairs of candies with different colours static int numOfWays(int[,] a, int n, int i, HashSet<int> blue) { // If n pairs are selected if (i == n) return 1; // Stores count of ways // to select the i-th pair int count = 0; // Iterate over the range [0, n] for(int j = 0; j < n; j++) { // If pair (i, j) is not included if (a[i, j] == 1 && !blue.Contains(j)) { blue.Add(j); count += numOfWays(a, n, i + 1, blue); blue.Remove(j); } } return count; } // Driver Code public static void Main() { int n = 3; int[,] mat = { { 0, 1, 1 }, { 1, 0, 1 }, { 1, 1, 1 } }; HashSet<int> mpp = new HashSet<int>(); Console.WriteLine((numOfWays(mat, n, 0, mpp))); } } // This code is contributed by ukasp
Javascript
<script> // Javascript program to implement // the above approach // Function to count ways to select N distinct // pairs of candies with different colours function numOfWays(a, n, i, blue) { // If n pairs are selected if (i == n) return 1; // Stores count of ways // to select the i-th pair let count = 0; // Iterate over the range [0, n] for(let j = 0; j < n; j++) { // If pair (i, j) is not included if (a[i][j] == 1 && !blue.has(j)) { blue.add(j); count += numOfWays(a, n, i + 1, blue); blue.delete(j); } } return count; } // Driver Code let n = 3; let mat = [ [ 0, 1, 1 ], [ 1, 0, 1 ], [ 1, 1, 1 ] ]; let mpp = new Set(); document.write(numOfWays(mat, n, 0, mpp)); // This code is contributed by _saurabh_jaiswal </script>
3
Complejidad temporal: O(N!)
Espacio auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar para la programación dinámica con enmascaramiento de bits . En lugar de generar todas las permutaciones de N caramelos azules, para cada caramelo rojo, utilice una máscara , donde el j -ésimo bit de máscara comprueba si el j -ésimo caramelo azul está disponible para seleccionar el par actual o no.
La relación de recurrencia para resolver el problema es la siguiente:
Si el K- ésimo bit de máscara no está configurado y mat[i][k] = 1:
dp[i + 1][j | (1 << k)] += dp[i][j]donde, (j | (1 << k)) marca el k-ésimo caramelo azul como seleccionado.
dp[i][j] = Recuento de formas de hacer pares entre i dulces rojos y N dulces azules, donde j es una permutación de N número de bits que va de 0 a 2 N – 1 ) .
Siga los pasos a continuación para resolver el problema:
- Inicialice una array 2D , digamos dp[][] , donde dp[i][j] almacena el recuento de formas de hacer pares entre i caramelos rojos y N caramelos azules. j representa una permutación del número de N bits que va de 0 a 2 N -1 .
- Use la relación de recurrencia anterior y complete todos los estados dp posibles de la relación de recurrencia.
- Finalmente, imprima el estado dp donde hay N dulces rojos y N dulces azules seleccionados, es decir, dp[i][2 n -1] .
A continuación se muestra la implementación del enfoque anterior:
Python3
# Python program to implement # the above approach # Function to count ways to select N distinct # pairs of candies with different colors def numOfWays(a, n): # dp[i][j]: Stores count of ways to make # pairs between i red candies and N blue candies dp = [[0]*((1 << n)+1) for _ in range(n + 1)] # If there is no red and blue candy, # the count of ways to make n pairs is 1 dp[0][0] = 1 # i: Stores count of red candy for i in range(n): # j generates a permutation of blue # candy of selected / not selected # as a binary number with n bits for j in range(1 << n): if dp[i][j] == 0: continue # Iterate over the range [0, n] for k in range(n): # Create a mask with only # the k-th bit as set mask = 1 << k # If Kth bit of mask is # unset and mat[i][k] = 1 if not(mask & j) and a[i][k]: dp[i + 1][j | mask] += dp[i][j] # Return the dp states, where n red # and n blue candies are selected return dp[n][(1 << n)-1] # Driver Code if __name__ == "__main__": n = 3 mat = [[0, 1, 1], [1, 0, 1], [1, 1, 1]] print(numOfWays(mat, n))
C#
// C# program to implement above approach using System; using System.Collections.Generic; class GFG { // Function to count ways to select N distinct // pairs of candies with different colors static int numOfWays(int[][] a,int n){ // dp[i][j]: Stores count of ways to make // pairs between i red candies and N blue candies int[][] dp = new int[n+1][]; for(int i = 0 ; i <= n ; i++){ dp[i] = new int[(1 << n)+1]; } // If there is no red and blue candy, // the count of ways to make n pairs is 1 dp[0][0] = 1; // i: Stores count of red candy for(int i = 0 ; i < n ; i++){ // j generates a permutation of blue // candy of selected / not selected // as a binary number with n bits for(int j = 0 ; j < (1 << n) ; j++){ if (dp[i][j] == 0){ continue; } // Iterate over the range [0, n] for (int k = 0 ; k < n ; k++){ // Create a mask with only // the k-th bit as set int mask = (1 << k); // If Kth bit of mask is // unset and mat[i][k] = 1 if ((mask & j) == 0 && a[i][k] == 1){ dp[i + 1][j | mask] += dp[i][j]; } } } } // Return the dp states, where n red // and n blue candies are selected return dp[n][(1 << n)-1]; } // Driver Code public static void Main(string[] args){ int n = 3; int[][] mat = new int[3][]; mat[0] = new int[]{0, 1, 1}; mat[1] = new int[]{1, 0, 1}; mat[2] = new int[]{1, 1, 1}; Console.Write(numOfWays(mat, n)); } } // This code is contributed by subhamgoyal2014.
3
Complejidad de Tiempo: O(N 2 * 2 N )
Espacio Auxiliar: O(N * 2 N )