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

2021年3月10日16:01:09 发表评论 661 次浏览

本文概述

给定第一个的排列

ñ

自然数作为数组和整数

ķ

。在最多之后打印按字典顺序排列的最大排列

ķ

掉期

例子：

Input: arr[] = {4, 5, 2, 1, 3}
       k = 3
Output: 5 4 3 2 1
Swap 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 = 1
Output: 3 1 2
Swap 1st and 3re elements: 3 1 2

推荐：请在"实践首先, 在继续解决方案之前。

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

算法：

  1. 查找将一个数组转换为另一个数组的最小交换这个文章。
  2. 复制原始数组, 然后按降序对该数组排序。因此, 排序后的数组是原始数组的最大排列。
  3. 现在按字典顺序降序生成所有排列。先前的排列使用prev_permutation()功能。
  4. 如果计数小于或等于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 of  node 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在各自位置的最大元素。

注意：如果允许的交换数量等于数组的大小, 则无需遍历整个数组。答案将只是反向排序的数组。

算法：

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

实施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 swaps
  
def KswapPermutation(arr, n, k):
  
     # Auxiliary array of storing the position of elements
     pos = {}
     for i in range (n):
         pos[arr[i]] = i
  
     for 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))

C#

// 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

实施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.

输出如下：

Largest possible permutation after 3 swaps is 5 4 3 2 1

复杂度分析：

  • 时间复杂度：上)。
    只需要遍历数组一次。
  • 空间复杂度：上)。
    要存储新数组, 需要O(n)空间。

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: