Dadas dos arrays arr1[] y arr2[] con elementos distintos de tamaño N. La tarea es contar el número total de combinaciones posibles después de intercambiar elementos en el mismo índice de ambas arrays de modo que no haya duplicados en ambas arrays después realizando la operación.
Ejemplos:
Entrada: arr1[] = {1, 2, 3, 4}, arr2[] = {2, 1, 4, 3}, N = 4
Salida: 4
Explicación: Las posibles combinaciones de arrays son:
- {1, 2, 3, 4} y {2, 1, 4, 3}
- { 2 , 1 , 3, 4} y { 1 , 2 , 4, 3}
- {1, 2, 4 , 3 } y {2, 1, 3 , 4 }
- { 2 , 1 , 4 , 3 } y { 1 , 2 , 3 , 4 }
Los que están en negrita son elementos intercambiados. Entonces, número total de combinaciones = 4.
Entrada: arr1[] = {3, 6, 5, 2, 1, 4, 7}, arr2[] = {1, 7, 2, 4, 3, 5, 6}, N = 7
Salida: 8
Enfoque: la idea es iterar la array para cada elemento y hacer un intercambio , luego encontrar para el intercambio del elemento actual, cuántos intercambios adicionales se necesitan para que la array esté libre de duplicados . Cuente cada combinación diferente como un grupo (conjunto), es decir, para cada grupo hay dos posibilidades de hacer un intercambio o no hacer un intercambio, por lo que la respuesta será la suma de 2 elevada a la potencia del número de grupos . Siga los pasos a continuación para resolver el problema:
- Cree un mapa desordenado para almacenar elementos de ambas arrays en pares clave-valor
- Tome una variable digamos contar para el conteo de posibles combinaciones y también tome un vector para rastrear los elementos digamos visitados .
- Iterar sobre el mapa y verificar si el elemento no es visitado , cada vez crear un conjunto y ejecutar un bucle hasta que el índice actual no sea igual a i . En cada iteración, inserte el elemento del índice actual del mapa en el conjunto y también actualice el índice actual. Marque todos los elementos como visitados en el conjunto.
- Después de cada iteración, mientras hace grupos (conjunto), multiplique el conteo por 2 ya que hay dos posibilidades para cada grupo de intercambiar o no intercambiar elementos.
- Al final, devuelve la cuenta .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count possible combinations
// of arrays after swapping of elements
// such that there are no duplicates
// in the arrays
int possibleCombinations(int arr1[], int arr2[], int N)
{
// Create an unordered_map
unordered_map<int, int> mp;
// Traverse both the arrays and
// store the elements of arr2[]
// in arr1[] element index in
// the map
for (int i = 0; i < N; i++) {
mp[arr1[i]] = arr2[i];
}
// Take a variable for count of
// possible combinations
int count = 1;
// Vector to keep track of already
// swapped elements
vector<bool> visited(N + 1, 0);
for (int i = 1; i <= N; i++) {
// If the element is not visited
if (!visited[i]) {
// Create a set
set<int> s;
// Variable to store the current index
int curr_index = i;
// Iterate a loop till curr_index
// is equal to i
do {
// Insert the element in the set
// of current index in map
s.insert(mp[curr_index]);
// Assign it to curr_index
curr_index = mp[curr_index];
} while (curr_index != i);
// Iterate over the set and
// mark element as visited
for (auto it : s) {
visited[it] = 1;
}
count *= 2;
}
}
return count;
}
// Driver Code
int main()
{
int arr1[] = { 3, 6, 5, 2, 1, 4, 7 };
int arr2[] = { 1, 7, 2, 4, 3, 5, 6 };
int N = sizeof(arr1) / sizeof(arr1[0]);
cout << possibleCombinations(arr1, arr2, N);
return 0;
}
Java
// Java implementation for the above approach
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
class GFG
{
// Function to count possible combinations
// of arrays after swapping of elements
// such that there are no duplicates
// in the arrays
public static int possibleCombinations(int arr1[], int arr2[], int N)
{
// Create an unordered_map
HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>();
// Traverse both the arrays and
// store the elements of arr2[]
// in arr1[] element index in
// the map
for (int i = 0; i < N; i++) {
mp.put(arr1[i], arr2[i]);
}
// Take a variable for count of
// possible combinations
int count = 1;
// Vector to keep track of already
// swapped elements
int[] visited = new int[N + 1];
Arrays.fill(visited, 0);
for (int i = 1; i <= N; i++) {
// If the element is not visited
if (visited[i] <= 0) {
// Create a set
HashSet<Integer> s = new HashSet<Integer>();
// Variable to store the current index
int curr_index = i;
// Iterate a loop till curr_index
// is equal to i
do {
// Insert the element in the set
// of current index in map
s.add(mp.get(curr_index));
// Assign it to curr_index
curr_index = mp.get(curr_index);
} while (curr_index != i);
// Iterate over the set and
// mark element as visited
for (int it : s) {
visited[it] = 1;
}
count *= 2;
}
}
return count;
}
// Driver Code
public static void main(String args[]) {
int arr1[] = { 3, 6, 5, 2, 1, 4, 7 };
int arr2[] = { 1, 7, 2, 4, 3, 5, 6 };
int N = arr1.length;
System.out.println(possibleCombinations(arr1, arr2, N));
}
}
// This code is contributed by gfgking.
Python3
# Python3 implementation for the above approach
# Function to count possible combinations
# of arrays after swapping of elements
# such that there are no duplicates
# in the arrays
def possibleCombinations(arr1, arr2, N) :
# Create an unordered_map
mp = {};
# Traverse both the arrays and
# store the elements of arr2[]
# in arr1[] element index in
# the map
for i in range(N) :
mp[arr1[i]] = arr2[i];
# Take a variable for count of
# possible combinations
count = 1;
# Vector to keep track of already
# swapped elements
visited = [0]*(N + 1);
for i in range(1 , N + 1) :
# If the element is not visited
if (not visited[i]) :
# Create a set
s = set();
# Variable to store the current index
curr_index = i;
# Iterate a loop till curr_index
# is equal to i
while True :
# Insert the element in the set
# of current index in map
s.add(mp[curr_index]);
# Assign it to curr_index
curr_index = mp[curr_index];
if (curr_index == i) :
break
# Iterate over the set and
# mark element as visited
for it in s :
visited[it] = 1;
count *= 2;
return count;
# Driver Code
if __name__ == "__main__" :
arr1 = [ 3, 6, 5, 2, 1, 4, 7 ];
arr2 = [ 1, 7, 2, 4, 3, 5, 6 ];
N = len(arr1);
print(possibleCombinations(arr1, arr2, N));
# This code is contributed by AnkThon
C#
// C# implementation for the above approach
using System;
using System.Collections.Generic;
class GFG {
// Function to count possible combinations
// of arrays after swapping of elements
// such that there are no duplicates
// in the arrays
public static int
possibleCombinations(int[] arr1, int[] arr2, int N)
{
// Create an unordered_map
Dictionary<int, int> mp
= new Dictionary<int, int>();
// Traverse both the arrays and
// store the elements of arr2[]
// in arr1[] element index in
// the map
for (int i = 0; i < N; i++) {
mp[arr1[i]] = arr2[i];
}
// Take a variable for count of
// possible combinations
int count = 1;
// Vector to keep track of already
// swapped elements
int[] visited = new int[N + 1];
for (int i = 1; i <= N; i++) {
// If the element is not visited
if (visited[i] <= 0) {
// Create a set
HashSet<int> s = new HashSet<int>();
// Variable to store the current index
int curr_index = i;
// Iterate a loop till curr_index
// is equal to i
do {
// Insert the element in the set
// of current index in map
s.Add(mp[curr_index]);
// Assign it to curr_index
curr_index = mp[curr_index];
} while (curr_index != i);
// Iterate over the set and
// mark element as visited
foreach(int it in s) { visited[it] = 1; }
count *= 2;
}
}
return count;
}
// Driver Code
public static void Main(string[] args)
{
int[] arr1 = { 3, 6, 5, 2, 1, 4, 7 };
int[] arr2 = { 1, 7, 2, 4, 3, 5, 6 };
int N = arr1.Length;
Console.WriteLine(
possibleCombinations(arr1, arr2, N));
}
}
// This code is contributed by ukasp.
Javascript
<script>
// Javascript implementation for the above approach
// Function to count possible combinations
// of arrays after swapping of elements
// such that there are no duplicates
// in the arrays
function possibleCombinations(arr1, arr2, N)
{
// Create an unordered_map
var mp = new Map();
// Traverse both the arrays and
// store the elements of arr2[]
// in arr1[] element index in
// the map
for (var i = 0; i < N; i++) {
mp.set(arr1[i], arr2[i]);
}
// Take a variable for count of
// possible combinations
var count = 1;
// Vector to keep track of already
// swapped elements
var visited = Array(N + 1).fill(false);
for (var i = 1; i <= N; i++) {
// If the element is not visited
if (!visited[i]) {
// Create a set
var s = new Set();
// Variable to store the current index
var curr_index = i;
// Iterate a loop till curr_index
// is equal to i
do {
// Insert the element in the set
// of current index in map
s.add(mp.get(curr_index));
// Assign it to curr_index
curr_index = mp.get(curr_index);
} while (curr_index != i);
// Iterate over the set and
// mark element as visited
for (var it of [...s]) {
visited[it] = true;
}
count *= 2;
}
}
return count;
}
// Driver Code
var arr1 = [3, 6, 5, 2, 1, 4, 7];
var arr2 = [1, 7, 2, 4, 3, 5, 6];
var N = arr1.length;
document.write(possibleCombinations(arr1, arr2, N));
// This code is contributed by rutvik_56.
</script>
Producción
8
Complejidad de Tiempo : O(N 2 )
Espacio Auxiliar : O(N)