Минимальное количество преобразований префикса для сортировки перестановок первых N чисел
Опубликовано: 16 Января, 2022
Даны N чисел, у которых есть перестановка первых N чисел. За одну операцию можно поменять местами любой префикс. Задача состоит в том, чтобы найти минимальное количество таких операций, чтобы числа в массиве располагались в порядке возрастания.
Примеры:
Ввод : a [] = {3, 1, 2} Выход : 2 Шаг 1. Инвертируйте весь массив a, a [] = {2, 1, 3} Шаг 2. Поменяйте местами префикс (0–1) в s, a [] = {1, 2, 3} Ввод : a [] = {1, 2, 4, 3} Выход : 3 Шаг 1. Инвертируйте весь массив a, a [] = {3, 4, 2, 1} Шаг 2. Поменяйте местами префикс (0–1) в s, a [] = {4, 3, 2, 1} Шаг 3. Инвертируйте весь массив a, a [] = {1, 2, 3, 4}
Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.
Подход к решению этой проблемы заключается в использовании BFS.
- Закодируйте заданные числа в строку. Отсортируйте массив и закодируйте его в строку назначения .
- Затем сделайте BFS из начальной перестановки. Каждый раз проверяйте все перестановки, вызванные изменением префикса текущей перестановки.
- Если он не посещен, поставить его в очередь с подсчетом выполненных обращений.
- Когда перестановка закодированной строки совпадает с перестановкой целевой строки, верните количество поворотов, необходимых для достижения здесь.
- То есть все перестановки строк выполняются, и в качестве ответа возвращается минимальная из них.
Below is the implementation of the above approach:
C++
// C++ program to find // minimum number of prefix reversals // to sort permutation of first N numbers #include <bits/stdc++.h> using namespace std; // Function to return the minimum prefix reversals int minimumPrefixReversals( int a[], int n) { string start = "" ; string destination = "" , t, r; for ( int i = 0; i < n; i++) { // converts the number to a character // and add to string start += to_string(a[i]); } sort(a, a + n); for ( int i = 0; i < n; i++) { destination += to_string(a[i]); } // Queue to store the pairs // of string and number of reversals queue<pair<string, int > > qu; pair<string, int > p; // Initially push the original string qu.push(make_pair(start, 0)); // if original string is the destination string if (start == destination) { return 0; } // iterate till queue is empty while (!qu.empty()) { // pair at the top p = qu.front(); // string t = p.first; // pop the top-most element qu.pop(); // peform prefix reversals for all index and push // in the queue and check for the minimal for ( int j = 2; j <= n; j++) { r = t; // reverse the string till prefix j reverse(r.begin(), r.begin() + j); // if after reversing the string from first i index // it is the destination if (r == destination) { return p.second + 1; } // push the number of reversals for string r qu.push(make_pair(r, p.second + 1)); } } } // Driver Code int main() { int a[] = { 1, 2, 4, 3 }; int n = sizeof (a) / sizeof (a[0]); // Calling function cout << minimumPrefixReversals(a, n); return 0; } |
Java
// Java program to find minimum // number of prefix reversals to // sort permutation of first N numbers import java.util.*; public class Main { // function to find minimum prefix reversal through BFS public static int minimumPrefixReversals( int [] a) { // size of array int n = a.length; // string for initial and goal nodes String start = "" , destination = "" ; // string for manipulation in while loop String original = "" ,modified = "" ; // node to store temporary values from front of queue Node temp = null ; // create the starting string for ( int i = 0 ; i < n; i++) start += a[i]; // sort the array and prepare final destination string Arrays.sort(a); for ( int i = 0 ; i < n; i++) destination += a[i]; // this queue will store all the BFS siblings Queue<Node> q = new LinkedList<>(); // place the starting node in queue q.add( new Node(start, 0 )); //base case:- if array is already sorted if (start == destination) return 0 ; // loop until the size of queue is empty while (q.size() != 0 ) { // put front node of queue in temporary variable temp = q.poll(); // store the original string at this step original = temp.string; for ( int j = 2 ; j <= n; j++) { // modified will be used to genrate all // manipulation of original string // like if original = 1342 // modified = 3142 , 4312 , 2431 modified = original; // generate the permutation by reversing modified = reverse (modified , j); if (modified.equals(destination)) { // if string match then return // the height of the current node return temp.steps + 1 ; } // else put this node into queue q.add( new Node(modified,temp.steps + 1 )); } } // if no case match then default value return Integer.MIN_VALUE; } // function to reverse the string upto an index public static String reverse (String s , int index) { char temp []= s.toCharArray(); int i = 0 ; while (i < index) { char c = temp[i]; temp[i] = temp[index- 1 ]; temp[index- 1 ] = c; i++;index--; } return String.valueOf(temp); } // Driver code public static void main(String []args) { int a[] = new int []{ 1 , 2 , 4 , 3 }; System.out.println(minimumPrefixReversals(a)); } // Node class to store a combined set of values static class Node { public String string ; public int steps; public Node(String string, int steps) { this .string = string; this .steps= steps; } } } // This code is contributed by Sparsh Singhal |
C#
// C# program to find minimum // number of prefix reversals to // sort permutation of first N numbers using System; using System.Collections.Generic; class GFG { // Node class to store a combined set of values public class Node { public String str; public int steps; public Node(String str, int steps) { this .str = str; this .steps= steps; } } // function to find minimum prefix reversal through BFS public static int minimumPrefixReversals( int [] a) { // size of array int n = a.Length; // string for initial and goal nodes String start = "" , destination = "" ; // string for manipulation in while loop String original = "" , modified = "" ; // node to store temporary values // from front of queue Node temp = null ; // create the starting string for ( int i = 0; i < n; i++) start += a[i]; // sort the array and prepare // final destination string Array.Sort(a); for ( int i = 0; i < n; i++) destination += a[i]; // this queue will store all the BFS siblings Queue<Node> q = new Queue<Node>(); // place the starting node in queue q.Enqueue( new Node(start, 0)); //base case:- if array is already sorted if (start == destination) return 0; // loop until the size of queue is empty while (q.Count != 0) { // put front node of queue in temporary variable temp = q.Dequeue(); // store the original string at this step original = temp.str; for ( int j = 2; j <= n; j++) { // modified will be used to generate all // manipulation of original string // like if original = 1342 // modified = 3142 , 4312 , 2431 modified = original; // generate the permutation by reversing modified = reverse (modified , j); if (modified.Equals(destination)) { // if string match then return // the height of the current node return temp.steps + 1; } // else put this node into queue q.Enqueue( new Node(modified, temp.steps + 1)); } } // if no case match then default value return int .MinValue; } // function to reverse the string upto an index public static String reverse (String s, int index) { char []temp = s.ToCharArray(); int i = 0; while (i < index) { char c = temp[i]; temp[i] = temp[index - 1]; temp[index - 1] = c; i++;index--; } return String.Join( "" , temp); } // Driver code public static void Main(String []args) { int []a = new int []{1, 2, 4, 3}; Console.WriteLine(minimumPrefixReversals(a)); } } // This code is contributed by 29AjayKumar |
Output:
3