如何让Prolog的subseq/2谓词输出符合预期的子序列顺序？

需求说明 #

需要实现subseq(-, +)谓词，满足：

• 两个参数均为列表
• 第一个参数是第二个参数移除零个或多个元素后得到的子序列
• 查询subseq(X, [a, b, c])时，输出必须从最长子序列到最短子序列，顺序如下：

?- subseq(X, [a, b, c]).
X = [a, b, c] ;
X = [a, b] ;
X = [a, c] ;
X = [a] ;
X = [b, c] ;
X = [b] ;
X = [c] ;
X = [].

当前实现的问题 #

你的现有代码：

subseq([], []).
subseq([], [_|_]).
subseq([X|XS], [X|YS]) :- subseq(XS, YS).
subseq([X|XS], [_|YS]) :- subseq([X|XS], YS).

会优先推导空子序列，再逐步构建长序列，导致输出顺序是从短到长，和预期不符。

修正方案 #

要反转输出顺序，核心是让长序列的推导分支被优先调用，同时调整规则的顺序。修改后的代码如下：

% 1. 首先匹配完整列表（最长子序列）
subseq(Full, Full).
% 2. 跳过当前元素，递归找剩余列表的子序列（先生成去掉末尾元素的长序列）
subseq(Sub, [_|Rest]) :- subseq(Sub, Rest).
% 3. 保留当前元素，递归找剩余列表的子序列（生成包含当前元素但缩短的子序列）
subseq([Head|SubRest], [Head|ListRest]) :- subseq(SubRest, ListRest).
% 4. 最后匹配空子序列（确保它是最后一个输出）
subseq([], [_|_]).

规则执行逻辑 #

1. subseq(Full, Full)：直接返回原列表作为第一个结果，这是最长的子序列。
2. subseq(Sub, [_|Rest])：跳过当前元素，递归处理剩余列表。比如处理[a,b,c]时，先跳过c得到[a,b]，再跳过b得到[a]，跳过a得到[]——这条规则会和第三条规则配合，优先走完长分支。
3. subseq([Head|SubRest], [Head|ListRest])：保留当前元素，对剩余列表递归找子序列。比如处理[a,b,c]时，保留a后，对[b,c]找子序列，得到[a,c]、[a]等。
4. subseq([], [_|_])：最后触发空子序列的匹配，确保它是最后一个输出。

验证结果 #

运行修改后的代码，查询subseq(X, [a, b, c])会得到完全符合预期的输出顺序：

?- subseq(X, [a, b, c]).
X = [a, b, c] ;
X = [a, b] ;
X = [a, c] ;
X = [a] ;
X = [b, c] ;
X = [b] ;
X = [c] ;
X = [] ;
false.

内容的提问来源于stack exchange，提问作者Syed