Crossing sequences

Question

Crossing Sequences

Given a list of positive integers A, call it an increasing sequence if each element is greater than or equal to the previous one; and call it a decreasing sequence if each element is less than or equal to the previous one.

Some increasing sequences:

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

Some decreasing sequences:

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

A crossing sequence is a list that can be decomposed into two disjoint subsequences, one an increasing sequence and the other a decreasing sequence.

For example, the list:

[3,5,2,4,1]

is a crossing sequence, since it can be decomposed into:

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

where [3,4] is the increasing subsequence and [5,2,1] is the decreasing subsequence. We'll call such a pair of (increasing,decreasing) subsequences a decomposition of the crossing sequence.

The list:

[4,5,2,1,3]

is not a crossing sequence; there is no way to decompose it into an increasing and decreasing subsequence.

Your task is to write a program/function taking as input a list of positive integers; and if it is a crossing sequence, return the two lists in one of its decompositions; or some consistent "falsey" value if the list is not a crossing sequence.

This is code-golf; shortest program/function in each language is the winner.

Rules:

• Input is flexible.
• The usual loopholes are forbidden.
• If there are multiple valid ways to decompose the input, you may output one or all of them.
• Output formatting for the decomposition is flexible; but it must be unambiguous regarding the distinction between the two subsequences.
• You may use any consistent output value to indicate that the input is not a crossing sequence; so long as it is unambiguous compared to the output for any crossing sequence. You should specify the falsey value in your answer.

Test Cases:

Using False to indicate non-crossing sequences:

[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

Answer 1

Brachylog, 17 bytes

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

Try it online!

There's probably considerable room to golf this.

Answer 2

05AB1E, 15 14 13 bytes

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

Try it online or validate all test cases.

Explanation:

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)

Answer 3

Jelly, 12 bytes

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

Try it online!

Answer 4

JavaScript (ES6),  110 105  104 bytes

Returns either [[decreasing], [increasing]] or \$1\$ if there's no solution.

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

Try it online!

How?

We try all values of a bitmask \$n\$ between \$0\$ and \$2^L\$, where \$L\$ is the length of the input array.

At each iteration, we split the original array into two subsequences \$b[0]\$ (decreasing) and \$b[1]\$ (increasing), using each bit \$i\$ of \$n\$ to know where each value goes.

When a new value is added to a subsequence, we simultaneously make sure that it's not invalid by comparing it with the last value, popped from a copy of the subsequence. The direction of the inequality is always the same, but the operands are multiplied by either \$1\$ (if \$i=1\$) or \$-1\$ (if \$i=0\$):

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

We stop and return \$b\$ as soon as all values are passing, i.e. some() is falsy.

Answer 5

Haskell, 84 bytes

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

Returns a list of all valid (decreasing,increasing) pairs or the empty list if there's no such pair.

Try it online!

Answer 6

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)

Try it online!

The function prints all possible decompositions to the standard output. If there are no possible decompositions, nothing is printed.

Thanks to @Sriotchilism O'Zaic for improvement suggestions.

Answer 7

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

Try it online!