Permutación presente en el medio del ordenamiento lexicográfico de permutaciones de longitud máxima N formada por números enteros hasta K

Dados dos números enteros positivos K y N , la tarea es encontrar la permutación presente en el medio de todas las permutaciones de longitud máxima N , que consta de números enteros del rango [1, K], ordenados lexicográficamente.

Ejemplos:

Entrada: K = 3, N = 2
Salida: 2 1
Explicación: El orden lexicográfico de todas las permutaciones posibles es:

  1. {1}.
  2. {1, 1}
  3. {1, 2}
  4. {1, 3}
  5. {2}
  6. {2, 1}
  7. {2, 2}
  8. {2, 3}
  9. {3}
  10. {3, 1}
  11. {3, 2}
  12. {3, 3}

Por lo tanto, la secuencia lexicográficamente más pequeña del medio es (N/2) th (= 6th ) secuencia, que es {2, 1}.

Entrada: K = 2, N = 4
Salida: 1 2 2 2

Enfoque ingenuo: el enfoque más simple para resolver el problema dado es generar todas las subsecuencias posibles de una longitud [1, N] , que consta de números enteros de [1, K] . Almacene estos elementos en una array. Después de generar todas las subsecuencias, ordene la lista almacenada de subsecuencias e imprima el elemento central de la lista.

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

Enfoque eficiente: el enfoque anterior se puede optimizar verificando la paridad de K , ya sea que K sea impar o par, y luego encuentre lexicográficamente la secuencia más pequeña en el medio en consecuencia. Siga los pasos a continuación para resolver el problema:

  • Si el valor de K es par , entonces exactamente la mitad de las secuencias comienzan con un número entero K/2 o menos. Por lo tanto, la secuencia resultante es K/2 seguida de (N – 1) aparición de K .
  • Si el valor K es impar , considere B como una secuencia que contiene N ocurrencias de (K + 1)/2 .
    • Para una secuencia X , sea f(X) una secuencia tal que X i en X se reemplaza con (K + 1 − X i ) .
    • La única excepción ocurre con los prefijos de B .
  • Comience con la secuencia B y realice los siguientes pasos (N – 1)/2 veces:
    • Si el último elemento de la secuencia actual es 1 , elimínelo.
    • De lo contrario, disminuya el último elemento en 1 , y mientras la secuencia contenga menos de N elementos, e inserte K al final de la secuencia B.
  • Después de completar los pasos anteriores, imprima la secuencia obtenida en la array B[] .

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

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function that finds the middle the
// lexicographical smallest sequence
void lexiMiddleSmallest(int K, int N)
{
    // If K is even
    if (K % 2 == 0) {
 
        // First element is K/2
        cout << K / 2 << " ";
 
        // Remaining elements of the
        // sequence are all integer K
        for (int i = 0; i < N - 1; ++i) {
            cout << K << " ";
        }
        cout << "\n";
        exit(0);
    }
 
    // Stores the sequence when K
    // is odd
    vector<int> a(N, (K + 1) / 2);
 
    // Iterate over the range [0, N/2]
    for (int i = 0; i < N / 2; ++i) {
 
        // Check if the sequence ends
        // with in 1 or not
        if (a.back() == 1) {
 
            // Remove the sequence
            // ending in 1
            a.pop_back();
        }
 
        // If it doesn't end in 1
        else {
 
            // Decrement by 1
            --a.back();
 
            // Insert K to the sequence
            // till its size is N
            while ((int)a.size() < N) {
                a.push_back(K);
            }
        }
    }
 
    // Print the sequence stored
    // in the vector
    for (auto i : a) {
        cout << i << " ";
    }
    cout << "\n";
}
 
// Driver Code
int main()
{
    int K = 2, N = 4;
    lexiMiddleSmallest(K, N);
 
    return 0;
}

Java

// Java program for the above approach
import java.io.*;
import java.util.*;
 
class GFG {
 
    // Function that finds the middle the
    // lexicographical smallest sequence
    static void lexiMiddleSmallest(int K, int N)
    {
       
        // If K is even
        if (K % 2 == 0) {
 
            // First element is K/2
            System.out.print(K / 2 + " ");
 
            // Remaining elements of the
            // sequence are all integer K
            for (int i = 0; i < N - 1; ++i) {
                System.out.print(K + " ");
            }
            System.out.println();
            return;
        }
 
        // Stores the sequence when K
        // is odd
        ArrayList<Integer> a = new ArrayList<Integer>();
 
        // Iterate over the range [0, N/2]
        for (int i = 0; i < N / 2; ++i) {
 
            // Check if the sequence ends
            // with in 1 or not
            if (a.get(a.size() - 1) == 1) {
 
                // Remove the sequence
                // ending in 1
                a.remove(a.size() - 1);
            }
 
            // If it doesn't end in 1
            else {
 
                // Decrement by 1
                int t = a.get(a.size() - 1) - 1;
                a.set(a.get(a.size() - 1), t);
 
                // Insert K to the sequence
                // till its size is N
                while (a.size() < N) {
                    a.add(K);
                }
            }
        }
 
        // Print the sequence stored
        // in the vector
        for (int i : a) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int K = 2, N = 4;
        lexiMiddleSmallest(K, N);
    }
}
 
