Dada una permutación P = p 1 , p 2 , …., p n de los primeros n números naturales (1 ≤ n ≤ 10) . Uno puede intercambiar dos elementos consecutivos p i y p i + 1 (1 ≤ i < n) . La tarea es encontrar el número mínimo de intercambios para cambiar P a otra permutación P’ = p’ 1 , p’ 2 , …., p’ n .
Ejemplos:
Entrada: P = “213”, P’ = “321”
Salida: 2
213 <-> 231 <-> 321
Entrada: P = “1234”, P’ = “4123”
Salida: 3
Enfoque: este problema se puede resolver utilizando el algoritmo de ruta más corta de Dijkstra. Parece que no hay nada relacionado con un gráfico en la declaración. Pero supongamos que una permutación es un vértice, entonces cada intercambio de elementos de una permutación es un borde que conecta este vértice con otro vértice. Por lo tanto, encontrar el número mínimo de intercambios ahora se convierte en un problema simple de BFS/ruta más corta.
Ahora analicemos la complejidad del tiempo. Tenemos n! vértices, cada vértice tiene n – 1 vértices adyacentes. También tenemos que almacenar los vértices visitados estado por mapa porque sus representaciones son difíciles de almacenar mediante arreglos normales. Entonces, la complejidad del tiempo total es O(N log(N!) * N!) . Encontrarse en el medioLa técnica se puede utilizar para hacer que la solución sea más rápida.
La solución Meet In The Middle es similar a la solución de Dijkstra con algunas modificaciones.
- Sea P el vértice inicial y P’ el vértice final.
- Que tanto el comienzo como el final sean raíces. Comenzamos BFS desde ambas raíces, comenzamos y terminamos al mismo tiempo pero usando solo una cola.
- Empuje el inicio y el final en la parte posterior de la cola, inicio visitado = final visitado = verdadero .
- Sea src u la raíz del vértice u en progresión BFS. Entonces, src start = start y src finish = finish .
- Sea D u la distancia más corta desde el vértice u hasta la raíz de su árbol. Entonces D inicio = D fin = 0 .
- Si bien la cola no está vacía, haga estallar el frente de la cola, que es el vértice u , luego empuje todos los vértices v que son adyacentes a u y aún no han sido visitados (visitado v = falso) en la parte posterior de la cola, luego deje D v = D u + 1 , src v = src u y visitó v = true . Especialmente, si se visitó v y src v ! = src u entonces podemos devolver inmediatamente D u + D v + 1 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to find minimum number of
// swaps to make another permutation
int ShortestPath(int n, string start, string finish)
{
unordered_map<string, bool> visited;
unordered_map<string, int> D;
unordered_map<string, string> src;
visited[start] = visited[finish] = true;
D[start] = D[finish] = 0;
src[start] = start;
src[finish] = finish;
queue<string> q;
q.push(start);
q.push(finish);
while (!q.empty()) {
// Take top vertex of the queue
string u = q.front();
q.pop();
// Generate n - 1 of it's permutations
for (int i = 1; i < n; i++) {
// Generate next permutation
string v = u;
swap(v[i], v[i - 1]);
// If v is not visited
if (!visited[v]) {
// Set it visited
visited[v] = true;
// Make root of u and root of v equal
src[v] = src[u];
// Increment it's distance by 1
D[v] = D[u] + 1;
// Push this vertex into queue
q.push(v);
}
// If it is already visited
// and roots are different
// then answer is found
else if (src[u] != src[v])
return D[u] + D[v] + 1;
}
}
}
// Driver code
int main()
{
string p1 = "1234", p2 = "4123";
int n = p1.length();
cout << ShortestPath(n, p1, p2);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG{
// Function to find minimum number of
// swaps to make another permutation
static int ShortestPath(int n, String start,
String finish)
{
HashMap<String,
Boolean> visited = new HashMap<String,
Boolean>();
HashMap<String,
Integer> D = new HashMap<String,
Integer>();
HashMap<String,
String> src = new HashMap<String,
String>();
visited.put(start, true);
visited.put(finish, true);
D.put(start, 0);
D.put(finish, 0);
src.put(start, start);
src.put(finish, finish);
Queue<String> q = new LinkedList<>();
q.add(start);
q.add(finish);
while (q.size() != 0)
{
// Take top vertex of the queue
String u = (String)q.peek();
q.remove();
// Generate n - 1 of it's permutations
for(int i = 1; i < n; i++)
{
// Generate next permutation
StringBuilder tmp = new StringBuilder(u);
char t = tmp.charAt(i);
tmp.setCharAt(i, tmp.charAt(i - 1));
tmp.setCharAt(i - 1, t);
String v = tmp.toString();
// If v is not visited
if (!visited.getOrDefault(v, false))
{
// Set it visited
visited.put(v, true);
// Make root of u and root of v equal
src.put(v, src.get(u));
// Increment it's distance by 1
D.put(v, D.get(u) + 1);
// Push this vertex into queue
q.add(v);
}
// If it is already visited
// and roots are different
// then answer is found
else if (src.get(u) != src.get(v))
return D.get(u) + D.get(v) + 1;
}
}
return 0;
}
// Driver Code
public static void main(String[] args)
{
String p1 = "1234", p2 = "4123";
int n = p1.length();
System.out.println(ShortestPath(n, p1, p2));
}
}
// This code is contributed by pratham76
Python3
# Python3 implementation of the approach from collections import deque, defaultdict # Function to find minimum number of # swaps to make another permutation def shortestPath(n: int, start: str, finish: str) -> int: visited, D, src = defaultdict(lambda: False), defaultdict( lambda: 0), defaultdict(lambda: '') visited[start] = visited[finish] = True D[start] = D[finish] = 0 src[start], src[finish] = start, finish q = deque() q.append(start) q.append(finish) while q: # Take top vertex of the queue u = q[0] q.popleft() # Generate n - 1 of it's permutations for i in range(n): v = list(u) v[i], v[i - 1] = v[i - 1], v[i] v = ''.join(v) if not visited[v]: # Set it visited visited[v] = True # Make root of u and root of v equal src[v] = src[u] # Increment it's distance by 1 D[v] = D[u] + 1 # Push this vertex into queue q.append(v) # If it is already visited # and roots are different # then answer is found elif u in src and src[u] != src[v]: return D[u] + D[v] + 1 # Driver Code if __name__ == "__main__": p1 = "1234" p2 = "4123" n = len(p1) print(shortestPath(n, p1, p2)) # This code is contributed by # sanjeev2552
C#
// C# implementation of the approach
using System;
using System.Collections;
using System.Text;
using System.Collections.Generic;
class GFG{
// Function to find minimum number of
// swaps to make another permutation
static int ShortestPath(int n, string start,
string finish)
{
Dictionary<string,
bool> visited = new Dictionary<string,
bool>();
Dictionary<string,
int> D = new Dictionary<string,
int>();
Dictionary<string,
string> src = new Dictionary<string,
string>();
visited[start] = true;
visited[finish] = true;
D[start] = 0;
D[finish] = 0;
src[start] = start;
src[finish] = finish;
Queue q = new Queue();
q.Enqueue(start);
q.Enqueue(finish);
while (q.Count != 0)
{
// Take top vertex of the queue
string u = (string)q.Peek();
q.Dequeue();
// Generate n - 1 of it's permutations
for(int i = 1; i < n; i++)
{
// Generate next permutation
StringBuilder tmp = new StringBuilder(u);
char t = tmp[i];
tmp[i] = tmp[i - 1];
tmp[i - 1] = t;
string v = tmp.ToString();
// If v is not visited
if (!visited.GetValueOrDefault(v, false))
{
// Set it visited
visited[v] = true;
// Make root of u and root of v equal
src[v] = src[u];
// Increment it's distance by 1
D[v] = D[u] + 1;
// Push this vertex into queue
q.Enqueue(v);
}
// If it is already visited
// and roots are different
// then answer is found
else if (src[u] != src[v])
return D[u] + D[v] + 1;
}
}
return 0;
}
// Driver Code
public static void Main(string[] args)
{
string p1 = "1234", p2 = "4123";
int n = p1.Length;
Console.Write(ShortestPath(n, p1, p2));
}
}
// This code is contributed by rutvik_56
Producción:
3
Publicación traducida automáticamente
Artículo escrito por pawan_asipu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA