Longest increasing subsequence: Difference between revisions

=={{header|jq}}==

{{works with|jq|1.4}}

Use the patience sorting method to find a longest (strictly) increasing subsequence.

'''Generic functions:'''

Recent versions of jq have functions that obviate the need for the two generic functions defined in this subsection.

<lang jq>def until(cond; update):

def _until:

if cond then . else (update | _until) end;

try _until catch if .== "break" then empty else . end;

# binary search for insertion point

def bsearch(target):

. as $in

| [0, length-1] # [low, high]

| until(.[0] > .[1];

.[0] as $low | .[1] as $high

| ($low + ($high - $low) / 2 | floor) as $mid

| if $in[$mid] >= target

then .[1] = $mid - 1

else .[0] = $mid + 1

end )

| .[0];</lang>

'''lis:'''

<lang jq>def lis:

# Helper function:

# given a stream, produce an array of the items in reverse order:

def reverse(stream): reduce stream as $i ([]; [$i] + .);

# put the items into increasing piles using the structure:

# NODE = {"val": value, "back": NODE}

reduce .[] as $x

( []; # array of NODE

# binary search for the appropriate pile

(map(.val) | bsearch($x)) as $i

| setpath([$i];

{"val": $x,

"back": (if $i > 0 then .[$i-1] else null end) })

)

| .[length - 1]

| reverse( recurse(.back) | .val ) ; </lang>

'''Example:'''

<lang jq>[0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15] | lis</lang>

{{out}}

<lang sh>$ jq -c -n -f lis.jq

[0,2,6,9,11,15]</lang>