Cuente las permutaciones unimodales y no unimodales de los primeros N números naturales

Posted on by Rudeus Greyrat

Dado un entero N , la tarea es contar el número total de permutaciones unimodales y no unimodales de enteros [1, N] posibles.

Una permutación unimodal es una permutación que aumenta hasta cierto punto, después del cual comienza a disminuir. 
Todas las demás permutaciones, excepto las unimodales, son permutaciones no unimodales .

Nota: Dado que el recuento total puede ser muy grande, imprima el módulo 10 9 +7.

Ejemplos:

Entrada: N = 3 
Salida: 4 2 
Explicación: 
Todas las permutaciones unimodales posibles son {1, 2, 3}, {1, 3, 2}, {2, 3, 1}, {3, 2, 1}. 
Por lo tanto, la cuenta de permutaciones unimodales es 4. 
Las permutaciones restantes son {2, 1, 3}, {3, 1, 2}. 
Por lo tanto, la cuenta de permutaciones no unimodales es 2.

Entrada: N = 4 
Salida: 8 16

Enfoque ingenuo: el enfoque más simple es generar todas las permutaciones posibles de números enteros del rango [1, N] y luego imprimir el recuento de todas esas permutaciones que son unimodales. Imprima el recuento de permutaciones unimodales y no unimodales en consecuencia. 
Complejidad temporal: O(N!) 
Espacio auxiliar: O(N)

Enfoque eficiente: para optimizar el enfoque anterior, la idea es encontrar primero el número total de permutaciones unimodales posibles para un número entero N y luego encontrar el número de permutaciones no unimodales para restar el número de permutaciones unimodales del número total. permutaciones A continuación se muestran los pasos:

  1. Construya permutaciones unimodales de longitud N en una array de longitud infinita.
  2. Coloque N en cualquier lugar de la permutación, entonces hay exactamente dos posiciones en las que se puede colocar el elemento (N – 1), es decir, a la izquierda oa la derecha de N .
  3. Supongamos que va a la derecha. Ahora, el (N – 2) ésimo elemento se puede colocar a la izquierda o a la derecha en la permutación actual.
  4. Esto continúa para todos los elementos hasta 1. Observe que hay dos opciones para cada elemento excepto N .
  5. Entonces, el número de permutaciones unimodales de longitud N será 2 N – 1
  6. ¡ El número total de permutaciones será N! .
  7. Ahora el número total de permutaciones no unimodales será igual a (¡N! – permutaciones unimodales).

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;
 
int mod = 1e9 + 7;
const int mx = 1e6;
int fact[mx + 1];
 
// Function to calculate the
// factorials up to a number
void Calculate_factorial()
{
    fact[0] = 1;
 
    // Calculate the factorial
    for (int i = 1; i <= mx; i++) {
        fact[i] = i * fact[i - 1];
        fact[i] %= mod;
    }
}
 
// Function to find power(a, b)
int UniModal_per(int a, int b)
{
    long long int res = 1;
 
    // Iterate until b exists
    while (b) {
 
        // If b is divisible by 2
        if (b % 2)
            res = res * a;
        res %= mod;
        a = a * a;
        a %= mod;
 
        // Decrease the value of b
        b /= 2;
    }
 
    // Return the answer
    return res;
}
 
// Function that counts the unimodal
// and non-unimodal permutations of
// a given integer N
void countPermutations(int n)
{
 
    // Function Call for finding
    // factorials up to N
    Calculate_factorial();
 
    // Function to count unimodal
    // permutations
    int uni_modal = UniModal_per(2, n - 1);
 
    // Non-unimodal permutation is
    // N! - unimodal permutations
    int nonuni_modal = fact[n] - uni_modal;
 
    cout << uni_modal << " " << nonuni_modal;
 
    return;
}
 
// Driver Code
int main()
{
    // Given Number N
    int N = 4;
 
    // Function Call
    countPermutations(N);
 
    return 0;
}

Java

// Java program for
// the above approach
class GFG {
 
    static int mod = (int)(1e9 + 7);
    static int mx = (int)1e6;
    static int[] fact = new int[(int)mx + 1];
 
    // Function to calculate the
    // factorials up to a number
    static void Calculate_factorial()
    {
        fact[0] = 1;
 
        // Calculate the factorial
        for (int i = 1; i <= mx; i++) {
            fact[i] = i * fact[i - 1];
            fact[i] %= mod;
        }
    }
 
    // Function to find power(a, b)
    static int UniModal_per(int a, int b)
    {
        int res = 1;
 
        // Iterate until b exists
        while (b > 0) {
            // If b is divisible by 2
            if (b % 2 != 0)
                res = res * a;
            res %= mod;
            a = a * a;
            a %= mod;
 
            // Decrease the value of b
            b /= 2;
        }
 
        // Return the answer
        return res;
    }
 
