Dada una array arr[] de N números ( N ≤ 20 ), la tarea es encontrar el número de Trastornos de la array donde se pueden repetir los elementos de la array.
Un trastorno es una permutación de N elementos, de modo que ningún elemento aparece en su posición original. Por ejemplo, un trastorno de {0, 1, 2, 3} es {2, 3, 1, 0}.
Ejemplos:
Entrada: arr[] = {0, 0, 1}
Salida: 0
Explicación: Todas las permutaciones de la array son: {0, 0, 1}, {0, 1, 0} y {1, 0, 0}.
En cada permutación, hay al menos un número que se coloca en la misma posición que en la array de entrada.
Por lo tanto la respuesta es 0.Entrada: arr[] = {1, 1, 0, 0}
Salida: 1
Explicación: El único trastorno es {0, 0, 1, 1}Entrada: arr[] = {1, 2, 2, 3, 3}
Salida: 4
Explicación: Los desarreglos son {2, 3, 3, 1, 2}, {2, 3, 3, 2, 1}, { 3, 3, 1, 2, 2} y {3, 1, 3, 2, 2}
Enfoque ingenuo: el enfoque más simple para resolver este problema es generar todas las permutaciones posibles y, para cada permutación, verificar si todos los elementos no están colocados en su posición original. Si se encuentra que es cierto, entonces incremente el conteo. Finalmente, imprima el conteo.
Complejidad temporal: O(N! * N)
Espacio auxiliar: O(N)
Enfoque eficiente: el enfoque anterior también se puede optimizar utilizando programación dinámica y enmascaramiento de bits , ya que tiene subproblemas superpuestos y una subestructura óptima . La idea para resolver este problema se basa en las siguientes observaciones:
- Para cada índice de Arr[], la idea es elegir un elemento de array no seleccionado de Arr[] y usar una máscara de bits para realizar un seguimiento de los elementos ya seleccionados de Arr[] . El elemento seleccionado tampoco debe ser igual al elemento actual para garantizar el trastorno.
- dp(i, mask) almacena el resultado desde la ‘i-ésima posición hasta el final, con la máscara de bits ‘máscara’ que denota los elementos ya seleccionados de la array Arr[] hasta la ‘i-1’-ésima posición.
- Dado que la posición actual se puede determinar mediante el recuento de bits establecidos de máscara, reduzca dp (i, máscara) a dp (máscara).
- Entonces la transición de un estado a otro estado se puede definir como:
- Para todo j en el rango [0, N – 1] :
- Si el j-ésimo bit de máscara no está configurado y si A[i] != A[j] , entonces, dp(i, mask) += dp(i + 1, mask|(1<<j)) .
Siga los pasos a continuación para resolver el problema:
- Defina una array de dp de tamaño (1 << N) e inicialícela con -1 para almacenar todos los estados de dp.
- Defina una función recursiva diga countDerangements(i, mask) para contar el número de derangements
- Caso base, si i es igual a N , entonces se ha construido un trastorno válido.
- Si dp[máscara] no es igual a -1, es decir, ya se ha visitado, devuelva dp[máscara].
- Iterar sobre el rango [0, N-1] usando la variable j y en cada iteración, si el j-ésimo bit en la máscara no está configurado y si A[i] != A[j] , entonces,
- Actualice dp[mask] como dp[mask] = dp[mask] + countDerangements (i+1, mask | (<< j)) .
- Finalmente, devuelve dp[máscara].
- Si cualquier número se repite más de una vez, entonces la respuesta devuelta debe dividirse por la frecuencia de ese número porque el mismo número intercambiado en diferentes posiciones dará como resultado el mismo trastorno.
- Por lo tanto, verifique la frecuencia de todos los números y divida la respuesta por la frecuencia de un número si es mayor que 1.
- Esta será la respuesta final.
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;
// Declaring a dp array
long long dp[1 << 20];
// Function to return
// the factorial of a number
long long factorial(int n)
{
long long fact = 1;
for (int i = 2; i <= n; ++i) {
fact *= i;
}
return fact;
}
// Function to count the
// Number of derangements
long long countDerangements(int i, int mask,
int n, int A[])
{
// If all the numbers are placed,
// then return 1.
if (mask == (1 << n) - 1) {
return 1;
}
// If the state has already been computed,
// then return it
if (dp[mask] != -1) {
return dp[mask];
}
dp[mask] = 0;
// Check for all possible numbers
// that can be placed in
// the current position 'i'.
for (int j = 0; j < n; ++j) {
// If the current element arr[j]
// Is not yet selected
//(bit 'j' is unset in mask),
// And if arr[i]!= arr[j]
//(to ensure derangement).
if (!(mask & (1 << j))
and (A[i] != A[j])) {
// Set the bit 'j' in mask and
// Call the function
// For index 'i + 1'.
dp[mask] += countDerangements(
i + 1, mask | (1 << j), n, A);
}
}
// Return dp[mask]
return dp[mask];
}
// Utility Function to count
// The number of derangements
long long UtilCountDerangements(int A[],
int N)
{
// Initializing the dp array with -1.
memset(dp, -1, sizeof dp);
// HashMap to store the frequency
// of each number.
map<int, int> frequencyMap;
for (int i = 0; i < N; ++i) {
++frequencyMap[A[i]];
}
// Function call and storing
// The return value in 'ans'.
long long ans
= countDerangements(0, 0, N, A);
// Iterating through the HashMap
for (auto itr : frequencyMap) {
// Frequency of current number
int times = itr.second;
// If it occurs more than 1 time,
// divide the answer by its frequency.
if (times > 1) {
ans /= factorial(times);
}
}
return ans;
}
// Driver code
int main()
{
// Input array
int arr[] = { 1, 2, 2, 3, 3 };
// Size of array
int N = sizeof(arr) / sizeof(arr[0]);
cout << UtilCountDerangements(arr, N);
return 0;
}
Java
// Java program to implement the approach
import java.util.*;
public class Main
{
// Declaring a dp array
static int[] dp = new int[1 << 20];
// Function to return
// the factorial of a number
static int factorial(int n)
{
int fact = 1;
for (int i = 2; i <= n; ++i) {
fact *= i;
}
return fact;
}
// Function to count the
// Number of derangements
static int countDerangements(int i, int mask,
int n, int[] A)
{
// If all the numbers are placed,
// then return 1.
if (mask == (1 << n) - 1) {
return 1;
}
// If the state has already been computed,
// then return it
if (dp[mask] != -1) {
return dp[mask];
}
dp[mask] = 0;
// Check for all possible numbers
// that can be placed in
// the current position 'i'.
for (int j = 0; j < n; ++j) {
// If the current element arr[j]
// Is not yet selected
//(bit 'j' is unset in mask),
// And if arr[i]!= arr[j]
//(to ensure derangement).
if ((mask & (1 << j)) == 0
&& (A[i] != A[j])) {
// Set the bit 'j' in mask and
// Call the function
// For index 'i + 1'.
dp[mask] += countDerangements(
i + 1, mask | (1 << j), n, A);
}
}
// Return dp[mask]
return dp[mask];
}
// Utility Function to count
// The number of derangements
static int UtilCountDerangements(int[] A,
int N)
{
// Initializing the dp array with -1.
for(int i = 0;i<(1 << 20); i++)
{
dp[i]=-1;
}
// HashMap to store the frequency
// of each number.
HashMap<Integer,
Integer> frequencyMap = new HashMap<Integer,
Integer>();
for (int i = 0; i < N; i++) {
// Counting freq of each element
if(frequencyMap.containsKey(A[i])){
frequencyMap.put(A[i], frequencyMap.get(A[i])+1);
}else{
frequencyMap.put(A[i], 1);
}
}
// Function call and storing
// The return value in 'ans'.
int ans
= countDerangements(0, 0, N, A);
// Iterating through the HashMap
for (Map.Entry<Integer,Integer> itr : frequencyMap.entrySet())
{
// Frequency of current number
int times = itr.getValue();
// If it occurs more than 1 time,
// divide the answer by its frequency.
if (times > 1) {
ans /= factorial(times);
}
}
return ans;
}
// Driver code
public static void main(String[] args)
{
// Input array
int[] arr = { 1, 2, 2, 3, 3 };
// Size of array
int N = arr.length;
System.out.println( UtilCountDerangements(arr, N));
}
}
// This code is contributed by code_hunt.
Python3
# Python program for the above approach
# Declaring a dp array
dp = [-1]*(1 << 20)
# Function to return
# the factorial of a number
def factorial(n):
fact = 1
for i in range(2,n+1):
fact *= i
return fact
# Function to count the
# Number of derangements
def countDerangements(i,mask,n, A):
# If all the numbers are placed,
# then return 1.
if (mask == (1 << n) - 1):
return 1
# If the state has already been computed,
# then return it
if (dp[mask] != -1):
return dp[mask]
dp[mask] = 0
# Check for all possible numbers
# that can be placed in
# the current position 'i'.
for j in range(n):
# If the current element arr[j]
# Is not yet selected
#(bit 'j' is unset in mask),
# And if arr[i]!= arr[j]
#(to ensure derangement).
if (mask & (1 << j) == 0 and (A[i] != A[j])):
# Set the bit 'j' in mask and
# Call the function
# For index 'i + 1'.
dp[mask] += countDerangements(i + 1, mask | (1 << j), n, A)
# Return dp[mask]
return dp[mask]
# Utility Function to count
# The number of derangements
def UtilCountDerangements(A,N):
# HashMap to store the frequency
# of each number.
frequencyMap = {}
for i in range(N):
if A[i] in frequencyMap:
frequencyMap[A[i]] = frequencyMap[A[i]]+1
else:
frequencyMap[A[i]] = 1
# Function call and storing
# The return value in 'ans'.
ans = countDerangements(0, 0, N, A)
# Iterating through the HashMap
for key,value in frequencyMap.items():
# Frequency of current number
times = value
# If it occurs more than 1 time,
# divide the answer by its frequency.
if (times > 1):
ans = ans // factorial(times)
return ans
# Driver code
# Input array
arr = [ 1, 2, 2, 3, 3 ]
# Size of array
N = len(arr)
print(UtilCountDerangements(arr, N))
# This code is contributed by shinjanpatra.
C#
// C# program of the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Declaring a dp array
static int[] dp = new int[1 << 20];
// Function to return
// the factorial of a number
static int factorial(int n)
{
int fact = 1;
for (int i = 2; i <= n; ++i) {
fact *= i;
}
return fact;
}
// Function to count the
// Number of derangements
static int countDerangements(int i, int mask,
int n, int[] A)
{
// If all the numbers are placed,
// then return 1.
if (mask == (1 << n) - 1) {
return 1;
}
// If the state has already been computed,
// then return it
if (dp[mask] != -1) {
return dp[mask];
}
dp[mask] = 0;
// Check for all possible numbers
// that can be placed in
// the current position 'i'.
for (int j = 0; j < n; ++j) {
// If the current element arr[j]
// Is not yet selected
//(bit 'j' is unset in mask),
// And if arr[i]!= arr[j]
//(to ensure derangement).
if ((mask & (1 << j)) == 0
&& (A[i] != A[j])) {
// Set the bit 'j' in mask and
// Call the function
// For index 'i + 1'.
dp[mask] += countDerangements(
i + 1, mask | (1 << j), n, A);
}
}
// Return dp[mask]
return dp[mask];
}
// Utility Function to count
// The number of derangements
static int UtilCountDerangements(int[] A,
int N)
{
// Initializing the dp array with -1.
for(int i = 0;i<(1 << 20); i++)
{
dp[i]=-1;
}
// HashMap to store the frequency
// of each number.
Dictionary<int,int> frequencyMap = new Dictionary<int,int>();
for (int i = 0; i < N; i++) {
if(frequencyMap.ContainsKey(A[i])){
frequencyMap[A[i]] = frequencyMap[A[i]] + 1;
}else{
frequencyMap.Add(A[i], 1);
}
}
// Function call and storing
// The return value in 'ans'.
int ans
= countDerangements(0, 0, N, A);
// Iterating through the HashMap
foreach (KeyValuePair<int,int> itr in frequencyMap)
{
// Frequency of current number
int times = itr.Value;
// If it occurs more than 1 time,
// divide the answer by its frequency.
if (times > 1) {
ans /= factorial(times);
}
}
return ans;
}
// Driver Code
public static void Main()
{
// Input array
int[] arr = { 1, 2, 2, 3, 3 };
// Size of array
int N = arr.Length;
Console.Write( UtilCountDerangements(arr, N));
}
}
// This code is contributed by sanjoy_62.
Javascript
<script>
// JavaScript code for the above approach
// Declaring a dp array
let dp = new Array(1 << 20).fill(-1);
// Function to return
// the factorial of a number
function factorial(n) {
let fact = 1;
for (let i = 2; i <= n; ++i) {
fact *= i;
}
return fact;
}
// Function to count the
// Number of derangements
function countDerangements(i, mask,
n, A)
{
// If all the numbers are placed,
// then return 1.
if (mask == (1 << n) - 1) {
return 1;
}
// If the state has already been computed,
// then return it
if (dp[mask] != -1) {
return dp[mask];
}
dp[mask] = 0;
// Check for all possible numbers
// that can be placed in
// the current position 'i'.
for (let j = 0; j < n; ++j) {
// If the current element arr[j]
// Is not yet selected
//(bit 'j' is unset in mask),
// And if arr[i]!= arr[j]
//(to ensure derangement).
if (!(mask & (1 << j))
&& (A[i] != A[j])) {
// Set the bit 'j' in mask and
// Call the function
// For index 'i + 1'.
dp[mask] += countDerangements(
i + 1, mask | (1 << j), n, A);
}
}
// Return dp[mask]
return dp[mask];
}
// Utility Function to count
// The number of derangements
function UtilCountDerangements(A, N) {
// Initializing the dp array with -1
// HashMap to store the frequency
// of each number.
let frequencyMap = new Map();
for (let i = 0; i < N; ++i) {
if (frequencyMap.has(A[i])) {
frequencyMap.set(A[i], frequencyMap.get(A[i]) + 1)
}
else {
frequencyMap.set(A[i], 1)
}
}
// Function call and storing
// The return value in 'ans'.
let ans
= countDerangements(0, 0, N, A);
// Iterating through the HashMap
for (let [key, val] of frequencyMap) {
// Frequency of current number
let times = val;
// If it occurs more than 1 time,
// divide the answer by its frequency.
if (times > 1) {
ans /= factorial(times);
}
}
return ans;
}
// Driver code
// Input array
let arr = [1, 2, 2, 3, 3];
// Size of array
let N = arr.length;
document.write(UtilCountDerangements(arr, N));
// This code is contributed by Potta Lokesh
</script>
Producción
4
Complejidad de Tiempo: O(N * 2 N )
Espacio Auxiliar: O(2 N )
Publicación traducida automáticamente
Artículo escrito por shreyasshetty788 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA