如何收集随机数字序列的最大不重叠升序/降序前缀

Question

令 S = [x₁, x₂, ..., x_n] 为不同数字的随机序列。我们可以将 S 的 run 定义为：

• 序列 [x₁, x₂, ..., x_i]，对于 1 ≤ i ≤ n，使得 x₁ < x₂ < ... < x_i，且 i = n或 x_i > x_i+1；或
• 序列 [x_i, x_i-1, ..., x₁]，对于 1 ≤ i ≤ n，使得 x₁ > x₂ > ... > x_i，且 i = n 或 x_i < x_i+1。

谓词

runs/2

收集给定的不同数字序列的所有运行（对于连续的非重叠升序或降序前缀）。

% 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) ).

示例：

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

问题：如何扩展此代码以处理包含重复数字的序列：

• 仅修改谓词

  run/3

  和

  run_case/6

  （在后者中，可以更改元数）；
• 没有明确使用谓词

  reverse/2

  ;
• 无需多次处理同一项目；
• 仅使用尾递归谓词；和
• 谓词

  runs/2

  必须花费时间O(n)。

修改后，谓词

run/2

应按如下方式工作：

?- 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]].

动机：谓词

runs/2

有助于实现（自下而上）版本的自然归并排序，它需要时间 O(n) 对已经排序的序列（升序或降序）进行排序，并且极大减少对已经“几乎有序”的序列进行排序的执行时间。

Answer 1

我想出了这个（升序和降序保持不变）：

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) ).
   

样品运行：

?- 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]].