    // Function that counts the unimodal
    // and non-unimodal permutations of
    // a given integer N
    static void countPermutations(int n)
    {
        // Function Call for finding
        // factorials up to N
        Calculate_factorial();
 
        // Function to count unimodal
        // permutations
        int uni_modal = UniModal_per(2, n - 1);
 
        // Non-unimodal permutation is
        // N! - unimodal permutations
        int nonuni_modal = fact[n] - uni_modal;
 
        System.out.print(uni_modal + " " + nonuni_modal);
 
        return;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        // Given Number N
        int N = 4;
 
        // Function Call
        countPermutations(N);
    }
}
 
// This code is contributed by shikhasingrajput

Python3

# Python3 program for the above approach
mod = 1e9 + 7
mx = 1000000
fact = [0] * (mx + 1)
 
# Function to calculate the
# factorials up to a number
 
 
def Calculate_factorial():
 
    fact[0] = 1
 
    # Calculate the factorial
    for i in range(1, mx + 1):
        fact[i] = i * fact[i - 1]
        fact[i] %= mod
 
# Function to find power(a, b)
 
 
def UniModal_per(a, b):
 
    res = 1
 
    # Iterate until b exists
    while (b != 0):
 
        # If b is divisible by 2
        if (b % 2 != 0):
            res = res * a
 
        res %= mod
        a = a * a
        a %= mod
 
        # Decrease the value of b
        b //= 2
 
    # Return the answer
    return res
 
# Function that counts the unimodal
# and non-unimodal permutations of
# a given integer N
 
 
def countPermutations(n):
 
    # Function Call for finding
    # factorials up to N
    Calculate_factorial()
 
    # Function to count unimodal
    # permutations
    uni_modal = UniModal_per(2, n - 1)
 
    # Non-unimodal permutation is
    # N! - unimodal permutations
    nonuni_modal = fact[n] - uni_modal
 
    print(int(uni_modal), "",
          int(nonuni_modal))
 
    return
 
# Driver Code
# Given number N
N = 4
 
# Function call
countPermutations(N)
 
# This code is contributed by code_hunt

C#

// C# program for
// the above approach
using System;
class GFG
{
    static int mod = (int)(1e9 + 7);
    static int mx = (int)1e6;
    static int[] fact = new int[(int)mx + 1];
 
    // Function to calculate the
    // factorials up to a number
    static void Calculate_factorial()
    {
        fact[0] = 1;
 
        // Calculate the factorial
        for (int i = 1; i <= mx; i++)
        {
            fact[i] = i * fact[i - 1];
            fact[i] %= mod;
        }
    }
 
    // Function to find power(a, b)
    static int UniModal_per(int a, int b)
    {
        int res = 1;
 
        // Iterate until b exists
        while (b > 0)
        {
            // If b is divisible by 2
            if (b % 2 != 0)
                res = res * a;
 
            res %= mod;
            a = a * a;
            a %= mod;
 
            // Decrease the value of b
            b /= 2;
        }
 
        // Return the answer
        return res;
    }
 
    // Function that counts the unimodal
    // and non-unimodal permutations of
    // a given integer N
    static void countPermutations(int n)
    {
        // Function Call for finding
        // factorials up to N
        Calculate_factorial();
 
        // Function to count unimodal
        // permutations
        int uni_modal = UniModal_per(2, n - 1);
 
        // Non-unimodal permutation is
        // N! - unimodal permutations
        int nonuni_modal = fact[n] - uni_modal;
 
        Console.Write(uni_modal + " " + nonuni_modal);
        return;
    }
 
    // Driver Code
    public static void Main(String[] args)
    {
        // Given Number N
        int N = 4;
 
        // Function Call
        countPermutations(N);
    }
}
 
// This code is contributed by shikhasingrajput

Javascript

<script>
      // JavaScript program for
      // the above approach
      var mod = parseInt(1e9 + 7);
      var mx = 1000000;
      var fact = new Array(mx + 1).fill(0);
 
      // Function to calculate the
      // factorials up to a number
      function Calculate_factorial() {
        fact[0] = 1;
 
        // Calculate the factorial
        for (var i = 1; i <= mx; i++) {
          fact[i] = i * fact[i - 1];
          fact[i] %= mod;
        }
      }
 
      // Function to find power(a, b)
      function UniModal_per(a, b) {
        var res = 1;
 
        // Iterate until b exists
        while (b > 0) {
          // If b is divisible by 2
          if (b % 2 !== 0) res = res * a;
 
          res %= mod;
          a = a * a;
          a %= mod;
 
          // Decrease the value of b
          b = parseInt(b / 2);
        }
 
        // Return the answer
        return res;
      }
 
      // Function that counts the unimodal
      // and non-unimodal permutations of
      // a given integer N
      function countPermutations(n) {
        // Function Call for finding
        // factorials up to N
        Calculate_factorial();
 
        // Function to count unimodal
        // permutations
        var uni_modal = UniModal_per(2, n - 1);
 
        // Non-unimodal permutation is
        // N! - unimodal permutations
        var nonuni_modal = fact[n] - uni_modal;
 
        document.write(uni_modal + " " + nonuni_modal);
        return;
      }
 
      // Driver Code
      // Given Number N
      var N = 4;
 
      // Function Call
      countPermutations(N);
    </script>
Producción

8 16

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

Publicación traducida automáticamente

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