Imprima todas las subsecuencias primero decreciendo y luego aumentando seleccionando N/2 elementos de [1, N]

Dado un entero positivo N , la tarea es imprimir todas las subsecuencias de la array de tal manera que la subsecuencia primero disminuya y luego aumente seleccionando ceil(N/2) elementos de 1 a N .

Ejemplos:

Entrada: N = 5
Salida:
(2, 1, 3), (2, 1, 4), (2, 1, 5), (3, 1, 2), (3, 1, 4), (3, 1, 5), (3, 2, 4), (3, 2, 5), (4, 1, 2), 
(4, 1, 3), (4, 1, 5), (4, 2, 3), (4, 2, 5), (4, 3, 5), (5, 1, 2), (5, 1, 3), (5, 1, 4), (5, 2, 3) , 
(5, 2, 4), (5, 3, 4).
Estas son las secuencias válidas de tamaño 3 que primero disminuye y luego aumenta. 

Enfoque: el enfoque se basa en el uso de la función incorporada de python itertools.permutation para generar todas las subsecuencias de tamaño ceil (N/2). Siga los pasos a continuación para resolver el problema:

• Inicialice una array arr[] e inserte todos los elementos del 1 al N.
• Inicializa una variable K como ceil(N/2) .
• Inserte todas las subsecuencias en la array » secuencias » usando la función integrada llamada itertools.permutations(arr, k) .
• Iterar a través de las secuencias de array usando la variable seq y realizar los siguientes pasos:
  • Verifique si seq[1]>seq[0] o seq[-1]< seq [-2] o si la secuencia está aumentando o descendiendo, continúe, de lo contrario, esta secuencia no cumple la condición mencionada anteriormente.
  • Si hay más de 1 elemento que seq[i]<seq[i-1] y seq[i] <seq[i+1] entonces también continúe y no imprima la array.
  • Si la secuencia no sigue ninguno de los puntos anteriores, imprima la secuencia .

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

// cpp program for the above approach
#include<bits/stdc++.h>
using namespace std;
 
// Function to check if the sequence is valid
// or not
bool  ValidSubsequence(vector<int>seq)
{
 
  // If first element is greater or last second
  // element is greater than last element
  int n = seq.size();
  if ((seq[0] < seq[1]) || (seq[n - 1] < seq[n - 2]))
    return false;
  int i = 0;
 
  // If the sequence is decreasing or increasing
  // or sequence is increasing return false
  // return 0;
  while (i<(seq.size() - 1))
  {
    if (seq[i] > seq[i + 1])
    {
      i++;
      continue;
    }
    else if (seq[i] < seq[i + 1]){
 
      int j = i + 1;
      if ((j != (seq.size())-1) && (seq[j]>seq[j + 1]))
        return false;
    }
    i+= 1;
 
  }
  // If the sequence do not follow above condition
  // Return True
  return true;
 
}
 
 
int main(){
  int N = 5;
  int K = (N+1)/2;
  vector<int>arr,arr0;
  for(int i = 0; i < N; i++)
  {
    arr.push_back(i+1);
  }
 
  // Generate all permutation of size N / 2 using
  // default function
  vector<vector<int>>sequences;
  do{
    vector<int>temp;
    for(int i = 0; i < K; i++)
    {
      temp.push_back(arr[i]);
    }
    sequences.push_back(temp);
  }while(next_permutation(arr.begin(),arr.end()));
 
  // Print the sequence which is valid valley subsequence
  map<vector<int>,int>vis;
  for (auto seq :sequences)
  {
 
    // Check whether the seq is valid or not
    // Function Call
    if (ValidSubsequence(seq) && !vis[seq])
    {
      vis[seq] = 1;
      for(auto j:seq){
        cout<<j<<" ";
      }
      cout<<endl;
    }
  }
}
 
// This code is contributed by Stream_Cipher

# Python3 program for the above approach
 
# import the ceil permutations in function
from math import ceil
 
# Function to generate all the permutations
from itertools import permutations
 
# Function to check if the sequence is valid
# or not
def ValidSubsequence(seq):
   
  # If first element is greater or last second
  # element is greater than last element
  if (seq[0]<seq[1]) or (seq[-1]<seq[-2]): return False
   
  i = 0
   
  # If the sequence is decreasing or increasing
  # or sequence is increasing return false
  while i<len(seq)-1:
    if seq[i]>seq[i + 1]:
      pass
    elif seq[i]<seq[i + 1]:
      j = i + 1
      if (j != len(seq)-1) and (seq[j]>seq[j + 1]):
        return False
    i+= 1
     
   # If the sequence do not follow above condition
   # Return True
  return True
 
         
# Driver code
N = 5
K = ceil(N / 2)
arr = list(range(1, N + 1))
 
# Generate all permutation of size N / 2 using
# default function
sequences = list(permutations(arr, K))
 
# Print the sequence which is valid valley subsequence
for seq in sequences:
  # Check whether the seq is valid or not
  # Function Call
  if ValidSubsequence(seq):
    print(seq, end =" ")

(2, 1, 3) (2, 1, 4) (2, 1, 5) (3, 1, 2) (3, 1, 4) (3, 1, 5) (3, 2, 4) (3, 2, 5) (4, 1, 2) (4, 1, 3) (4, 1, 5) (4, 2, 3) (4, 2, 5) (4, 3, 5) (5, 1, 2) (5, 1, 3) (5, 1, 4) (5, 2, 3) (5, 2, 4) (5, 3, 4)

Complejidad de tiempo: O(C ^N _N/2  * ceil(N/2)! *N)
Espacio auxiliar: O(C ^N _N/2  * ceil(N/2)!)