算法设计（求最多k次交换后的最大排列） _算法

本文概述

建议：在继续解决方案之前, 请先在"实践"上解决它。
C ++
Java
python
C#
的PHP

给定第一个的排列
?
自然数作为数组和整数
?
。在最多之后打印按字典顺序排列的最大排列
?
掉期
例子：

Input: arr[] = {4, 5, 2, 1, 3}k = 3Output: 5 4 3 2 1Swap 1st and 2nd elements: 5 4 2 1 3 Swap 3rd and 5th elements: 5 4 3 1 2 Swap 4th and 5th elements: 5 4 3 2 1 Input: arr[] = {2, 1, 3}k = 1Output: 3 1 2Swap 1st and 3re elements: 3 1 2

推荐：请在"实践首先, 在继续解决方案之前。天真的方法:这个想法是按字典顺序递减的顺序生成一个排列。将每个生成的排列与原始数组进行比较, 然后计算转换所需的掉期数量。如果count小于或等于k, 则打印此排列。这种方法的问题在于难以实现, 并且肯定会因N的较大值而超时。
算法：

查找将一个数组转换为另一个数组的最小交换这个文章。
复制原始数组, 然后按降序对该数组排序。因此, 排序后的数组是原始数组的最大排列。
现在按字典顺序降序生成所有排列。先前的排列使用prev_permutation()功能。
如果计数小于或等于k, 则找到将新数组(降序排列)转换为原始数组所需的最小步骤。然后打印数组并中断。

#include < bits/stdc++.h> using namespace std; // Function returns the minimum number // of swaps required to sort the array // This method is taken from below post // https:// www.lsbin.org/ // minimum-number-swaps-required-sort-array/ int minSwapsToSort( int arr[], int n) { // Create an array of pairs where first // element is array element and second // element is position of first element pair< int , int > arrPos[n]; for ( int i = 0; i < n; i++) { arrPos[i].first = arr[i]; arrPos[i].second = i; }// Sort the array by array element // values to get right position of // every element as second // element of pair. sort(arrPos, arrPos + n); // To keep track of visited elements. // Initialize all elements as not // visited or false. vector< bool > vis(n, false ); // Initialize result int ans = 0; // Traverse array elements for ( int i = 0; i < n; i++) { // Already swapped and corrected or // already present at correct pos if (vis[i] || arrPos[i].second == i) continue ; // Find out the number ofnode in // this cycle and add in ans int cycle_size = 0; int j = i; while (!vis[j]) { vis[j] = 1; // move to next node j = arrPos[j].second; cycle_size++; }// Update answer by adding current // cycle. ans += (cycle_size - 1); }// Return result return ans; }// method returns minimum number of // swap to make array B same as array A int minSwapToMakeArraySame( int a[], int b[], int n) { // Map to store position of elements // in array B we basically store // element to index mapping. map< int , int > mp; for ( int i = 0; i < n; i++) mp[b[i]] = i; // now we're storing position of array // A elements in array B. for ( int i = 0; i < n; i++) b[i] = mp[a[i]]; /* We can uncomment this section to print modified b array for (int i = 0; i < N; i++) cout < < b[i] < < " "; cout < < endl; */// Returing minimum swap for sorting // in modified array B as final answer return minSwapsToSort(b, n); }// Function to calculate largest // permutation after atmost K swaps void KswapPermutation( int arr[], int n, int k) { int a[n]; // copy the array for ( int i = 0; i < n; i++) a[i] = arr[i]; // Sort the array in descending order sort(arr, arr + n, greater< int > ()); // generate permutation in lexicographically // decreasing order. do { // copy the array int a1[n], b1[n]; for ( int i = 0; i < n; i++) { a1[i] = arr[i]; b1[i] = a[i]; }// Check if it can be made same in k steps if ( minSwapToMakeArraySame( a1, b1, n) < = k) { // Print the array for ( int i = 0; i < n; i++) cout < < arr[i] < < " " ; break ; }// move to previous permutation } while (prev_permutation(arr, arr + n)); }int main() { int arr[] = { 4, 5, 2, 1, 3 }; int n = sizeof (arr) / sizeof (arr[0]); int k = 3; cout < < "Largest permutation after " < < k < < " swaps:\n" ; KswapPermutation(arr, n, k); return 0; }

