El menor trastorno de la secuencia

Dada la secuencia 

find the lexicographically smallest (earliest in dictionary order) derangement of 

A derangement of S is as any permutation of S such that no two elements in S and its permutation occur at same position.

Ejemplos:   

Input: 3
Output : 2 3 1
Explanation: The Sequence is 1 2 3.
Possible permutations are (1, 2, 3), (1, 3, 2),
          (2, 1, 3), (2, 3, 1), (3, 1, 2) (3, 2, 1).
Derangements are (2, 3, 1), (3, 1, 2).
Smallest Derangement: (2, 3, 1)

Input : 5
Output : 2 1 4 5 3.
Explanation: Out of all the permutations of 
(1, 2, 3, 4, 5), (2, 1, 4, 5, 3) is the first derangement.

Método 1: 

Podemos modificar el método que se muestra en este artículo: Desorden más grande 
Usando un montón mínimo podemos obtener sucesivamente el elemento mínimo y colocarlo en posiciones más significativas, teniendo cuidado de que se mantenga la propiedad de desajuste. 

Complejidad: O(N * log N)

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

// C++ program to generate smallest derangement
// using priority queue.
#include <bits/stdc++.h>
using namespace std;
 
void generate_derangement(int N)
{
    // Generate Sequence and insert into a
    // priority queue.
    int S[N + 1];
    priority_queue<int, vector<int>, greater<int> > PQ;
    for (int i = 1; i <= N; i++) {
        S[i] = i;
        PQ.push(S[i]);
    }
 
    // Generate Least Derangement
    int D[N + 1];
    for (int i = 1; i <= N; i++) {
        int d = PQ.top();
        PQ.pop();
        if (d != S[i] || i == N) {
            D[i] = d;
        }
        else {
            D[i] = PQ.top();
            PQ.pop();
            PQ.push(d);
        }
    }
 
    if (D[N] == S[N])
       swap(D[N-1], D[N]);
 
    // Print Derangement
    for (int i = 1; i <= N; i++)
        printf("%d ", D[i]);   
    printf("\n");
}
 
// Driver code
int main()
{
    generate_derangement(10);
    return 0;
}

// Java program to generate
// smallest derangement
// using priority queue.
import java.util.*;
class GFG{
 
static void generate_derangement(int N)
{
  // Generate Sequence and insert
  // into a priority queue.
  int []S = new int[N + 1];
   
  PriorityQueue<Integer> PQ =
                new PriorityQueue <>();
   
  for (int i = 1; i <= N; i++)
  {
    S[i] = i;
    PQ.add(S[i]);
  }
 
  // Generate Least Derangement
  int []D = new int[N + 1];
   
  for (int i = 1; i <= N; i++)
  {
    int d = PQ.peek();
    PQ.remove();
    if (d != S[i] || i == N)
    {
      D[i] = d;
    }
    else
    {
      D[i] = PQ.peek();
      PQ.remove();
      PQ.add(d);
    }
  }
 
  if (D[N] == S[N])
  {
    int t = D[N - 1];
    D[N - 1] = D[N];
    D[N] = t;
  }
 
  // Print Derangement
  for (int i = 1; i <= N; i++)
    System.out.printf("%d ", D[i]);   
  System.out.printf("\n");
}
 
// Driver code
public static void main(String[] args)
{
  generate_derangement(10);
}
}
 
// This code is contributed by Amit Katiyar

# Python3 program to generate
# smallest derangement
# using priority queue.
def generate_derangement(N) :
     
    # Generate Sequence and insert
    # into a priority queue.
    S = [i for i in range(N + 1)]   
    PQ = []   
    for i in range(1, N + 1) :      
        PQ.append(S[i])
         
    # Generate Least Derangement
    D = [0] * (N + 1)   
    PQ.sort()  
    for i in range(1, N + 1) :     
        PQ.sort()     
        d = PQ[0]
        del PQ[0]    
        if (d != S[i]) or (i == N) :        
            D[i] = d         
        else :        
            PQ.sort()
            D[i] = PQ[0]
            del PQ[0]
            PQ.append(d)           
    if D[N] == S[N] :       
        t = D[N - 1]
        D[N - 1] = D[N]
        D[N] = t
         
    # Print Derangement
    for i in range(1, N + 1) :
        print(D[i], end = " ")       
    print()
     
generate_derangement(10)
 
# This code is contributed by divyeshrabadiya07

// C# program to generate
// smallest derangement
// using priority queue.
using System;
using System.Collections.Generic;
 
