Número mínimo de intercambios adyacentes necesarios para convertir una permutación en otra permutación según una condición dada

Dada una permutación P de tamaño N , con valores de 1 a N . la tarea es encontrar el número mínimo de intercambios adyacentes necesarios de modo que para todo i en el rango [1, N] , P[i] no sea igual a i .
Ejemplos: 
 

Entrada: P = [1, 4, 3, 5, 2] 
Salida: 2 
Explicación: 
Aquí P = [1, 4, 3, 5, 2] en el índice 1, 2, 3, 4, 5. Como podemos ver , P[1] = 1 y P[3] = 3. Por lo tanto, necesitamos deshacernos de este invariante. 
Intercambio 1: Intercambio de índice 1 e índice 2 => [4, 1, 3, 5, 2] 
Intercambio 2: Intercambio de índice 2 e índice 3 => [4, 3, 1, 5, 2] 
La array final no tiene i donde P[i] = i. Por lo tanto, se requiere un mínimo de 2 intercambios.
Entrada: P = [1, 2, 4, 9, 5, 8, 7, 3, 6] 
Salida: 3 
Explicación: 
Intercambiar 1: Intercambiar índice 1 e índice 2 => [2, 1, 4, 9, 5, 8, 7, 3, 6] 
Intercambio 2: Intercambio de índice 5 e índice 6 => [2, 1, 4, 9, 8, 5, 7, 3, 6] 
Intercambio 2: Intercambio de índice 7 e índice 8 => [ 2, 1, 4, 9, 8, 5, 3, 7, 6] 
Por lo tanto, se requiere un mínimo de 3 intercambios. 
 

Enfoque: Consideremos las posiciones donde P[i] = i se denotarán por X y las otras posiciones por O . A continuación se presentan tres observaciones básicas para la pregunta: 
 

• Si los valores en cualquiera de los dos índices adyacentes de la permutación tienen la forma XO , podemos simplemente intercambiar los 2 índices para obtener ‘OO’.
• Si los valores en cualquiera de los dos índices adyacentes de la permutación tienen la forma XX , podemos simplemente intercambiar los 2 índices para obtener ‘OO’.
• Si los valores en cualquiera de los dos índices adyacentes de la permutación tienen la forma OX , es simplemente ‘XO’ o ‘XX’ una vez que el puntero alcanza el índice en X .

A continuación se muestran los pasos: 
 

1. Iterar de 1 a N – 1 y verificar si P[i] = i , entonces simplemente intercambiamos (P[i], P[i + 1]) , de lo contrario, continuamos el proceso para los siguientes pares adyacentes.
2. El Caso de la esquina para la pregunta dada es cuando i = N , si P[i] = i, entonces intercambiamos (P[i], P[i – 1]) .

A continuación se muestra la implementación del enfoque anterior: 
 

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum
// number of swaps
void solve(vector<int>& P, int n)
{
 
    // New array to convert
    // to 1-based indexing
    vector<int> arr;
 
    arr.push_back(0);
 
    for (auto x : P)
        arr.push_back(x);
 
    // Keeps count of swaps
    int cnt = 0;
 
    for (int i = 1; i < n; i++) {
 
        // Check if it is an 'X' position
        if (arr[i] == i) {
            swap(arr[i], arr[i + 1]);
            cnt++;
        }
    }
 
    // Corner Case
    if (arr[n] == n) {
 
        swap(arr[n - 1], arr[n]);
        cnt++;
    }
 
    // Print the minimum swaps
    cout << cnt << endl;
}
 
// Driver Code
signed main()
{
    // Given Number N
    int N = 9;
 
    // Given Permutation of N numbers
    vector<int> P = { 1, 2, 4, 9, 5,
                      8, 7, 3, 6 };
 
    // Function Call
    solve(P, N);
 
    return 0;
}

// Java program for the above approach
import java.io.*;
 