输出如下：

Largest permutation after 3 swaps:5 4 3 2 1

复杂度分析：

时间复杂度：上！)。
要生成所有置换O(N！), 需要时间复杂度。
空间复杂度：上)。
需要存储新数组O(n)空间。

高效的方法:这是一种贪婪的方法。当最大元素位于数组的前面时, 即找到最大排列时, 即最大元素按降序排序。最多有k个掉期, 因此将1st, 2nd, 3rd, …, kth在各自位置的最大元素。
注意：如果允许的交换数量等于数组的大小, 则无需遍历整个数组。答案将只是反向排序的数组。
算法：

创建一个HashMap或长度为n的数组, 以存储元素索引对或将元素映射到其索引。
现在运行一个循环k次。
在每次迭代中, 将第ith个元素与元素n – i交换。其中, i是循环的索引或计数。还要交换其位置, 即更新哈希图或数组。因此, 在此步骤中, 将剩余元素中的最大元素交换到最前面。
打印输出数组。

实施1：
这使用简单的数组来得出解决方案。
C ++

// Below is C++ code to print largest // permutation after at most K swaps #include < bits/stdc++.h> using namespace std; // Function to calculate largest // permutation after atmost K swaps void KswapPermutation( int arr[], int n, int k) { // Auxiliary dictionary of // storing the position of elements int pos[n + 1]; for ( int i = 0; i < n; ++i) pos[arr[i]] = i; for ( int i = 0; i < n & & k; ++i) { // If element is already i'th largest, // then no need to swap if (arr[i] == n - i) continue ; // Find position of i'th // largest value, n-i int temp = pos[n - i]; // Swap the elements position pos[arr[i]] = pos[n - i]; pos[n - i] = i; // Swap the ith largest value with the // current value at ith place swap(arr[temp], arr[i]); // decrement number of swaps --k; } }// Driver code int main() { int arr[] = { 4, 5, 2, 1, 3 }; int n = sizeof (arr) / sizeof (arr[0]); int k = 3; KswapPermutation(arr, n, k); cout < < "Largest permutation after " < < k < < " swaps:n" ; for ( int i = 0; i < n; ++i) printf ( "%d " , arr[i]); return 0; }

Java

// Below is Java code to print // largest permutation after // atmost K swaps class GFG {// Function to calculate largest // permutation after atmost K swaps static void KswapPermutation( int arr[], int n, int k) {// Auxiliary dictionary of storing // the position of elements int pos[] = new int [n + 1 ]; for ( int i = 0 ; i < n; ++i) pos[arr[i]] = i; for ( int i = 0 ; i < n & & k > 0 ; ++i) {// If element is already i'th // largest, then no need to swap if (arr[i] == n - i) continue ; // Find position of i'th largest // value, n-i int temp = pos[n - i]; // Swap the elements position pos[arr[i]] = pos[n - i]; pos[n - i] = i; // Swap the ith largest value with the // current value at ith place int tmp1 = arr[temp]; arr[temp] = arr[i]; arr[i] = tmp1; // decrement number of swaps --k; } }// Driver method public static void main(String[] args) {int arr[] = { 4 , 5 , 2 , 1 , 3 }; int n = arr.length; int k = 3 ; KswapPermutation(arr, n, k); System.out.print( "Largest permutation " + "after " + k + " swaps:\n" ); for ( int i = 0 ; i < n; ++i) System.out.print(arr[i] + " " ); } }// This code is contributed by Anant Agarwal.

python

# Python code to print largest permutation after K swapsdef KswapPermutation(arr, n, k):# Auxiliary array of storing the position of elements pos = {} for i in range (n): pos[arr[i]] = ifor i in range (n):# If K is exhausted then break the loop if k = = 0 : break# If element is already largest then no need to swap if (arr[i] = = n - i): continue# Find position of i'th largest value, n-i temp = pos[n - i]# Swap the elements position pos[arr[i]] = pos[n - i] pos[n - i] = i# Swap the ith largest value with the value at # ith place arr[temp], arr[i] = arr[i], arr[temp]# Decrement K after swap k = k - 1# Driver code arr = [ 4 , 5 , 2 , 1 , 3 ] n = len (arr) k = 3 KswapPermutation(arr, N, K)# Print the answer print "Largest permutation after" , K, "swaps: " print " " .join( map ( str , arr))

