Кратчайший путь с помощью Meet In The Middle

Опубликовано: 5 Января, 2022

Дана перестановка P = p 1 , p 2 ,…., P n первых n натуральных чисел (1 ≤ n ≤ 10) . Можно поменять местами любые два последовательных элемента p i и p i + 1 (1 ≤ i <n) . Задача состоит в том, чтобы найти минимальное количество перестановок, чтобы заменить P на другую перестановку P '= p' 1 , p ' 2 ,…., P' n .

Примеры:

Input: P = “213”, P’ = “321”
Output: 2
213 <-> 231 <-> 321
 

Input: P = “1234”, P’ = “4123”
Output: 3

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход: эту проблему можно решить с помощью алгоритма кратчайшего пути Дейкстры. Кажется, что в заявлении нет ничего, что связано с графиком. Но предположим, что одна перестановка - это одна вершина, тогда каждая перестановка элементов перестановки - это ребро, которое соединяет эту вершину с другой вершиной. Таким образом, поиск минимального количества свопов теперь становится простой проблемой BFS / кратчайшего пути.
Теперь проанализируем временную сложность. У нас есть n! вершин, каждая вершина имеет n - 1 смежную вершину. Мы также должны хранить вершины, посещенные в состоянии по карте, потому что их представления трудно сохранить в обычных массивах. Таким образом, общая временная сложность составляет O (N log (N!) * N!) . Для ускорения решения можно использовать технику Meet In The Middle.
Решение Meet In The Middle похоже на решение Дейкстры с некоторыми изменениями.

  • Пусть P - начальная вершина, а P ' - конечная вершина.
  • Пусть и начало, и конец будут корнями. Мы запускаем BFS из обоих корней, запускаем и заканчиваем одновременно, но используя только одну очередь.
  • Поместите начало и конец в конец очереди, посещенное начало = посещение финиш = истина .
  • Пусть src u - корень вершины u в прогрессии BFS. Итак, src start = start и src finish = finish .
  • Пусть D u - кратчайшее расстояние от вершины u до корня дерева. Итак, D start = D finish = 0 .
  • Пока очередь не пуста, вытолкните переднюю часть очереди, которая является вершиной u, затем вытолкните все вершины v , смежные с u и еще не посещенные (посещенные v = false), в заднюю часть очереди, затем пусть D v = D u + 1 , src v = src u и посетил v = true . В частности, если v был посещен и src v ! = Src u, мы можем немедленно вернуть D u + D v + 1 .

Ниже представлена реализация описанного выше подхода:

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 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, start, string
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
Выход:
 3

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Получите все важные математические концепции для соревновательного программирования с курсом Essential Maths for CP по доступной для студентов цене.

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.