Dada una array p[] de tamaño N que representa una permutación de los primeros N números naturales , donde N es un número par , la tarea es ordenar la array tomando un par de índices a, b e intercambiar p[a] y p[ b] en cada operación, donde 2 * |a – b| ≥ norte . Imprime los pares de índices intercambiados en cada operación.
Ejemplos:
Entrada: p[] = {2, 5, 3, 1, 4, 6}
Salida: 3
1 5
2 5
1 4
Explicación:
Operación 1: Intercambiar p[1] y p[5]. Por lo tanto, p[] se modifica a {4, 5, 3, 1, 2, 6}.
Operación 2: Intercambiar p[2] y p[5]. Por lo tanto, p[] se modifica a {4, 2, 3, 1, 5, 6}.
Operación 3: Intercambiar p[1] y p[4]. Por lo tanto, p[] se modifica a {1, 2, 3, 4, 5, 6}.
Por lo tanto, la array está ordenada.Entrada: p[] = {1, 2, 3, 4}
Salida: 0
Enfoque: siga los pasos a continuación para resolver el problema:
- Cree una array , posOfCurrNum[] que almacene la posición de los números presentes en p[] .
- Iterar en el rango [1, N] usando la variable i y establecer posOfCurrNum[p[i]] en i .
- Declare un vector de par ans para almacenar los intercambios que se realizarán para ordenar la array dada p[] .
- Iterar en el rango [1, N] usando la variable i
- Si p[i] es igual a i , eso significa que el número actual i ya está presente en la posición correcta. Por lo tanto, continúe con la siguiente iteración.
- Inicialice una variable j con posOfCurrNum[i] para almacenar la posición actual del número i .
- Ahora, se plantean 4 casos:
- Caso 1: Si |i – j| * 2 es mayor que n , luego intercambia (i, j) y almacena este par en ans .
- Caso 2: si n/2 es menor o igual que i – 1 , entonces, swap(i, 1) → swap(1, j) → swap(i, 1) y almacena estos pares en ans .
- Caso 3: si n/2 es menor o igual que n – j , entonces, swap(i, n) → swap(j, n) → swap(i, n) y almacena estos pares en ans .
- Caso 4: si n/2 es menor que j -1 y n/2 es menor o igual que n – i , entonces swap(i, n) → swap(n, 1) → swap(1, j) → swap (1, n) → swap(i, n) y almacene estos pares en ans .
- Imprime el tamaño del vector , ans .
- Recorre el vector de pares , ans , e imprime cada par.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to swap integers
// in an operation
void Swap(int x, int y, int p[],
int posOfCurrNum[])
{
swap(posOfCurrNum[p[x]],
posOfCurrNum[p[y]]);
swap(p[x], p[y]);
}
// Function to sort permutation
// using given operations
void sortArray(int p[], int n)
{
// Store the position of the
// array elements
int posOfCurrNum[n + 1];
for (int i = 1; i <= n; i++) {
posOfCurrNum[p[i]] = i;
}
// Store the result
vector<pair<int, int> > ans;
// Traverse the given array, p[]
for (int i = 1; i <= n; i++) {
// If current number is already
// present at the right position
if (p[i] == i) {
continue;
}
// Store the current position of
// the number 'i'
int j = posOfCurrNum[i];
// Case 1: If both the indices
// satisfies the given condition
if (abs(i - j) * 2 >= n) {
Swap(i, j, p, posOfCurrNum);
ans.push_back({ i, j });
}
// Case 2: If the current number
// 'i' is present at right side
// of half of the given array
else if (n / 2 <= i - 1) {
Swap(1, i, p, posOfCurrNum);
ans.push_back({ i, 1 });
Swap(1, j, p, posOfCurrNum);
ans.push_back({ 1, j });
Swap(i, 1, p, posOfCurrNum);
ans.push_back({ i, 1 });
}
// Case 3: If the position of the
// current number 'i' is left side
// of half of the given array
else if (n - j >= n / 2) {
Swap(i, n, p, posOfCurrNum);
ans.push_back({ i, n });
Swap(j, n, p, posOfCurrNum);
ans.push_back({ j, n });
Swap(i, n, p, posOfCurrNum);
ans.push_back({ i, n });
}
// Case 4: For all other cases
else {
Swap(i, n, p, posOfCurrNum);
ans.push_back({ i, n });
Swap(n, 1, p, posOfCurrNum);
ans.push_back({ n, 1 });
Swap(1, j, p, posOfCurrNum);
ans.push_back({ 1, j });
Swap(1, n, p, posOfCurrNum);
ans.push_back({ 1, n });
Swap(i, n, p, posOfCurrNum);
ans.push_back({ i, n });
}
}
// Print the number of operations
cout << ans.size() << '\n';
// Print the steps
for (auto p : ans)
cout << p.first << " "
<< p.second << '\n';
}
// Driver Code
int main()
{
// Given Input
int n = 6;
// Append 0 to consider
// 1-based indexing
int p[] = { 0, 2, 5, 3, 1, 4, 6 };
// Function Call
sortArray(p, n);
return 0;
}
Java
// Java program for the above approach
import java.lang.*;
import java.util.*;
class pair
{
int first, second;
pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
class GFG
{
// Function to swap integers
// in an operation
static void Swap(int x, int y, int p[],
int posOfCurrNum[])
{
int t1 = posOfCurrNum[p[x]];
posOfCurrNum[p[x]] = posOfCurrNum[p[y]];
posOfCurrNum[p[y]] = t1;
int t2 = p[x];
p[x] = p[y];
p[y] = t2;
}
// Function to sort permutation
// using given operations
static void sortArray(int p[], int n)
{
// Store the position of the
// array elements
int[] posOfCurrNum = new int[n + 1];
for (int i = 1; i <= n; i++) {
posOfCurrNum[p[i]] = i;
}
// Store the result
ArrayList<pair > ans=new ArrayList<>();
// Traverse the given array, p[]
for (int i = 1; i <= n; i++) {
// If current number is already
// present at the right position
if (p[i] == i) {
continue;
}
// Store the current position of
// the number 'i'
int j = posOfCurrNum[i];
// Case 1: If both the indices
// satisfies the given condition
if (Math.abs(i - j) * 2 >= n) {
Swap(i, j, p, posOfCurrNum);
ans.add(new pair( i, j ));
}
// Case 2: If the current number
// 'i' is present at right side
// of half of the given array
else if (n / 2 <= i - 1) {
Swap(1, i, p, posOfCurrNum);
ans.add(new pair( i, 1 ));
Swap(1, j, p, posOfCurrNum);
ans.add(new pair( 1, j ));
Swap(i, 1, p, posOfCurrNum);
ans.add(new pair( i, 1 ));
}
// Case 3: If the position of the
// current number 'i' is left side
// of half of the given array
else if (n - j >= n / 2) {
Swap(i, n, p, posOfCurrNum);
ans.add(new pair( i, n ));
Swap(j, n, p, posOfCurrNum);
ans.add(new pair( j, n ));
Swap(i, n, p, posOfCurrNum);
ans.add(new pair( i, n ));
}
// Case 4: For all other cases
else {
Swap(i, n, p, posOfCurrNum);
ans.add(new pair( i, n ));
Swap(n, 1, p, posOfCurrNum);
ans.add(new pair( n, 1 ));
Swap(1, j, p, posOfCurrNum);
ans.add(new pair( 1, j ));
Swap(1, n, p, posOfCurrNum);
ans.add(new pair( 1, n ));
Swap(i, n, p, posOfCurrNum);
ans.add(new pair( i, n ));
}
}
// Print the number of operations
System.out.println(ans.size());
// Print the steps
for (pair pp : ans)
System.out.println(pp.first+" "+pp.second);
}
// Driver code
public static void main(String[] args)
{
// Given Input
int n = 6;
// Append 0 to consider
// 1-based indexing
int p[] = { 0, 2, 5, 3, 1, 4, 6 };
// Function Call
sortArray(p, n);
}
}
// This code is contributed by offbeat
Python3
# Python3 program for the above approach # Function to swap integers # in an operation def Swap(x, y, p, posOfCurrNum): posOfCurrNum[p[x]], posOfCurrNum[p[y]] = posOfCurrNum[p[y]], posOfCurrNum[p[x]] p[x], p[y] = p[y], p[x] return p, posOfCurrNum # Function to sort permutation # using given operations def sortArray(p, n): # Store the position of the # array elements posOfCurrNum = [0] * (n + 1) for i in range(1, n + 1): posOfCurrNum[p[i]] = i # Store the result ans = [] # Traverse the given array, p[] for i in range(1, n + 1): # If current number is already # present at the right position if (p[i] == i): continue # Store the current position of # the number 'i' j = posOfCurrNum[i] # Case 1: If both the indices # satisfies the given condition if (abs(i - j) * 2 >= n): p, posOfCurrNum = Swap(i, j, p, posOfCurrNum) ans.append([i, j]) # Case 2: If the current number # 'i' is present at right side # of half of the given array elif (n // 2 <= i - 1): p, posOfCurrNum = Swap(1, i, p, posOfCurrNum) ans.append([i, 1]) p, posOfCurrNum = Swap(1, j, p, posOfCurrNum) ans.append([1, j]) p, posOfCurrNum = Swap(i, 1, p, posOfCurrNum) ans.append([i, 1]) # Case 3: If the position of the # current number 'i' is left side # of half of the given array elif (n - j >= n // 2): p, posOfCurrNum = Swap(i, n, p, posOfCurrNum) ans.append([i, n]) p, posOfCurrNum = Swap(j, n, p, posOfCurrNum) ans.append([j, n]) p, posOfCurrNum = Swap(i, n, p, posOfCurrNum) ans.append([i, n]) # Case 4: For all other cases else: p, posOfCurrNum = Swap(i, n, p, posOfCurrNum) ans.append([i, n]) p, posOfCurrNum = Swap(n, 1, p, posOfCurrNum) ans.append([n, 1]) p, posOfCurrNum = Swap(1, j, p, posOfCurrNum) ans.append([1, j]) p, posOfCurrNum = Swap(1, n, p, posOfCurrNum) ans.append([1, n]) p, posOfCurrNum = Swap(i, n, p, posOfCurrNum) ans.append([i, n]) # Print the number of operations print(len(ans)) # Print the steps for p in ans: print(p[0], p[1]) # Driver Code if __name__ == '__main__': # Given Input n = 6 # Append 0 to consider # 1-based indexing p = [ 0, 2, 5, 3, 1, 4, 6 ] # Function Call sortArray(p, n) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG {
// Function to swap integers
// in an operation
static void Swap(int x, int y, int[] p,
int[] posOfCurrNum)
{
int t1 = posOfCurrNum[p[x]];
posOfCurrNum[p[x]] = posOfCurrNum[p[y]];
posOfCurrNum[p[y]] = t1;
int t2 = p[x];
p[x] = p[y];
p[y] = t2;
}
// Function to sort permutation
// using given operations
static void sortArray(int[] p, int n)
{
// Store the position of the
// array elements
int[] posOfCurrNum = new int[n + 1];
for (int i = 1; i <= n; i++) {
posOfCurrNum[p[i]] = i;
}
// Store the result
List<Tuple<int,int>> ans = new List<Tuple<int,int>>();
// Traverse the given array, p[]
for (int i = 1; i <= n; i++) {
// If current number is already
// present at the right position
if (p[i] == i) {
continue;
}
// Store the current position of
// the number 'i'
int j = posOfCurrNum[i];
// Case 1: If both the indices
// satisfies the given condition
if (Math.Abs(i - j) * 2 >= n) {
Swap(i, j, p, posOfCurrNum);
ans.Add(new Tuple<int,int>(i, j));
}
// Case 2: If the current number
// 'i' is present at right side
// of half of the given array
else if (n / 2 <= i - 1) {
Swap(1, i, p, posOfCurrNum);
ans.Add(new Tuple<int,int>(i, 1));
Swap(1, j, p, posOfCurrNum);
ans.Add(new Tuple<int,int>(1, j));
Swap(i, 1, p, posOfCurrNum);
ans.Add(new Tuple<int,int>(i, 1));
}
// Case 3: If the position of the
// current number 'i' is left side
// of half of the given array
else if (n - j >= n / 2) {
Swap(i, n, p, posOfCurrNum);
ans.Add(new Tuple<int,int>(i, n));
Swap(j, n, p, posOfCurrNum);
ans.Add(new Tuple<int,int>(j, n));
Swap(i, n, p, posOfCurrNum);
ans.Add(new Tuple<int,int>(i, n));
}
// Case 4: For all other cases
else {
Swap(i, n, p, posOfCurrNum);
ans.Add(new Tuple<int,int>(i, n));
Swap(n, 1, p, posOfCurrNum);
ans.Add(new Tuple<int,int>(n, 1));
Swap(1, j, p, posOfCurrNum);
ans.Add(new Tuple<int,int>(1, 4));
Swap(1, n, p, posOfCurrNum);
ans.Add(new Tuple<int,int>(1, 6));
Swap(i, n, p, posOfCurrNum);
ans.Add(new Tuple<int,int>(i, n));
}
}
// Print the number of operations
Console.WriteLine(ans.Count);
// Print the steps
foreach(Tuple<int,int> pp in ans)
Console.WriteLine(pp.Item1+" "+pp.Item2);
}
// Driver code
static void Main()
{
// Given Input
int n = 6;
// Append 0 to consider
// 1-based indexing
int[] p = { 0, 2, 5, 3, 1, 4, 6 };
// Function Call
sortArray(p, n);
}
}
// This code is contributed by mukesh07.
Javascript
<script>
// Javascript program for the above approach
// Function to swap integers
// in an operation
function Swap(x, y, p, posOfCurrNum)
{
let temp = posOfCurrNum[p[x]];
posOfCurrNum[p[x]] = posOfCurrNum[p[y]];
posOfCurrNum[p[y]] = temp;
temp = p[x];
p[x] = p[y];
p[y] = temp;
}
// Function to sort permutation
// using given operations
function sortArray(p, n)
{
// Store the position of the
// array elements
let posOfCurrNum = new Array(n + 1);
for (let i = 1; i <= n; i++) {
posOfCurrNum[p[i]] = i;
}
// Store the result
let ans = [];
// Traverse the given array, p[]
for (let i = 1; i <= n; i++) {
// If current number is already
// present at the right position
if (p[i] == i) {
continue;
}
// Store the current position of
// the number 'i'
let j = posOfCurrNum[i];
// Case 1: If both the indices
// satisfies the given condition
if (Math.abs(i - j) * 2 >= n) {
Swap(i, j, p, posOfCurrNum);
ans.push([ i, j ]);
}
// Case 2: If the current number
// 'i' is present at right side
// of half of the given array
else if (n / 2 <= i - 1) {
Swap(1, i, p, posOfCurrNum);
ans.push([ i, 1 ]);
Swap(1, j, p, posOfCurrNum);
ans.push([ 1, j ]);
Swap(i, 1, p, posOfCurrNum);
ans.push([ i, 1 ]);
}
// Case 3: If the position of the
// current number 'i' is left side
// of half of the given array
else if (n - j >= n / 2) {
Swap(i, n, p, posOfCurrNum);
ans.push([ i, n ]);
Swap(j, n, p, posOfCurrNum);
ans.push([ j, n ]);
Swap(i, n, p, posOfCurrNum);
ans.push([ i, n ]);
}
// Case 4: For all other cases
else {
Swap(i, n, p, posOfCurrNum);
ans.push([ i, n ]);
Swap(n, 1, p, posOfCurrNum);
ans.push([ n, 1 ]);
Swap(1, j, p, posOfCurrNum);
ans.push([ 1, j ]);
Swap(1, n, p, posOfCurrNum);
ans.push([ 1, n ]);
Swap(i, n, p, posOfCurrNum);
ans.push([ i, n ]);
}
}
// Print the number of operations
document.write(ans.length + '<br>');
// Print the steps
for (let p of ans)
document.write(p[0] + " " + p[1] + '<br>');
}
// Driver Code
// Given Input
let n = 6;
// Append 0 to consider
// 1-based indexing
let p = [ 0, 2, 5, 3, 1, 4, 6 ];
// Function Call
sortArray(p, n);
// This code is contributed by gfgking.
</script>
Producción:
9 1 4 2 6 6 1 1 4 1 6 2 6 4 1 1 5 4 1
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por samarpitsmarty y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA