Permutación lexicográficamente más pequeña de {1, .. n} tal que no. y la posición no coinciden

Dado un entero positivo n, encuentre la permutación lexicográficamente más pequeña p de {1, 2, .. n} tal que p i != iie, i no debería estar allí en la i-ésima posición donde i varía de 1 a n. 

Ejemplos:  

Input : 5
Output : 2 1 4 5 3
Consider the two permutations that follow
the requirement that position and numbers
should not be same.
p = (2, 1, 4, 5, 3) and q = (2, 4, 1, 5, 3).  
Since p is lexicographically smaller, our 
output is p.

Input  : 6
Output : 2 1 4 3 6 5
 

Como necesitamos lexicográficamente el más pequeño (y el 1 no puede estar en la posición 1), ponemos el 2 en la primera posición. Después de 2, ponemos el siguiente elemento más pequeño, es decir, 1. Después de eso, el siguiente elemento más pequeño considerando que no viola nuestra condición de pi != i. 
Ahora, si nuestro n es par, simplemente tomamos dos variables, una que contendrá nuestro conteo de números pares y otra que contendrá nuestro conteo de números impares y luego las mantendremos sumando en el vector hasta llegar a n. 

Pero, si nuestro n es impar, hacemos la misma tarea hasta llegar a n-1 porque si sumamos hasta n, al final terminaremos teniendo p i = i. Entonces, cuando lleguemos a n-1, primero agregamos n a la posición n-1 y luego en la posición n pondremos n-2. 

La implementación del programa anterior se muestra a continuación.  

C++

// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to print the permutation
void findPermutation(vector<int> a, int n)
{
    vector<int> res;  
 
    // Initial numbers to be pushed to result
    int en = 2, on = 1;
 
    // If n is even
    if (n % 2 == 0) {
        for (int i = 0; i < n; i++) {
            if (i % 2 == 0) {
                res.push_back(en);
                en += 2;
            } else {
                res.push_back(on);
                on += 2;
            }
        }
    }
 
    // If n is odd
    else {
        for (int i = 0; i < n - 2; i++) {
            if (i % 2 == 0) {
                res.push_back(en);
                en += 2;
            } else {
                res.push_back(on);
                on += 2;
            }
        }
        res.push_back(n);
        res.push_back(n - 2);
    }
 
    // Print result
    for (int i = 0; i < n; i++)
        cout << res[i] << " ";   
    cout << "\n";
}
 
// Driver Code
int main()
{
    long long int n = 9;
    findPermutation(n);
    return 0;
}

Java

// Java implementation of the above approach
import java.util.Vector;
 
class GFG {
 
// Function to print the permutation
    static void findPermutation(int n) {
        Vector<Integer> res = new Vector<Integer>();
 
        // Initial numbers to be pushed to result
        int en = 2, on = 1;
 
        // If n is even
        if (n % 2 == 0) {
            for (int i = 0; i < n; i++) {
                if (i % 2 == 0) {
                    res.add(en);
                    en += 2;
                } else {
                    res.add(on);
                    on += 2;
                }
            }
        } // If n is odd
        else {
            for (int i = 0; i < n - 2; i++) {
                if (i % 2 == 0) {
                    res.add(en);
                    en += 2;
                } else {
                    res.add(on);
                    on += 2;
                }
            }
            res.add(n);
            res.add(n - 2);
        }
 
        // Print result
        for (int i = 0; i < n; i++) {
            System.out.print(res.get(i) + " ");
        }
        System.out.println("");
    }
 
// Driver Code
    public static void main(String[] args) {
        int n = 9;
        findPermutation(n);
    }
}
// This code is contributed by PrinciRaj1992

Python3

# Python3 implementation of the above approach
 
# Function to print the permutation
def findPermutation(n) :
 
    res = []
 
    # Initial numbers to be pushed to result
    en, on = 2, 1
 
    # If n is even
    if (n % 2 == 0) :
        for i in range(n) :
            if (i % 2 == 0) :
                res.append(en)
                en += 2
            else :
                res.append(on)
                on += 2
          
 
    # If n is odd
    else :
        for i in range(n-2) :
            if (i % 2 == 0) :
                res.append(en)
                en += 2
            else :
                res.append(on)
                on += 2
             
          
        res.append(n)
        res.append(n - 2)
      
 
    # Print result
    for i in range(n) :
        print(res[i] ,end = " ")    
    print()
 
 
