Cuente las permutaciones de todos los números enteros hasta N que pueden formar un gráfico acíclico basado en condiciones dadas

Dado un número entero N, la tarea es encontrar el número de permutaciones de números enteros del rango [1, N] que pueden formar un gráfico acíclico de acuerdo con las siguientes condiciones:

• Para cada 1 ≤ i ≤ N , encuentre el j más grande tal que 1 ≤ j < i y A[j] > A[i ], y agregue un borde no dirigido entre el Node i y el Node j .
• Para cada 1 ≤ i ≤ N , encuentre el j más pequeño tal que i < j ≤ N y A[j] > A[i] , y agregue un borde no dirigido entre el Node i y el Node j .

Ejemplos:

Entrada: 3
Salida: 4
Explicación: 
{1, 2, 3}: Posible (Bordes del gráfico: { [1, 2], [2, 3] }. Por lo tanto, no existe ningún ciclo) 
{1, 3, 2}: Posible (Bordes del gráfico: { [1, 3], [2, 3] }. Por lo tanto, no existe ningún ciclo) 
{2, 1, 3}: No es posible (Bordes del gráfico: { [2, 3], [1, 3] , [1, 2] }. Por lo tanto, existe un ciclo) 
{2, 3, 1}: Posible (Bordes del gráfico: { [2, 3], [1, 3] }. Por lo tanto, no existe un ciclo) 
{3, 1 , 2}: No es posible (Bordes del gráfico: { [1, 2], [1, 3], [2, 3] }. Por lo tanto, el ciclo existe) 
{3, 2, 1}: Posible (Bordes del gráfico: { [ 2, 3], [1, 2] }. Por lo tanto, no existe ningún ciclo)

Entrada: 4
Salida: 8

Enfoque: siga los pasos a continuación para resolver el problema:

• Hay un total de N! arrays posibles que se pueden generar que consisten en permutaciones de enteros del rango [1, N] .
• De acuerdo con las condiciones dadas, si i, j, k (i < j < k) son índices del arreglo, entonces si A[i] > A[j] y A[j] < A[k] , entonces habrá ser un ciclo que consta de aristas { [A[j], A[i]], [A[j], A[k]], [A[i], A[k]]} .
• Al eliminar estas permutaciones, quedan 2 ^{(N – 1)} permutaciones posibles.
• Las permutaciones restantes dan solo dos posiciones posibles para enteros del rango [1, N – 1] y 1 posición posible para N .

Ilustración: 
Para N = 3:  la
permutación {2, 1, 3} contiene un ciclo como A[0] > A[1] y A[1] < A[2]. 
La permutación {3, 1, 2} contiene un ciclo como A[0] > A[1] y A[1] < A[2].
Todas las permutaciones restantes pueden generar un gráfico acíclico. 
Por lo tanto, la cuenta de permutaciones válidas = 3! – 2 = 4 = 2 ^{3 – 1} 

• Por lo tanto, escriba 2 ^{N – 1} como la respuesta requerida.

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

// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
 
// Find the count of possible graphs
void possibleAcyclicGraph(int N)
{
    cout << pow(2, N - 1);
    return;
}
 
// Driver Code
int main()
{
 
    int N = 4;
    possibleAcyclicGraph(N);
 
    return 0;
}

// Java implementation of
// the above approach
import java.util.*;
class GFG{
 
// Find the count of
// possible graphs
static void possibleAcyclicGraph(int N)
{
  System.out.print((int)Math.pow(2,
                                 N - 1));
  return;
}
 
// Driver Code
public static void main(String[] args)
{
  int N = 4;
  possibleAcyclicGraph(N);
}
}
 
// This code is contributed by Princi Singh

# Python3 implementation of above approach
 
# Find the count of possible graphs
def possibleAcyclicGraph(N):
     
    print(pow(2, N - 1))
    return
 
# Driver code
if __name__ == '__main__':
     
    N = 4
     
    possibleAcyclicGraph(N)
 
# This code is contributed by mohit kumar 29

// C# implementation of
// the above approach
using System;
 
class GFG{
     
// Find the count of
// possible graphs
static void possibleAcyclicGraph(int N)
{
    Console.Write((int)Math.Pow(2, N - 1));
     
    return;
}
  
// Driver Code
public static void Main()
{
    int N = 4;
     
    possibleAcyclicGraph(N);
}
}
 
// This code is contributed by sanjoy_62

<script>
 
// Javascript implementation of above approach
 
// Find the count of
// possible graphs
function possibleAcyclicGraph(N)
{
    document.write(Math.pow(2, N - 1));
    return;
}
  
// Driver Code
let N = 4;
 
possibleAcyclicGraph(N);
 
// This code is contributed by target_2
 
</script>

8

Complejidad de tiempo: O(logN)
Complejidad de espacio: O(1)