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

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

## 本文概述

ñ

ķ

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

ķ

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

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

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++;
}

// 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)空间。

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

## 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``````

``````// 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)空间。