class GFG{
 
static void generate_derangement(int N)
{
   
  // Generate Sequence and insert
  // into a priority queue.
  int []S = new int[N + 1];
   
  List<int> PQ = new List <int>();
   
  for(int i = 1; i <= N; i++)
  {
    S[i] = i;
    PQ.Add(S[i]);
  }
 
  // Generate Least Derangement
  int []D = new int[N + 1];
  PQ.Sort();
  for(int i = 1; i <= N; i++)
  {
    PQ.Sort();
     
    int d = PQ[0];
    PQ.RemoveAt(0);
     
    if (d != S[i] || i == N)
    {
      D[i] = d;
    }
    else
    {
      PQ.Sort();
      D[i] = PQ[0];
      PQ.RemoveAt(0);
      PQ.Add(d);
    }
  }
 
  if (D[N] == S[N])
  {
    int t = D[N - 1];
    D[N - 1] = D[N];
    D[N] = t;
  }
 
  // Print Derangement
  for(int i = 1; i <= N; i++)
    Console.Write(D[i] + " "); 
   
  Console.Write("\n");
}
 
// Driver code
public static void Main(String[] args)
{
  generate_derangement(10);
}
}
 
// This code is contributed by Amit Katiyar

<script>
// Javascript program to generate
// smallest derangement
// using priority queue.
 
function generate_derangement(N)
{
 
    // Generate Sequence and insert
  // into a priority queue.
  let S = new Array(N + 1);
    
  let PQ =[];
    
  for (let i = 1; i <= N; i++)
  {
    S[i] = i;
    PQ.push(S[i]);
  }
  
 PQ.sort(function(a,b){return a-b;});   
  
  // Generate Least Derangement
  let D = new Array(N + 1);
    
  for (let i = 1; i <= N; i++)
  {
    let d = PQ.shift();
     
    if (d != S[i] || i == N)
    {
      D[i] = d;
    }
    else
    {
      D[i] = PQ.shift();
       
      PQ.push(d);
    }
    PQ.sort(function(a,b){return a-b;});
  }
  
  if (D[N] == S[N])
  {
    let t = D[N - 1];
    D[N - 1] = D[N];
    D[N] = t;
  }
  
  // Print Derangement
  for (let i = 1; i <= N; i++)
    document.write( D[i]+" ");  
  document.write("<br>");
}
 
// Driver code
generate_derangement(10);
 
// This code is contributed by avanitrachhadiya2155
</script>

2 1 4 3 6 5 8 7 10 9 

Método 2:

Dado que se nos da una secuencia muy específica, es decir, 

Podemos calcular la respuesta aún más eficientemente.
Divida la secuencia original en pares de dos elementos y luego intercambie los elementos de cada par. 
Si N es impar, entonces el último par debe intercambiarse nuevamente. 

Representación pictórica  

Complejidad: realizamos como máximo intercambios N/2 + 1, por lo que la complejidad es O (N).

¿Por qué funciona este método? 
Este método es una aplicación muy específica del método 1 y se basa en la observación. Dada la naturaleza de la sucesión, en la posición i ya sabemos el mínimo elemento que se puede poner, que es i+1 o i-1. Dado que ya se nos ha dado la permutación mínima de S, está claro que el trastorno debe comenzar desde 2 y no desde 1, es decir, de la forma i+1 (i = 1). El siguiente elemento será de forma i – 1. El elemento después de esto será i + 1 y luego el próximo i – 1. Este patrón continuará hasta el final. 
Esta operación se entiende más fácilmente como el intercambio de elementos adyacentes de pares de elementos de S.
Si podemos determinar el elemento mínimo en tiempo constante, entonces se elimina la sobrecarga de complejidad del montón. Por lo tanto, de O(N * log N) la complejidad se reduce a O(N). 

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

Implementación:

// Efficient C++ program to find smallest
// derangement.
#include <bits/stdc++.h>
 
void generate_derangement(int N)
{       
    // Generate Sequence S
    int S[N + 1];
    for (int i = 1; i <= N; i++)
        S[i] = i;
 
    // Generate Derangement
    int D[N + 1];
    for (int i = 1; i <= N; i += 2) {
        if (i == N && i%N!=0) {
 
            // Only if i is odd
            // Swap D[N-1] and D[N]
            int temp=D[N];
            D[N] = D[N - 1];
            D[N - 1] = temp;
        }
        else {
            D[i] = i + 1;
            D[i + 1] = i;
        }
    }
 
    // Print Derangement
    for (int i = 1; i <= N; i++)
        printf("%d ", D[i]);   
    printf("\n");
}
 
// Driver Program
int main()
{
    generate_derangement(10);
    return 0;
}