// This code is contributed by Dharanendra L V.

Python3

# Python3 program for the above approach
 
# Function that finds the middle the
# lexicographical smallest sequence
def lexiMiddleSmallest(K, N):
    # If K is even
    if (K % 2 == 0):
 
        # First element is K/2
        print(K // 2,end=" ")
 
        # Remaining elements of the
        # sequence are all integer K
        for i in range(N - 1):
            print(K, end = " ")
        print()
        return
 
    # Stores the sequence when K
    # is odd
    a = [(K + 1) // 2]*(N)
 
    # Iterate over the range [0, N/2]
    for i in range(N//2):
        # Check if the sequence ends
        # with in 1 or not
        if (a[-1] == 1):
 
            # Remove the sequence
            # ending in 1
            del a[-1]
 
        # If it doesn't end in 1
        else:
 
            # Decrement by 1
            a[-1] -= 1
 
            # Insert K to the sequence
            # till its size is N
            while (len(a) < N):
                a.append(K)
 
    # Print sequence stored
    # in the vector
    for i in a:
        print(i, end = " ")
    print()
 
# Driver Code
if __name__ == '__main__':
    K, N = 2, 4
    lexiMiddleSmallest(K, N)
 
# This code is contributed by mohit kumar 29.

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG {
 
    // Function that finds the middle the
    // lexicographical smallest sequence
    static void lexiMiddleSmallest(int K, int N)
    {
        // If K is even
        if (K % 2 == 0) {
 
            // First element is K/2
            Console.Write(K / 2 + " ");
 
            // Remaining elements of the
            // sequence are all integer K
            for (int i = 0; i < N - 1; ++i) {
                Console.Write(K + " ");
            }
            Console.WriteLine();
            return;
        }
 
        // Stores the sequence when K
        // is odd
        List<int> a = new List<int>();
 
        // Iterate over the range [0, N/2]
        for (int i = 0; i < N / 2; ++i) {
 
            // Check if the sequence ends
            // with in 1 or not
            if (a[a.Count - 1] == 1) {
 
                // Remove the sequence
                // ending in 1
                a.Remove(a.Count - 1);
            }
 
            // If it doesn't end in 1
            else {
 
                // Decrement by 1
                a[a.Count - 1] -= 1;
 
                // Insert K to the sequence
                // till its size is N
                while ((int)a.Count < N) {
                    a.Add(K);
                }
            }
        }
 
        // Print the sequence stored
        // in the vector
        foreach(int i in a) { Console.Write(i + " "); }
        Console.WriteLine();
    }
 
    // Driver Code
    public static void Main()
    {
        int K = 2, N = 4;
        lexiMiddleSmallest(K, N);
    }
}
 
// This code is contributed by ukasp.

Javascript

<script>
 
// javascript program for the above approach
 
    // Function that finds the middle the
    // lexicographical smallest sequence
    function lexiMiddleSmallest(K, N)
    {
        // If K is even
        if (K % 2 == 0) {
  
            // First element is K/2
            document.write(K / 2 + " ");
  
            // Remaining elements of the
            // sequence are all integer K
            for (let i = 0; i < N - 1; ++i) {
                document.write(K + " ");
            }
            document.write("<br/>");
            return;
        }
  
        // Stores the sequence when K
        // is odd
        let a = [];
  
        // Iterate over the range [0, N/2]
        for (let i = 0; i < N / 2; ++i) {
  
            // Check if the sequence ends
            // with in 1 or not
            if (a[a.length - 1] == 1) {
  
                // Remove the sequence
                // ending in 1
                a.pop(a.length - 1);
            }
  
            // If it doesn't end in 1
            else {
  
                // Decrement by 1
                a[a.length - 1] -= 1;
  
                // Insert K to the sequence
                // till its size is N
                while (a.length < N) {
                    a.push(K);
                }
            }
        }
  
        // Print the sequence stored
        // in the vector
        for(let i in a) { document.write(i + " "); }
        document.write("<br/>");
    }
 
// Driver Code
 
    let K = 2, N = 4;
    lexiMiddleSmallest(K, N);
     
 
</script>
Producción: 

1 2 2 2

 

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

Publicación traducida automáticamente

Artículo escrito por huzaifa0602 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 *