Permutación lexicográficamente más pequeña sin dígitos en el índice original

Dado un número entero N. La tarea es encontrar la permutación lexicográficamente más pequeña de un número entero de la forma: 12345…N tal que no aparezca ningún dígito en el índice como en el número original, es decir, si P ¹ P ² P ³ …P ^N es nuestro permutación entonces P ⁱ no debe ser igual a i.

Nota : N es mayor que 1 y menor que 10.

Ejemplos :

Input : N = 5
Output : 21435

Input : N = 2
Output : 21

Para la permutación más pequeña, los dígitos más pequeños deben colocarse al principio. Entonces, hay dos casos para manejar este problema.

N es par , es decir, el número de dígitos es par. En tal caso, si todos los dígitos impares se colocaron en el siguiente índice par y todos los dígitos pares se colocaron en sus índices anteriores, tendremos la permutación más pequeña que satisfaga la condición anterior.
N es impar , es decir, el número de dígitos es impar. En esto, todos son similares al caso anterior, el único cambio es que los últimos tres dígitos se barajan de tal manera que su permutación es la más pequeña. Por ejemplo, si tenemos 123 como los últimos tres dígitos, entonces 231 es la permutación más pequeña posible.

Algoritmo :

If N is even:place all even digits (upto N) in increasing order at odd index.place all odd digits in increasing order at even index.elseplace all even digits (upto N-3) in increasing order at odd index.place all odd digits (upto N-4) in increasing order at even index.Place N at (N-1)th place, N-1 at (N-2)th and N-2 at Nth place.

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

C++

// C++ program to find the smallest permutation
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to print the smallest permutation
string smallestPermute(int n)
{
    char res[n + 1];
 
    // when n is even
    if (n % 2 == 0) {
        for (int i = 0; i < n; i++) {
            if (i % 2 == 0)
                res[i] = 48 + i + 2;
            else
                res[i] = 48 + i;
        }
    }
 
    // when n is odd
    else {
        for (int i = 0; i < n - 2; i++) {
            if (i % 2 == 0)
                res[i] = 48 + i + 2;
            else
                res[i] = 48 + i;
        }
        // handling last 3 digit
        res[n - 1] = 48 + n - 2;
        res[n - 2] = 48 + n;
        res[n - 3] = 48 + n - 1;
    }
 
    // add EOL and print result
    res[n] = '\0';
 
    return res;
}
 
// Driver Code
int main()
{
    int n = 7;
 
    cout << smallestPermute(n);
 
    return 0;
}

Java

// Java program to find the smallest permutation
class GFG
{
 
// Function to print the smallest permutation
static void smallestPermute(int n)
{
    char res[] = new char[n + 1];
 
    // when n is even
    if (n % 2 == 0) {
        for (int i = 0; i < n; i++)
        {
            if (i % 2 == 0)
                res[i] = (char)(48 + i + 2);
            else
                res[i] = (char)(48 + i);
        }
    }
 
    // when n is odd
    else
    {
        for (int i = 0; i < n - 2; i++)
        {
            if (i % 2 == 0)
                res[i] = (char)(48 + i + 2);
            else
                res[i] = (char)(48 + i);
        }
        // handling last 3 digit
        res[n - 1] = (char)(48 + n - 2);
        res[n - 2] = (char)(48 + n);
        res[n - 3] = (char)(48 + n - 1);
    }
 
    // add EOL and print result
    res[n] = '\0';
 
    for (int i = 0; i < n ; i++)
    {
        System.out.print(res[i]);
    }
}
 
// Driver Code
public static void main(String []args)
{
    int n = 7;
 
    smallestPermute(n);
}
}
 
// This code is contributed by ANKITRAI1

Python 3

# Python 3 program to find the
# smallest permutation
 
# Function to print the smallest
# permutation
def smallestPermute( n):
 
    res = [""] * (n + 1)
     
    # when n is even
    if (n % 2 == 0) :
        for i in range(n):
            if (i % 2 == 0):
                res[i] = chr(48 + i + 2)
            else:
                res[i] = chr(48 + i)
 
    # when n is odd
    else :
        for i in range(n - 2 ):
            if (i % 2 == 0):
                res[i] = chr(48 + i + 2)
            else:
                res[i] = chr(48 + i)
         
        # handling last 3 digit
        res[n - 1] = chr(48 + n - 2)
        res[n - 2] = chr(48 + n)
        res[n - 3] = chr(48 + n - 1)
 
    # add EOL and print result
    res = ''.join(res)
    return res
 