// Efficient Java program to find
// smallest derangement.
class GFG
{
     
static void generate_derangement(int N)
{
    // Generate Sequence S
    int S[] = new int[N + 1];
    for (int i = 1; i <= N; i++)
        S[i] = i;
 
    // Generate Derangement
    int D[] = new int[N + 1];
    for (int i = 1; i <= N; i += 2)
    {
        if (i == N)
        {
 
            // Only if i is odd
            // Swap S[N-1] and S[N]
            D[N] = S[N - 1];
            D[N - 1] = S[N];
        }
        else
        {
            D[i] = i + 1;
            D[i + 1] = i;
        }
    }
 
    // Print Derangement
    for (int i = 1; i <= N; i++)
        System.out.print(D[i] + " ");
    System.out.println();
}
 
// Driver Program
public static void main(String[] args)
{
    generate_derangement(10);
}
}
 
// This code is contributed by Arnab Kundu

# Efficient Python3 program to find
# smallest derangement.
 
def generate_derangement(N):
     
    # Generate Sequence S
    S = [0] * (N + 1)
    for i in range(1, N + 1):
        S[i] = i
 
    # Generate Derangement
    D = [0] * (N + 1)
    for i in range(1, N + 1, 2):
        if i == N:
 
            # Only if i is odd
            # Swap S[N-1] and S[N]
            D[N] = S[N - 1]
            D[N - 1] = S[N]
        else:
            D[i] = i + 1
            D[i + 1] = i
 
    # Print Derangement
    for i in range(1, N + 1):
        print(D[i], end = " ")
    print()
 
# Driver Code
if __name__ == '__main__':
    generate_derangement(10)
     
# This code is contributed by PranchalK

// Efficient C# program to find
// smallest derangement.
using System;
 
class GFG
{
     
static void generate_derangement(int N)
{
    // Generate Sequence S
    int[] S = new int[N + 1];
    for (int i = 1; i <= N; i++)
        S[i] = i;
 
    // Generate Derangement
    int[] D = new int[N + 1];
    for (int i = 1; i <= N; i += 2)
    {
        if (i == N)
        {
 
            // Only if i is odd
            // Swap S[N-1] and S[N]
            D[N] = S[N - 1];
            D[N - 1] = S[N];
        }
        else
        {
            D[i] = i + 1;
            D[i + 1] = i;
        }
    }
 
    // Print Derangement
    for (int i = 1; i <= N; i++)
        Console.Write(D[i] + " ");
    Console.WriteLine();
}
 
// Driver Program
public static void Main()
{
    generate_derangement(10);
}
}
 
// This code is contributed
// by Akanksha Rai

<?php
// Efficient PHP program to find smallest
// derangement.
 
function generate_derangement($N)
{    
    // Generate Sequence S
    $S = array();
    for ($i = 1; $i <= $N; $i++)
        $S[$i] = $i;
 
    // Generate Derangement
    $D = array();
    for ($i = 1; $i <= $N; $i += 2)
    {
        if ($i == $N)
        {
 
            // Only if i is odd
            // Swap S[N-1] and S[N]
            $D[$N] = $S[$N - 1];
            $D[$N - 1] = $S[$N];
        }
        else
        {
            $D[$i] = $i + 1;
            $D[$i + 1] = $i;
        }
    }
 
    // Print Derangement
    for ($i = 1; $i <= $N; $i++)
        echo $D[$i] . " ";
    echo "\n";
}
 
// Driver Program
generate_derangement(10);
 
// This code is contributed
// by Akanksha Rai
?>

<script>
 
// Javascript program to find
// smallest derangement.
function generate_derangement(N)
{
 
    // Generate Sequence S
    let S = [];
    for (let i = 1; i <= N; i++)
        S[i] = i;
  
    // Generate Derangement
    let D = [];
    for (let i = 1; i <= N; i += 2)
    {
        if (i == N)
        {
  
            // Only if i is odd
            // Swap S[N-1] and S[N]
            D[N] = S[N - 1];
            D[N - 1] = S[N];
        }
        else
        {
            D[i] = i + 1;
            D[i + 1] = i;
        }
    }
  
    // Print Derangement
    for (let i = 1; i <= N; i++)
        document.write(D[i] + " ");
    document.write("<br/>");
 }
 
     
// Driver code
        generate_derangement(10);
       
      // This code is contributed by code_hunt.
</script>

2 1 4 3 6 5 8 7 10 9 

Nota: El espacio auxiliar se puede reducir a O(1) si realizamos las operaciones de intercambio en S mismo.

Este artículo es una contribución de Sayan Mahapatra . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su 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.