LongestDecreasingSubsequence
The length of a longest decreasing subsequence.
✓ checked against that system · ! checked, with disagreements (hover a chip)Wikipedia
Longest increasing subsequenceWikidataQ4183855FindStatSt000760via IntegerComposition✓LongestDecreasingSubsequence(p)The length of a longest decreasing subsequence.Typed signatures
| Type | Package | Applies |
|---|---|---|
(composition | list<integer> | permutation) -> number | combinatorics | always |
Details
- Defined over
Permutationas an expression in_x, evaluated by compute-engine — the definition IS the implementation. - Takes a
Permutation, and also a bare list of integers: this reading compares entries with each other rather than with their positions, so it stands on any sequence. - The same fold with the comparison reversed — by Dilworth, the number of piles when the tops are kept decreasing.
Definition
Epsil, as the implementation runs it.
on Permutation, over _x
0 if Length(_x) < 1 else Count(Fold(Function(Apply(
Function(
Join(a, [b]) if k >
Count(a) else ReplaceAt(a, k, b),
k,
),
Count(Filter(
a,
Function(
t >
b,
t,
),
)) + 1,
), a, b), [], _x))on IntegerComposition, over _x
0 if Length(_x) < 1 else Count(Fold(Function(Apply(
Function(
Join(a, [b]) if m >
Count(a) else ReplaceAt(a, m, b),
m,
),
Count(Filter(
a,
Function(
t >
b,
t,
),
)) + 1,
), a, b), [], _x))