Contar formas de seleccionar N pares de caramelos de distintos colores (Programación Dinámica + Máscara de Bits)

Posted on by Rudeus Greyrat

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>
Producción: 

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.
Producción: 

3

 

Complejidad de Tiempo: O(N 2 * 2 N )  
Espacio Auxiliar: O(N * 2 N )

Publicación traducida automáticamente

Artículo escrito por debrc y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *