ISO-Prolog受限模块环境下如何实现N元划分谓词

首先观察示例的规律：

• 所有拆分出的元素只能是N的非负整数次幂（即1、N、N²、N³...），不存在其他值
• 列表元素严格非递增，不会出现后面元素比前面大的情况
• 枚举顺序从大元素开始，优先选大的幂值，再逐步拆分为更小的幂值，最后到全1的情况

基于这个规律，用递归+辅助谓词实现即可，全程不需要用到call/2或multimap类功能，完全符合ISO-Prolog classic模式的语法约束：

1. 先实现一个求不超过上限的最大N次幂的工具谓词，用来确定当前位置能选的最大元素
2. 实现一个枚举合法元素的谓词，从当前最大允许值开始，每次除以N得到下一个更小的合法幂值，直到1为止
3. 写一个带剩余和、当前允许最大元素两个参数的辅助递归谓词，逐位生成列表元素：每次选一个合法的幂值，扣减对应剩余和，下一轮递归的最大允许值设为当前选中的元素（保证非递增），直到剩余和为0返回空列表
4. 主谓词直接调用辅助谓词，初始最大允许值设为目标总和即可

:- module(_,_,[classic,assertions,regtypes]).

% 主谓词：nary(基数N, 总和S, 划分结果P)
nary(N, S, P) :-
    S > 0,
    nary_helper(N, S, S, P).

% 辅助递归谓词：nary_helper(基数, 剩余和, 当前允许最大元素, 生成的列表)
nary_helper(_, 0, _, []).
nary_helper(N, Remain, MaxAllow, [K|Rest]) :-
    Remain > 0,
    min(MaxAllow, Remain, Upper),
    max_power(N, Upper, StartK),
    generate_k(N, StartK, K),
    NextRemain is Remain - K,
    nary_helper(N, NextRemain, K, Rest).

% 工具谓词：求两个数的较小值
min(A,B,A) :- A =< B.
min(A,B,B) :- B < A.

% 工具谓词：求不超过Upper的最大N的非负整数次幂
max_power(N, Upper, Res) :-
    max_power_acc(N, Upper, 1, Res).
max_power_acc(N, Upper, Cur, Res) :-
    Next is Cur * N,
    ( Next =< Upper ->
        max_power_acc(N, Upper, Next, Res)
    ;
        Res = Cur
    ).

% 工具谓词：从StartK开始，从大到小枚举所有合法的N次幂（每次除以N直到1）
generate_k(_, K, K) :- K >= 1.
generate_k(N, CurK, K) :-
    CurK > 1,
    NextK is CurK // N,
    generate_k(N, NextK, K).

代码加载后执行示例查询，输出和预期完全一致：

?- nary(3,9,P).
P = [9] ? ;
P = [3,3,3] ? ;
P = [3,3,1,1,1] ? ;
P = [3,1,1,1,1,1,1] ? ;
P = [1,1,1,1,1,1,1,1,1] ? ;
no

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