Séquences de croisement

Étant donné une liste d'entiers positifs A, appelez-la une séquence croissante si chaque élément est supérieur ou égal au précédent; et appelez-le une séquence décroissante si chaque élément est inférieur ou égal au précédent.

Quelques séquences croissantes:

[1,2,4,7]
[3,4,4,5]
[2,2,2]
[]

Quelques séquences décroissantes:

[7,4,2,1]
[5,4,4,3]
[2,2,2]
[]

Une séquence de croisement est une liste qui peut être décomposée en deux sous-séquences disjointes, l'une une séquence croissante et l'autre une séquence décroissante.

Par exemple, la liste:

[3,5,2,4,1]

est une séquence de croisement, car elle peut être décomposée en:

[3,    4  ]
[  5,2,  1]

où [3,4]est la sous-séquence croissante et [5,2,1]la sous-séquence décroissante. Nous appellerons une telle paire de sous- séquences (croissantes, décroissantes) une décomposition de la séquence de croisement.

La liste:

[4,5,2,1,3]

n'est pas une séquence de croisement; il n'y a aucun moyen de le décomposer en une sous-séquence croissante et décroissante.

Votre tâche consiste à écrire un programme / fonction en prenant en entrée une liste d'entiers positifs; et s'il s'agit d'une séquence de croisement, renvoyez les deux listes dans l'une de ses décompositions; ou une valeur "falsey" cohérente si la liste n'est pas une séquence de croisement.

C'est du code-golf ; le programme / fonction le plus court dans chaque langue est le gagnant.

Règles:

• L'entrée est flexible.
• Les failles habituelles sont interdites.
• S'il existe plusieurs façons valides de décomposer l'entrée, vous pouvez en sortir une ou toutes.
• Le formatage de sortie pour la décomposition est flexible; mais il doit être sans ambiguïté quant à la distinction entre les deux sous-séquences.
• Vous pouvez utiliser n'importe quelle valeur de sortie cohérente pour indiquer que l'entrée n'est pas une séquence de croisement; tant qu'il n'est pas ambigu par rapport à la sortie de toute séquence de croisement. Vous devez spécifier la valeur de falsey dans votre réponse.

Cas de test:

Utilisation Falsepour indiquer des séquences non croisées:

[3, 5, 2, 4, 1] => [3, 4], [5, 2, 1]
[3, 5, 2, 4, 4, 1, 1] => [3, 4, 4], [5, 2, 1, 1]

[7, 9, 8, 8, 6, 11] => [7, 8, 8, 11], [9, 6]
[7, 9, 8, 8, 6, 11] => [7, 9, 11], [8, 8, 6] # also valid
[7, 9, 8, 8, 6, 11] => [7, 8, 11], [9, 8, 6] # also valid

[7, 8, 9, 10, 20, 30] => [7, 8, 9, 20, 30], [10]
[7, 8, 9, 10, 20, 30] => [8, 9, 10, 20, 30], [7] # this is also valid

[5, 5, 5] => [5, 5, 5], []

[4, 5, 2, 1, 3] => False
[3, 4, 3, 4, 5, 2, 4] => False

05AB1E , 15 14 13 octets

2.Œ.ΔćRšεü@}W

Essayez-le en ligne ou validez tous les cas de test .

Explication:

2.Π                   # all partitions of the input in 2 subsequences
   .Δ                  # find the first partition such that the following gives 1
     ćRš               # reverse the first subsequence
        ε  }           # map each subsequence to
         ü@            # pairwise greater-than
            W          # minimum (1 if all 1s, 0 otherwise)

Gelée , 12 octets

ŒPżṚ$ṢNÞƭ€ƑƇ

Essayez-le en ligne!

JavaScript (ES6),  110 105  104 octets

[[decreasing], [increasing]]$1$

f=(a,n,b=[[],[]])=>a.some((v,i)=>[...x=b[i=n>>i&1]].pop()*(x.push(v),i-=!i)>v*i)?n>>a.length||f(a,-~n):b

Essayez-le en ligne!

Comment?

$n$$0$$2^L$$L$

$b[0]$$b[1]$$i$$n$

$1$$i=1$$-1$$i=0$

[...x = b[i = n >> i & 1]].pop() * (x.push(v), i -= !i) > v * i

$b$some()

Haskell, 84 octets

(([],[])#)
(d,i)#(a:b)=(#b)=<<[(d++[a],i)|all(a<=)d]++[(d,i++[a])|all(a>=)i]
p#_=[p]

Renvoie une liste de toutes les (decreasing,increasing)paires valides ou la liste vide s'il n'y en a pas.

Essayez-le en ligne!

Python 3 , 109 107 octets

def f(l,i=[],d=[]):
 if l:s,*r=l;i and s<i[-1]or f(r,i+[s],d);d and s>d[-1]or f(r,i,d+[s])
 else:print(i,d)

Essayez-le en ligne!

La fonction imprime toutes les décompositions possibles sur la sortie standard. S'il n'y a pas de décompositions possibles, rien n'est imprimé.

Merci à @Sriotchilism O'Zaic pour ses suggestions d'amélioration.

Brachylog , 17 octets

;Ṣzpᵐz{ℕˢ}ᵐ≤₁ʰ≥₁ᵗ

Essayez-le en ligne!

Il y a probablement beaucoup de place pour jouer au golf.

Python 2 , 147 octets

def f(a):
 for i in range(2**len(a)):
	x=[];y=[]
	for c in a:[x,y][i&1]+=[c];i/=2
	if x==sorted(x)and y[::-1]==sorted(y[::-1]):return x,y
 return 0

Essayez-le en ligne!