// Below is C# code to print largest // permutation after atmost K swaps. using System; class GFG {// Function to calculate largest // permutation after atmost K // swaps static void KswapPermutation( int [] arr, int n, int k) {// Auxiliary dictionary of storing // the position of elements int [] pos = new int [n + 1]; for ( int i = 0; i < n; ++i) pos[arr[i]] = i; for ( int i = 0; i < n & & k > 0; ++i) {// If element is already i'th // largest, then no need to swap if (arr[i] == n - i) continue ; // Find position of i'th largest // value, n-i int temp = pos[n - i]; // Swap the elements position pos[arr[i]] = pos[n - i]; pos[n - i] = i; // Swap the ith largest value with // the current value at ith place int tmp1 = arr[temp]; arr[temp] = arr[i]; arr[i] = tmp1; // decrement number of swaps --k; } }// Driver method public static void Main() {int [] arr = { 4, 5, 2, 1, 3 }; int n = arr.Length; int k = 3; KswapPermutation(arr, n, k); Console.Write( "Largest permutation " + "after " + k + " swaps:\n" ); for ( int i = 0; i < n; ++i) Console.Write(arr[i] + " " ); } }// This code is contributed nitin mittal.

的PHP

< ?php // PHP code to print largest permutation // after atmost K swaps// Function to calculate largest // permutation after atmost K swaps function KswapPermutation(& $arr , $n , $k ) {for ( $i = 0; $i < $n ; ++ $i ) $pos [ $arr [ $i ]] = $i ; for ( $i = 0; $i < $n & & $k ; ++ $i ) { // If element is already i'th largest, // then no need to swap if ( $arr [ $i ] == $n - $i ) continue ; // Find position of i'th largest // value, n-i $temp = $pos [ $n - $i ]; // Swap the elements position $pos [ $arr [ $i ]] = $pos [ $n - $i ]; $pos [ $n - $i ] = $i ; // Swap the ith largest value with the // current value at ith place $t = $arr [ $temp ]; $arr [ $temp ] = $arr [ $i ]; $arr [ $i ] = $t ; // decrement number of swaps -- $k ; } }// Driver code $arr = array (4, 5, 2, 1, 3); $n = sizeof( $arr ); $k = 3; KswapPermutation( $arr , $n , $k ); echo ( "Largest permutation after " ); echo ( $k ); echo ( " swaps:\n" ); for ( $i = 0; $i < $n ; ++ $i ) { echo ( $arr [ $i ] ); echo ( " " ); } // This code is contributed // by Shivi_Aggarwal ?>

输出如下：

Largest permutation after 3 swaps:5 4 3 2 1

【算法设计（求最多k次交换后的最大排列）】实施2：这使用哈希图来得出解决方案。

// C++ Program to find the // largest permutation after // at most k swaps using unordered_map. #include < bits/stdc++.h> #include < unordered_map> using namespace std; // Function to find the largest // permutation after k swaps void bestpermutation( int arr[], int k, int n) { // Storing the elements and // their index in map unordered_map< int , int > h; for ( int i = 0; i < n; i++) { h.insert(make_pair(arr[i], i)); }// If number of swaps allowed // are equal to number of elements // then the resulting permutation // will be descending order of // given permutation. if (n < = k) { sort(arr, arr + n, greater< int > ()); } else {for ( int j = n; j > = 1; j--) { if (k > 0) {int initial_index = h[j]; int best_index = n - j; // if j is not at it's best index if (initial_index != best_index) {h[j] = best_index; // Change the index of the element // which was at position 0. Swap // the element basically. int element = arr[best_index]; h[element] = initial_index; swap( arr[best_index], arr[initial_index]); // decrement number of swaps k--; } } } } }// Driver code int main() { int arr[] = { 3, 1, 4, 2, 5 }; // K is the number of swaps int k = 10; // n is the size of the array int n = sizeof (arr) / sizeof ( int ); // Function calling bestpermutation(arr, k, n); cout < < "Largest possible permutation after " < < k < < " swaps is " ; for ( int i = 0; i < n; i++) cout < < arr[i] < < " " ; return 0; } // This method is contributed by Kishan Mishra.

输出如下：