Dada una permutación de los primeros n números naturales como array y un entero k . Imprima la permutación lexicográficamente más grande después de un máximo de k intercambios
Ejemplos:
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
Enfoque ingenuo : la idea es generar permutaciones una por una en orden lexicográficamente decreciente. Compare cada permutación generada con la array original y cuente la cantidad de intercambios necesarios para convertir . Si cuenta es menor o igual que k, imprime esta permutación. El problema de este enfoque es que sería difícil de implementar y definitivamente se agotaría por el gran valor de N.
Algoritmo:
- Para encontrar los intercambios mínimos para convertir una array en otra, lea este artículo.
- Copie la array original y ordene esa array en orden decreciente. Entonces, la array ordenada es la permutación más grande de la array original.
- Ahora genere todas las permutaciones en orden lexicográficamente decreciente. La permutación anterior se calcula utilizando la función prev_permutation() .
- Encuentre los pasos mínimos requeridos para convertir la nueva array (permutación en orden decreciente) a la array original, si el conteo es menor o igual a k. Luego imprima la array y rompa.
Implementación:
C++14
#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.geeksforgeeks.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; */
// Returning 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;
}
Producción
Largest permutation after 3 swaps: 5 4 3 2 1
Análisis de Complejidad:
- Complejidad temporal: O(N!).
Para generar todas las permutaciones O(N!) se requiere complejidad de tiempo. - Complejidad espacial: O(n).
para almacenar la nueva array O(n) se requiere espacio.
Otro enfoque que vale la pena considerar:
Este problema se puede considerar como una instancia de una ordenación por selección “controlada”. Por controlado, queremos decir que no estamos realizando la operación de clasificación por selección en toda la array. En su lugar, nos estamos construyendo solo con el número total de intercambios K que podemos realizar.
Entonces, en el siguiente enfoque, todo lo que tenemos que hacer es simplemente dejar que la clasificación por selección continúe por k veces, no más que eso. También debemos verificar si la posición del número máximo que estamos a punto de intercambiar con la posición actual i es igual al número que ya está presente en esa posición, y debemos saltar sobre esta situación particular, no sea que desperdiciemos nuestro limitado número de intercambios.
Implementación:
C++14
#include <bits/stdc++.h>
using namespace std;
void KswapPermutation(
int arr[], int n, int k)
{
for(int i=0;i<n-1;i++)
{
if( k>0)
{
int max = i;
for(int j=i+1;j<n;j++)
if(arr[j]>arr[max])
max = j;
// this condition checks whether the max value has changed since when
// we started , or is it the same.
// We need to ignore the swap if the value is same.
// It means that the number ought to be present at the ith position , is already
// there.
if(max!=i)
{
int temp = arr[max];
arr[max] = arr[i];
arr[i] = temp;
k--;
}
}
else
break;
}
}
// 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:"<<endl;
for (int i = 0; i < n; ++i)
cout<<arr[i]<<" ";
return 0;
}
Python3
def KswapPermutation(arr, n, k):
for i in range(0, n-1):
if(k > 0):
max = i
for j in range(i+1, n):
if(arr[j] > arr[max]):
max = j
# this condition checks whether the max value has changed since when
# we started , or is it the same.
# We need to ignore the swap if the value is same.
# It means that the number ought to be present at the ith position , is already
# there.
if(max != i):
temp = arr[max]
arr[max] = arr[i]
arr[i] = temp
k = k-1
else:
break
# Driver code
arr = [4, 5, 2, 1, 3]
n = len(arr)
k = 3
KswapPermutation(arr, n, k)
print("Largest permutation after "+str(k) + " swaps:")
for i in range(0, n):
print(arr[i], end=' ')
# This code is contributed by Harsh Khatri
Producción
Largest permutation after 3 swaps: 5 4 3 2 1
Análisis de complejidad :
- Complejidad de tiempo: O(n^2), porque este enfoque utiliza ordenación por selección
- Complejidad del espacio : O(1) , porque la clasificación está en su lugar y no se necesita espacio adicional
Enfoque eficiente :
Este es un enfoque codicioso. La permutación más grande se encuentra cuando los elementos más grandes están al frente de la array, es decir, los elementos más grandes se ordenan en orden decreciente. Hay como máximo k intercambios, así que coloque el 1 er , 2 nd , 3 rd , …, kth elemento más grande en su posición respectiva.
Nota: si la cantidad de intercambios permitidos es igual al tamaño de la array, entonces no es necesario iterar sobre toda la array. La respuesta será simplemente la array ordenada inversa.
Algoritmo:
- Cree un HashMap o una array de longitud n para almacenar el par elemento-índice o asignar el elemento a su índice.
- Ahora ejecute un bucle k veces.
- En cada iteración, intercambie el i-ésimo elemento con el elemento n – i. donde i es el índice o conteo del ciclo. También intercambie su posición, es decir, actualice el hashmap o la array. Entonces, en este paso, el elemento más grande en el elemento restante se intercambia al frente.
- Imprima la array de salida.
Implementación 1: utiliza arrays simples para llegar a la solución.
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.
Python3
# 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
?>
Javascript
<script>
// Below is Javascript code to print largest
// permutation after at most K swaps
// Function to calculate largest
// permutation after atmost K swaps
function KswapPermutation(arr, n, k)
{
// Auxiliary dictionary of
// storing the position of elements
let pos = new Array(n + 1);
for (let i = 0; i < n; ++i)
pos[arr[i]] = i;
for (let 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
let 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
let tmp1 = arr[temp];
arr[temp] = arr[i];
arr[i] = tmp1;
// decrement number of swaps
--k;
}
}
let arr = [ 4, 5, 2, 1, 3 ];
let n = arr.length;
let k = 3;
KswapPermutation(arr, n, k);
document.write("Largest permutation after " + k + " swaps:" + "</br>");
for (let i = 0; i < n; ++i)
document.write(arr[i] + " ");
</script>
Producción
Largest permutation after 3 swaps:n5 4 3 2 1
Implementación 2: utiliza un hashmap para llegar a la solución.
C++
// 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.
Java
// Java Program to find the
// largest permutation after
// at most k swaps using unordered_map.
import java.util.*;
class GFG
{
// Function to find the largest
// permutation after k swaps
static void bestpermutation(ArrayList<Integer> arr, int k, int n)
{
// Storing the elements and
// their index in map
HashMap<Integer, Integer> h =
new HashMap<Integer, Integer>();
for (int i = 0; i < n; i++)
{
h.put(arr.get(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) {
Collections.sort(arr, Collections.reverseOrder());
}
else {
for (int j = n; j >= 1; j--)
{
if (k > 0)
{
int initial_index = h.get(j);
int best_index = n - j;
// if j is not at it's best index
if (initial_index != best_index)
{
h.put(j, best_index);
// Change the index of the element
// which was at position 0. Swap
// the element basically.
int element = arr.get(best_index);
h.put(element, initial_index);
int temp = arr.get(best_index);
arr.set(best_index, arr.get(initial_index));
arr.set(initial_index, temp);
// decrement number of swaps
k--;
}
}
}
}
}
// Driver code
public static void main(String []args)
{
ArrayList<Integer> arr = new ArrayList<Integer>();
arr.add(3);
arr.add(1);
arr.add(4);
arr.add(2);
arr.add(5);
// K is the number of swaps
int k = 10;
// n is the size of the array
int n = arr.size();
// Function calling
bestpermutation(arr, k, n);
System.out.print("Largest possible permutation after " + k + " swaps is ");
for (int i = 0; i < n; i++)
System.out.print(arr.get(i) + " ");
}
}
// This code is contributed by rutvik_56.
Python3
# Python3 program to find the
# largest permutation after
# at most k swaps using unordered_map.
# Function to find the largest
# permutation after k swaps
def bestpermutation(arr, k, n):
# Storing the elements and
# their index in map
h = {}
for i in range(n):
h[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):
arr.sort()
arr.reverse()
else:
for j in range(n, 0, -1):
if (k > 0):
initial_index = h[j]
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.
element = arr[best_index]
h[element] = initial_index
arr[best_index], arr[initial_index] = (arr[initial_index],
arr[best_index])
# Decrement number of swaps
k -= 1
# Driver Code
arr = [ 3, 1, 4, 2, 5 ]
# K is the number of swaps
k = 10
# n is the size of the array
n = len(arr)
# Function calling
bestpermutation(arr, k, n)
print("Largest possible permutation after",
k, "swaps is", end = " ")
for i in range(n):
print(arr[i], end = " ")
# This code is contributed by divyesh072019
C#
// C# Program to find the
// largest permutation after
// at most k swaps using unordered_map.
using System;
using System.Collections.Generic;
class GFG {
// Function to find the largest
// permutation after k swaps
static void bestpermutation(List<int> arr, int k, int n)
{
// Storing the elements and
// their index in map
Dictionary<int, int> h =
new Dictionary<int, int>();
for (int i = 0; i < n; i++) {
h.Add(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) {
arr.Sort();
arr.Reverse();
}
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;
int temp = arr[best_index];
arr[best_index] = arr[initial_index];
arr[initial_index] = temp;
// decrement number of swaps
k--;
}
}
}
}
}
static void Main() {
List<int> arr = new List<int>(new int[] {3, 1, 4, 2, 5 });
// K is the number of swaps
int k = 10;
// n is the size of the array
int n = arr.Count;
// Function calling
bestpermutation(arr, k, n);
Console.Write("Largest possible permutation after " + k + " swaps is ");
for (int i = 0; i < n; i++)
Console.Write(arr[i] + " ");
}
}
// This code is contributed by divyeshrabadiya07
Javascript
<script>
// JavaScript Program to find the
// largest permutation after
// at most k swaps using unordered_map.
// Function to find the largest
// permutation after k swaps
function bestpermutation(arr,k,n)
{
// Storing the elements and
// their index in map
let h =
new Map();
for (let i = 0; i < n; i++)
{
h.set(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) {
arr.sort(function(a,b){return b-a;});
}
else {
for (let j = n; j >= 1; j--)
{
if (k > 0)
{
let initial_index = h[j];
let best_index = n - j;
// if j is not at it's best index
if (initial_index != best_index)
{
h.set(j, best_index);
// Change the index of the element
// which was at position 0. Swap
// the element basically.
let element = arr.get(best_index);
h.set(element, initial_index);
let temp = arr[best_index];
arr.set(best_index, arr[initial_index]);
arr.set(initial_index, temp);
// decrement number of swaps
k--;
}
}
}
}
}
// Driver code
let arr=[3,1,4,2,5];
// K is the number of swaps
let k = 10;
// n is the size of the array
let n = arr.length;
// Function calling
bestpermutation(arr, k, n);
document.write(
"Largest possible permutation after " + k + " swaps is "
);
for (let i = 0; i < n; i++)
document.write(arr[i] + " ");
// This code is contributed by avanitrachhadiya2155
</script>
Producción
Largest possible permutation after 10 swaps is 5 4 3 2 1
Análisis de Complejidad:
- Complejidad temporal: O(N).
Solo se requiere un recorrido de la array. - Complejidad espacial: O(n).
Para almacenar la nueva array O(n) se requiere espacio.
Este artículo es una contribución de Shubham Bansal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA