Kreuzungssequenzen

ANennen Sie eine Liste positiver Ganzzahlen eine aufsteigende Folge, wenn jedes Element größer oder gleich dem vorherigen ist. und nenne es eine abnehmende Sequenz, wenn jedes Element kleiner oder gleich dem vorherigen ist.

Einige zunehmende Sequenzen:

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

Einige abnehmende Sequenzen:

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

Eine Kreuzungssequenz ist eine Liste, die in zwei disjunkte Teilsequenzen zerlegt werden kann, eine eine zunehmende Sequenz und die andere eine abnehmende Sequenz.

Zum Beispiel die Liste:

[3,5,2,4,1]

ist eine Kreuzungssequenz, da sie zerlegt werden kann in:

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

wo [3,4]ist die zunehmende Teilsequenz und [5,2,1]ist die abnehmende Teilsequenz. Wir werden ein solches Paar von (zunehmenden, abnehmenden) Teilsequenzen eine Zerlegung der Kreuzungssequenz nennen.

Die Liste:

[4,5,2,1,3]

ist keine Kreuzungssequenz; Es gibt keine Möglichkeit, es in eine zunehmende und abnehmende Teilfolge zu zerlegen.

Ihre Aufgabe ist es, ein Programm / eine Funktion zu schreiben, die eine Liste positiver Ganzzahlen als Eingabe verwendet. und wenn es sich um eine Kreuzungssequenz handelt, geben Sie die beiden Listen in einer ihrer Zerlegungen zurück; oder ein konsistenter "Falsey" -Wert, wenn die Liste keine Kreuzungssequenz ist.

Das ist Code-Golf ; Das kürzeste Programm / die kürzeste Funktion in jeder Sprache ist der Gewinner.

Regeln:

• Die Eingabe ist flexibel.
• Die üblichen Lücken sind verboten.
• Wenn es mehrere gültige Möglichkeiten gibt, die Eingabe zu zerlegen, können Sie eine oder alle ausgeben.
• Die Ausgabeformatierung für die Zerlegung ist flexibel. es muss jedoch hinsichtlich der Unterscheidung zwischen den beiden Teilsequenzen eindeutig sein.
• Sie können einen beliebigen konsistenten Ausgabewert verwenden, um anzuzeigen, dass die Eingabe keine Kreuzungssequenz ist. solange es im Vergleich zur Ausgabe für eine Kreuzungssequenz eindeutig ist. Sie sollten den Falsey-Wert in Ihrer Antwort angeben.

Testfälle:

Verwenden False, um nicht kreuzende Sequenzen anzuzeigen:

[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 Bytes

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

Probieren Sie es online aus oder validieren Sie alle Testfälle .

Erläuterung:

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)

Gelee , 12 Bytes

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

Probieren Sie es online aus!

JavaScript (ES6),  110 105  104 Byte

[[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

Probieren Sie es online aus!

Wie?

$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 Bytes

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

Gibt eine Liste aller gültigen (decreasing,increasing)Paare oder die leere Liste zurück, wenn es kein solches Paar gibt.

Probieren Sie es online aus!

Python 3 , 109 107 Bytes

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)

Probieren Sie es online aus!

Die Funktion druckt alle möglichen Zerlegungen in die Standardausgabe. Wenn keine möglichen Zerlegungen möglich sind, wird nichts gedruckt.

Vielen Dank an @Sriotchilism O'Zaic für Verbesserungsvorschläge.

Brachylog , 17 Bytes

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

Probieren Sie es online aus!

Es gibt wahrscheinlich viel Platz zum Golfen.

Python 2 , 147 Bytes

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

Probieren Sie es online aus!