# Driver Code
if __name__ == "__main__":
     
    n = 7
    print(smallestPermute(n))
 
# This code is contributed by ita_c

C#

// C# program to find the smallest
// permutation
using System;
class GFG
{
 
// Function to print the smallest
// permutation
static void smallestPermute(int n)
{
    char[] res = new char[n + 1];
 
    // when n is even
    if (n % 2 == 0)
    {
        for (int i = 0; i < n; i++)
        {
            if (i % 2 == 0)
                res[i] = (char)(48 + i + 2);
            else
                res[i] = (char)(48 + i);
        }
    }
 
    // when n is odd
    else
    {
        for (int i = 0; i < n - 2; i++)
        {
            if (i % 2 == 0)
                res[i] = (char)(48 + i + 2);
            else
                res[i] = (char)(48 + i);
        }
        // handling last 3 digit
        res[n - 1] = (char)(48 + n - 2);
        res[n - 2] = (char)(48 + n);
        res[n - 3] = (char)(48 + n - 1);
    }
 
    // add EOL and print result
    res[n] = '\0';
 
    for (int i = 0; i < n ; i++)
    {
        Console.Write(res[i]);
    }
}
 
// Driver Code
public static void Main()
{
    int n = 7;
 
    smallestPermute(n);
}
}
 
// This code is contributed
// by Akanksha Rai

PHP

<?php
// PHP program to find the smallest permutation
 
// Function to print the smallest permutation
function smallestPermute($n)
{
    $res = array_fill(0, $n + 1, "");
 
    // when n is even
    if ($n % 2 == 0)
    {
        for ($i = 0; $i < $n; $i++)
        {
            if ($i % 2 == 0)
                $res[$i] = chr(48 + $i + 2);
            else
                $res[$i] = chr(48 + $i);
        }
    }
 
    // when n is odd
    else
    {
        for ($i = 0; $i < $n - 2; $i++)
        {
            if ($i % 2 == 0)
                $res[$i] = chr(48 + $i + 2);
            else
                $res[$i] = chr(48 + $i);
        }
         
        // handling last 3 digit
        $res[$n - 1] = chr(48 + $n - 2);
        $res[$n - 2] = chr(48 + $n);
        $res[$n - 3] = chr(48 + $n - 1);
    }
 
    // add EOL and print result
    $res[$n] = '\0';
 
    for ($i = 0; $i < $n ; $i++)
    {
        echo $res[$i];
    }
}
 
// Driver Code
$n = 7;
 
smallestPermute($n);
 
// This code is contributed by mits
?>

Javascript

<script>
 
// Javascript program to find the smallest permutation
 
// Function to print the smallest permutation
function smallestPermute(n)
{
    var res = Array(n+1).fill(0);
 
    // when n is even
    if (n % 2 == 0) {
        for (var i = 0; i < n; i++) {
            if (i % 2 == 0)
                res[i] = 48 + i + 2;
            else
                res[i] = 48 + i;
        }
    }
 
    // when n is odd
    else {
        for (var i = 0; i < n - 2; i++) {
            if (i % 2 == 0)
                res[i] = 48 + i + 2;
            else
                res[i] = 48 + i;
        }
        // handling last 3 digit
        res[n - 1] = 48 + n - 2;
        res[n - 2] = 48 + n;
        res[n - 3] = 48 + n - 1;
    }
 
    for(var i =0; i<res.length; i++)
    {
      res[i] = String.fromCharCode(res[i]);
    }
 
    return res.join("");
}
 
// Driver Code
var n = 7;
document.write( smallestPermute(n));
 
</script>

Producción:

Complejidad de Tiempo: O(n), Espacio Auxiliar: O(n)

Publicación traducida automáticamente

Artículo escrito por Shivam.Pradhan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

C++

Java

Python 3

C#

PHP

Javascript

Deja una respuesta Cancelar la respuesta