Given a positive integer N, the task is to print all the subsequences of the array in such a way that the subsequence is first decreasing then increasing by selecting ceil(N/2) elements from 1 to N.
Examples:
Input: N = 5
Output :
(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).
These are the valid sequences of size 3 which first decreases and then increases.
Approach: The approach is based on using the inbuilt function of python itertools.permutation to generate all the subsequences of size ceil(N/2). Follow the steps below to solve the problem:
- Initialize an array arr[] and insert all the elements from 1 to N.
- Initialize a variable K as ceil(N/2).
- Insert all the subsequences in the array “sequences” using the built-in function called itertools.permutations(arr, k).
- Iterate through the array sequences using the variable seq and perform the following steps:
- Check if seq[1]>seq[0] or seq[-1]< seq[-2] or if the seq is increasing or descending then continue else this sequence is not satisfying the condition mentioned above.
- If there is more than 1 element than seq[i]<seq[i-1] and seq[i] <seq[i+1] then also continue and do not print the array.
- If the seq does not follow any of the points above, then print the seq.
Below is the implementation of the above approach:
C++
// cpp program for the above approach#include<bits/stdc++.h>using namespace std;// Function to check if the sequence is valid// or notbool 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
# Python3 program for the above approach# import the ceil permutations in function from math import ceil# Function to generate all the permutationsfrom itertools import permutations# Function to check if the sequence is valid# or notdef 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 codeN = 5K = ceil(N / 2)arr = list(range(1, N + 1))# Generate all permutation of size N / 2 using# default functionsequences = list(permutations(arr, K))# Print the sequence which is valid valley subsequencefor seq in sequences: # Check whether the seq is valid or not # Function Call if ValidSubsequence(seq): print(seq, end =" ") |
Java
import java.util.ArrayList;import java.util.Arrays;import java.util.HashMap;import java.util.List;import java.util.Map;public class ValleySubSequence { // Function to check if the sequence is valid // or not public static boolean ValidSubsequence(List<Integer> seq) { // If first element is greater or last second // element is greater than last element int n = seq.size(); if ((seq.get(0) < seq.get(1)) || (seq.get(n - 1) < seq.get(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.get(i) > seq.get(i + 1)) { i++; continue; } else if (seq.get(i) < seq.get(i + 1)) { int j = i + 1; if ((j != (seq.size() - 1)) && (seq.get(j) > seq.get(j + 1))) return false; } i += 1; } // If the sequence do not follow above condition // Return True return true; } public static void main(String[] args) { int N = 5; int K = (N + 1) / 2; List<Integer> arr = new ArrayList<Integer>(); for (int i = 0; i < N; i++) { arr.add(i + 1); } // Generate all permutation of size N / 2 using // default function List<List<Integer>> sequences = new ArrayList<List<Integer>>(); do { List<Integer> temp = new ArrayList<Integer>(); for (int i = 0; i < K; i++) { temp.add(arr.get(i)); } sequences.add(temp); } while (nextPermutation(arr)); // Print the sequence which is valid valley subsequence Map<List<Integer>, Integer> vis = new HashMap<List<Integer>, Integer>(); for (List<Integer> seq : sequences) { // Check whether the seq is valid or not // Function Call if (ValidSubsequence(seq) && !vis.containsKey(seq)) { vis.put(seq, 1); for (int j : seq) { System.out.print(j + " "); } System.out.println(); } } } public static boolean nextPermutation(List<Integer> arr) { int n = arr.size(); int i = n - 2; while (i >= 0 && arr.get(i) >= arr.get(i + 1)) { i--; } if (i < 0) { return false; } int j = n - 1; while (arr.get(j) <= arr.get(i)) { j--; } int temp = arr.get(i); arr.set(i, arr.get(j)); arr.set(j, temp); int l = i + 1; int r = n - 1; while (l < r) { int m = arr.get(l); arr.set(l, arr.get(r)); arr.set(r, m); l++; r--; } return true; }} |
C#
using System;using System.Collections.Generic;class GFG { // Function to check if the sequence is valid // or not public static bool ValidSubsequence(List<int> seq) { // If first element is greater or last second // element is greater than last element int n = seq.Count; 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 while (i < (seq.Count - 1)) { if (seq[i] > seq[i + 1]) { i++; continue; } else if (seq[i] < seq[i + 1]) { int j = i + 1; if ((j != (seq.Count - 1)) && (seq[j] > seq[j + 1])) return false; } i += 1; } // If the sequence do not follow above condition // Return True return true; } public static void Main(string[] args) { int N = 5; int K = (N + 1) / 2; List<int> arr = new List<int>(); for (int i = 0; i < N; i++) { arr.Add(i + 1); } // Generate all permutation of size N / 2 using // default function List<List<int> > sequences = new List<List<int> >(); do { List<int> temp = new List<int>(); for (int i = 0; i < K; i++) { temp.Add(arr[i]); } sequences.Add(temp); } while (nextPermutation(arr)); // Print the sequence which is valid valley // subsequence Dictionary<Tuple<int, int, int>, int> vis = new Dictionary<Tuple<int, int, int>, int>(); foreach(List<int> seq1 in sequences) { // Check whether the seq is valid or not // Function Call var seq2 = Tuple.Create(seq1[0], seq1[1], seq1[2]); if (ValidSubsequence(seq1) && !vis.ContainsKey(seq2)) { vis.Add(seq2, 1); Console.Write("("); foreach(int j in seq1) { Console.Write(" " + j); } Console.Write(" ) "); } } } // This function converts a given list to its next permutation public static bool nextPermutation(List<int> arr) { int n = arr.Count; int i = n - 2; while (i >= 0 && arr[i] >= arr[i + 1]) { i--; } if (i < 0) { return false; } int j = n - 1; while (arr[j] <= arr[i]) { j--; } int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; int l = i + 1; int r = n - 1; while (l < r) { int m = arr[l]; arr[l] = arr[r]; arr[r] = m; l++; r--; } return true; }}// This code is contributed by phasing17 |
Javascript
// This function generates all valley subsequences of length nfunction generateValleySubsequences(n) {// Calculate the number of elements in the first half of the valley subsequencelet k = Math.floor((n + 1) / 2);// Create an array with elements from 1 to nlet arr = [];for (let i = 0; i < n; i++) {arr.push(i + 1);}// Generate all permutations of the arraylet sequences = [];do {let temp = [];// Take the first k elements of the permutation as the first half of the valley subsequencefor (let i = 0; i < k; i++) {temp.push(arr[i]);}sequences.push(temp);} while (nextPermutation(arr)); // Continue generating permutations until all have been generatedlet output = "";let vis = new Map();// Iterate over all generated sequences and check if they are valid valley subsequencesfor (let seq of sequences) {if (ValidSubsequence(seq) && !vis.has(seq)) {vis.set(seq, 1);// Add the sequence to the output stringoutput += "(" + seq.join(", ") + ") ";}}console.log(output.trim()); // Print the output string with leading and trailing whitespace removed}// This function checks if a sequence is a valid valley subsequencefunction ValidSubsequence(seq) {let n = seq.length;// Check if the first and last elements of the sequence are in decreasing orderif (seq[0] < seq[1] || seq[n - 1] < seq[n - 2]) {return false;}let i = 0;// Iterate over the sequence and check if it is a valley subsequencewhile (i < n - 1) {if (seq[i] > seq[i + 1]) {i++;continue;} else if (seq[i] < seq[i + 1]) {let j = i + 1;// Check if the remaining elements of the sequence are in decreasing orderif (j !== n - 1 && seq[j] > seq[j + 1]) {return false;}}i++;}return true;}// This function generates the next lexicographically larger permutation of an arrayfunction nextPermutation(arr) {let n = arr.length;let i = n - 2;// Find the rightmost element that is smaller than the element to its rightwhile (i >= 0 && arr[i] >= arr[i + 1]) {i--;}// If no such element exists, the array is already the largest permutationif (i < 0) {return false;}let j = n - 1;// Find the smallest element to the right of the element at index i that is greater than the element at index iwhile (arr[j] <= arr[i]) {j--;}// Swap the elements at indices i and jlet temp = arr[i];arr[i] = arr[j];arr[j] = temp;// Reverse the elements from index i + 1 to the end of the arraylet l = i + 1;let r = n - 1;while (l < r) {let m = arr[l];arr[l] = arr[r];arr[r] = m;l++;r--; } return true;}function generateValleySubsequences(n) { let k = Math.floor((n + 1) / 2); let arr = []; for (let i = 0; i < n; i++) { arr.push(i + 1); } let sequences = []; do { let temp = []; for (let i = 0; i < k; i++) { temp.push(arr[i]); } sequences.push(temp); } while (nextPermutation(arr)); let output = ""; let vis = new Map(); for (let seq of sequences) { if (ValidSubsequence(seq) && !vis.has(seq)) { vis.set(seq, 1); output += "(" + seq.join(", ") + ") "; } } console.log(output.trim());}generateValleySubsequences(5); |
Output:
(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)
Time Complexity: O(CNN/2 * ceil(N/2)! *N)
Auxiliary Space: O(CNN/2 * ceil(N/2)!)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
