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