class GFG{
 
// Function to find the minimum
// number of swaps
static void solve(int P[], int n)
{
 
    // New array to convert
    // to 1-based indexing
    int arr[] = new int[n + 1];
 
    arr[0] = 0;
 
    for(int i = 0; i < n; i++)
       arr[i + 1] = P[i];
 
    // Keeps count of swaps
    int cnt = 0;
 
    for(int i = 1; i < n; i++)
    {
        
       // Check if it is an 'X' position
       if (arr[i] == i)
       {
           int t = arr[i + 1];
           arr[i + 1] = arr[i];
           arr[i] = t;
           cnt++;
       }
    }
 
    // Corner Case
    if (arr[n] == n)
    {
         
        // Swap
        int t = arr[n - 1];
        arr[n - 1] = arr[n];
        arr[n] = t;
        cnt++;
    }
 
    // Print the minimum swaps
    System.out.println(cnt);
}
 
// Driver code
public static void main(String[] args)
{
     
    // Given Number N
    int N = 9;
 
    // Given Permutation of N numbers
    int P[] = new int[]{ 1, 2, 4, 9, 5,
                         8, 7, 3, 6 };
 
    // Function Call
    solve(P, N);
}
}
 
// This code is contributed by Pratima Pandey

# Python3 program for the above approach
 
# Function to find the minimum
# number of swaps
def solve(P, n):
 
    # New array to convert
    # to 1-based indexing
    arr = []
 
    arr.append(0)
 
    for x in P:
        arr.append(x)
 
    # Keeps count of swaps
    cnt = 0
 
    for i in range(1, n):
 
        # Check if it is an 'X' position
        if (arr[i] == i):
            arr[i], arr[i + 1] = arr[i + 1], arr[i]
            cnt += 1
 
    # Corner Case
    if (arr[n] == n):
        arr[n - 1], arr[n] = arr[n] , arr[n - 1]
        cnt += 1
 
    # Print the minimum swaps
    print(cnt)
 
# Driver Code
 
# Given number N
N = 9
 
# Given permutation of N numbers
P = [ 1, 2, 4, 9, 5,
      8, 7, 3, 6 ]
 
# Function call
solve(P, N)
 
# This code is contributed by chitranayal

// C# program for the above approach
using System;
 
class GFG{
 
// Function to find the minimum
// number of swaps
static void solve(int []P, int n)
{
     
    // New array to convert
    // to 1-based indexing
    int []arr = new int[n + 1];
 
    arr[0] = 0;
 
    for(int i = 0; i < n; i++)
        arr[i + 1] = P[i];
 
    // Keeps count of swaps
    int cnt = 0;
 
    for(int i = 1; i < n; i++)
    {
         
        // Check if it is an 'X' position
        if (arr[i] == i)
        {
            int t = arr[i + 1];
            arr[i + 1] = arr[i];
            arr[i] = t;
            cnt++;
        }
    }
 
    // Corner Case
    if (arr[n] == n)
    {
         
        // Swap
        int t = arr[n - 1];
        arr[n - 1] = arr[n];
        arr[n] = t;
        cnt++;
    }
 
    // Print the minimum swaps
    Console.WriteLine(cnt);
}
 
// Driver code
public static void Main(String[] args)
{
     
    // Given Number N
    int N = 9;
 
    // Given Permutation of N numbers
    int []P = { 1, 2, 4, 9, 5,
                8, 7, 3, 6 };
 
    // Function Call
    solve(P, N);
}
}
 
// This code is contributed by Princi Singh

<script>
 
// JavaScript program for the above approach
 
// Function to find the minimum
// number of swaps
function solve(P, n)
{
 
    // New array to convert
    // to 1-based indexing
    let arr = Array.from({length: n+1}, (_, i) => 0);
 
    arr[0] = 0;
 
    for(let i = 0; i < n; i++)
       arr[i + 1] = P[i];
 
    // Keeps count of swaps
    let cnt = 0;
 
    for(let i = 1; i < n; i++)
    {
        
       // Check if it is an 'X' position
       if (arr[i] == i)
       {
           let t = arr[i + 1];
           arr[i + 1] = arr[i];
           arr[i] = t;
           cnt++;
       }
    }
 
    // Corner Case
    if (arr[n] == n)
    {
         
        // Swap
        let t = arr[n - 1];
        arr[n - 1] = arr[n];
        arr[n] = t;
        cnt++;
    }
 
    // Print the minimum swaps
    document.write(cnt);
}
 
// Driver Code
 
    // Given Number N
    let N = 9;
 
    // Given Permutation of N numbers
    let P = [ 1, 2, 4, 9, 5,
                         8, 7, 3, 6 ];
 
    // Function Call
    solve(P, N);
 
</script>

3

Complejidad temporal: O(N)  
Espacio auxiliar : O(N)