sortingprologmergesorttail-recursion# How to collect maximal non-overlapping ascending/descending prefixes of a random sequence of numbers

Let S = [x_{1}, x_{2}, ..., x_{n}] be a random sequence of distinct numbers. We can define a **run** of S as:

- a sequence
**[x**, for 1 ≤ i ≤ n, such that x_{1}, x_{2}, ..., x_{i}]_{1}< x_{2}< ... < x_{i}, and i = n or x_{i}> x_{i+1}; or - a sequence
**[x**, for 1 ≤ i ≤ n, such that x_{i}, x_{i-1}, ..., x_{1}]_{1}> x_{2}> ... > x_{i}, and i = n or x_{i}< x_{i+1}.

The predicate `runs/2`

collects all runs of a given sequence of distinct numbers (for successive non-overlapping ascending or descending prefixes).

```
% runs(+Sequence, -Runs)
runs([], []).
runs([X|Xs], [Run|Runs]) :-
run(Xs, X, Run, Rest),
runs(Rest, Runs).
run([], X, [X], []).
run([X1|Xs], X0, Run, Rest) :-
compare(Order, X0, X1),
run_case(Order, X0, X1, Xs, Run, Rest).
run_case(<, X0, X1, Xs, [X0|Run], Rest) :-
ascending(Xs, X1, Run, Rest).
run_case(>, X0, X1, Xs, Run, Rest) :-
descending(Xs, X1, [X0], Run, Rest).
% for an ascending prefix, the run is built up as a QUEUE
ascending([], X0, [X0], []).
ascending([X1|Xs], X0, [X0|Run0], Rest) :-
( X0 @> X1
-> Run0 = [],
Rest = [X1|Xs]
; ascending(Xs, X1, Run0, Rest) ).
% for a descending prefix, the run is built up as a STACK
descending([], X0, Run, [X0|Run], []).
descending([X1|Xs], X0, Run0, Run, Rest) :-
( X0 @< X1
-> Run = [X0|Run0],
Rest = [X1|Xs]
; descending(Xs, X1, [X0|Run0], Run, Rest) ).
```

Example:

```
?- runs([1, 2, 9, 8, 5, 3, 7, 6, 4, 0], R).
R = [[1, 2, 9], [3, 5, 8], [0, 4, 6, 7]].
```

**PROBLEM**: How to extend this code to deal with sequences containing **repeating** numbers:

- modifying only the predicates
`run/3`

and`run_case/6`

(in the latter, the arity can be changed); - without explicitly using the predicate
`reverse/2`

; - without processing the same item more than once;
- using only tail-recursive predicates; and
- the predicate
`runs/2`

must take time O(n).

After the modifications, the predicate `run/2`

should work as follows:

```
?- runs([5, 5, 3, 2, 2, 4, 4, 7, 6, 6, 1, 7, 8, 8, 9], Runs).
Runs = [[2, 2, 3, 5, 5], [4, 4, 7], [1, 6, 6], [7, 8, 8, 9]].
```

**MOTIVATION**: The predicate `runs/2`

helps to implement a (bottom-up) version of **natural merge sort** that takes time O(n) to sort sequences that are already sorted (ascending or descending), as well as greatly reducing the execution time to sort sequences that are already "almost ordered".

Solution

I came up with this (ascending and descending remain the same):

```
runs([], []).
runs([X|Xs], [Run|Runs]) :-
run(Xs, X, [X|Tail]-Tail, Run, Rest),
runs(Rest, Runs).
run([], _, Run-[], Run, []).
run([X1|Xs], X0, LInit-Tail, Run, Rest):-
compare(Order, X0, X1),
run_case(Order, X1, LInit-Tail, Xs, Run, Rest).
run_case(=, X1, LInit-[X1|Tail], Xs, Run, Rest) :-
run(Xs, X1, LInit-Tail, Run, Rest).
run_case(<, X1, LInit-Run, Xs, LInit, Rest) :-
ascending(Xs, X1, Run, Rest).
run_case(>, X1, LInit-[], Xs, Run, Rest) :-
descending(Xs, X1, LInit, Run, Rest).
% for an ascending prefix, the run is built up as a QUEUE
ascending([], X0, [X0], []).
ascending([X1|Xs], X0, [X0|Run0], Rest) :-
( X0 @> X1
-> Run0 = [],
Rest = [X1|Xs]
; ascending(Xs, X1, Run0, Rest) ).
% for a descending prefix, the run is built up as a STACK
descending([], X0, Run, [X0|Run], []).
descending([X1|Xs], X0, Run0, Run, Rest) :-
( X0 @< X1
-> Run = [X0|Run0],
Rest = [X1|Xs]
; descending(Xs, X1, [X0|Run0], Run, Rest) ).
```

Sample runs:

```
?- runs([1, 2, 9, 8, 5, 3, 7, 6, 4, 0], R).
R = [[1, 2, 9], [3, 5, 8], [0, 4, 6, 7]].
?- runs([5, 5, 3, 2, 2, 4, 4, 7, 6, 6, 1, 7, 8, 8, 9], Runs).
Runs = [[2, 2, 3, 5, 5], [4, 4, 7], [1, 6, 6], [7, 8, 8, 9]].
```

- Excel sort numbers with letter prefix
- How do I sort a list of objects based on an attribute of the objects?
- UNIX shell: sort a string by word length and by ASCII order ignoring case
- Custom Sort Using 4 Columns
- How can I reverse a Java 8 stream and generate a decrementing IntStream of values?
- Python sorted function key
- Specific character count in string
- MongoDB Search and Sort, with Number of Matches and Exact Match
- dplyr arrange() function sort by missing values
- Sort NSArray of NSDictionary objects in Swift
- Sort array of values by their levenshtein distance from a comparison string
- WooCommerce catalog order by a custom range based on metadata
- Why std::sort actually moves the content of std::string?
- Sort array of objects by string property value
- Pandas: Sort a dataframe based on multiple columns
- Excel Sorting and filtering breaking formulas
- Why is Merge Sort Performance LINEAR?
- Find four,whose sum equals to target
- Spring MongoDB query sorting
- JTable, RowSorter, getSelectedRow data
- Jquery DataTable update `data-sort` attribute at runtime not affecting sort
- Efficient way to insert a number into a sorted array of numbers?
- using lodash .groupBy. how to add your own keys for grouped output?
- How do I sort array of pairs based on the greater value in first or second
- Why does `min()` call a key function when there is only one item in the Iterable?
- Sort nested javascript array / object
- Resort one array based on another array
- Find max product using divide and conqure in O(n) time
- How do I sort specific elements in list in javascript?
- Sort array on key value