# Driver Code
if __name__ == "__main__" :
  
    n = 9;
    findPermutation(n)
 
# This code is contributed by Ryuga

C#

// C# implementation of the above approach
using System;
using System.Collections;
public class GFG {
 
// Function to print the permutation
    static void findPermutation(int n) {
        ArrayList res = new ArrayList();
 
        // Initial numbers to be pushed to result
        int en = 2, on = 1;
 
        // If n is even
        if (n % 2 == 0) {
            for (int i = 0; i < n; i++) {
                if (i % 2 == 0) {
                    res.Add(en);
                    en += 2;
                } else {
                    res.Add(on);
                    on += 2;
                }
            }
        } // If n is odd
        else {
            for (int i = 0; i < n - 2; i++) {
                if (i % 2 == 0) {
                    res.Add(en);
                    en += 2;
                } else {
                    res.Add(on);
                    on += 2;
                }
            }
            res.Add(n);
            res.Add(n - 2);
        }
 
        // Print result
        for (int i = 0; i < n; i++) {
            Console.Write(res[i] + " ");
        }
        Console.WriteLine("");
    }
 
// Driver Code
    public static void Main() {
        int n = 9;
        findPermutation(n);
    }
}
// This code is contributed by 29AjayKumar

PHP

<?php
// PHP implementation of the above approach
 
// Function to print the permutation
function findPermutation($n)
{
    $res = array();
 
    // Initial numbers to be pushed
    // to result
    $en = 2;
    $on = 1;
 
    // If n is even
    if ($n % 2 == 0)
    {
        for ($i = 0; $i < $n; $i++)
        {
            if (i % 2 == 0)
            {
                array_push($res, $en);
                $en += 2;
            } else
            {
                array_push($res, $on);
                $on += 2;
            }
        }
    }
 
    // If n is odd
    else
    {
        for ($i = 0; $i < $n - 2; $i++)
        {
            if ($i % 2 == 0)
            {
                array_push($res, $en);
                $en += 2;
            }
            else
            {
                array_push($res, $on);
                $on += 2;
            }
        }
        array_push($res, $n);
        array_push($res, $n - 2);
    }
 
    // Print result
    for ($i = 0; $i < $n; $i++)
        echo $res[$i] . " ";
    echo "\n";
}
 
// Driver Code
$n = 9;
findPermutation($n);
 
// This code is contributed by ita_c
?>

Javascript

<script>
 
// Javascript implementation of the above approach
 
// Function to print the permutation
function findPermutation(n)
{
    let res = [];
     
    // Initial numbers to be pushed to result
    let en = 2, on = 1;
 
    // If n is even
    if (n % 2 == 0)
    {
        for(let i = 0; i < n; i++)
        {
            if (i % 2 == 0)
            {
                res.push(en);
                en += 2;
            }
            else
            {
                res.push(on);
                on += 2;
            }
        }
    }
    // If n is odd
    else
    {
        for(let i = 0; i < n - 2; i++)
        {
            if (i % 2 == 0)
            {
                res.push(en);
                en += 2;
            }
            else
            {
                res.push(on);
                on += 2;
            }
        }
        res.push(n);
        res.push(n - 2);
    }
 
    // Print result
    for(let i = 0; i < n; i++)
    {
        document.write(res[i] + " ");
    }
    document.write("");
}
 
// Driver Code
let n = 9;
 
findPermutation(n);
 
// This code is contributed by avanitrachhadiya2155
 
</script>

Producción: 

2 1 4 3 6 5 8 9 7

Complejidad de tiempo: O(n), donde n es el entero positivo dado.

Espacio auxiliar: O(n), donde n es el entero positivo dado.

Este artículo es una contribución de Sarthak Kohli . 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.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
 

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *