![Imprimez toutes les sous-séquences en diminuant d’abord puis en augmentant en sélectionnant N/2 éléments de [1, N]](https://geektechnique.net/wp-content/uploads/2021/09/Imprimez-toutes-les-sous-sequences-en-diminuant-dabord-puis-en-augmentant.png)
Étant donné un entier positif N, la tâche consiste à imprimer toutes les sous-séquences du tableau de telle sorte que la sous-séquence soit d’abord décroissante puis croissante en sélectionnant plafond(N/2) éléments de 1 à N.
Exemples:
Saisir: N = 5
Sortir :
(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).
Ce sont les séquences valides de taille 3 qui diminue d’abord puis augmente.
Approcher: L’approche est basée sur l’utilisation de la fonction intégrée de python itertools.permutation pour générer toutes les sous-séquences de taille ceil(N/2). Suivez les étapes ci-dessous pour résoudre le problème :
- Initialiser un tableau arr[] et insérez tous les éléments de 1 à N.
- Initialiser une variable K comme plafond(N/2).
- Insérez toutes les sous-séquences dans le tableau « séquences” en utilisant la fonction intégrée appelée itertools.permutations(arr, k).
- Itérer dans le tableau séquences en utilisant la variable seq et effectuez les étapes suivantes :
- Vérifier si seq[1]> suite[0] ou seq[-1]< suite[-2] ou si le seq est croissante ou décroissante puis continuez sinon cette séquence ne satisfait pas la condition mentionnée ci-dessus.
- S’il y a plus d’un élément que seq[i]
- Si la seq ne suit aucun des points ci-dessus, puis imprimez le seq.
Vous trouverez ci-dessous la mise en œuvre de l’approche ci-dessus :
Python3
|
à partir de la cellule d’importation mathématique à partir d’itertools importer des permutations def ValidSubsequence(seq) : si (séquence[0] je = 0 tandis que i si seq[i]> suite[i + 1]: passe elif seq[i] j = je + 1 si (j != len(seq)-1) et (seq[j]> suite[j + 1]): retourner Faux i+= 1 retourner vrai N = 5 K = plafond(N / 2) arr = liste(plage (1, N + 1)) séquences = liste(permutations(arr, K)) pour les séquences en séquences : si ValidSubsequence(seq) : print(seq, end = » « ) |
Sortir:
(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)
Complexité temporelle : O(CNN/2 * plafond(N/2)! *N)
Espace auxiliaire : O(CNN/2 * plafond(N/2) !)
Attention lecteur ! N’arrêtez pas d’apprendre maintenant. Obtenez tous les concepts importants de DSA avec le Cours auto-rythmé DSA à un prix adapté aux étudiants et devenez prêt pour l’industrie. Pour compléter votre préparation de l’apprentissage d’une langue à DS Algo et bien d’autres, veuillez vous référer Cours complet de préparation aux entretiens.
Au cas où vous souhaiteriez assister cours en direct avec des experts, veuillez vous référer Cours en direct DSA pour les professionnels en activité et Programmation compétitive en direct pour les étudiants.
![Imprimez toutes les sous-séquences en diminuant d’abord puis en augmentant en sélectionnant N/2 éléments de [1, N]](https://geektechnique.net/wp-content/uploads/2021/09/Imprimez-toutes-les-sous-sequences-en-diminuant-dabord-puis-en-augmentant-75x75.png)
