我怎样才能得到分区？

Question

我是 prolog 的新手，我想使用回溯在 prolog 中列出数字的 n 元分区。结果必须是这样的：

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

你有什么想法吗？非常感谢。

Answer 1

我想出了这个，其中 nary 分区是列表中的数字，或者它扩展 (spand)。然后 spand 进程获取第一个可被分区大小整除的数字，在其上拆分列表，插入分区，然后在那里完成或在回溯时扩展新构造的完整列表。

这是我获得您的回溯请求的唯一方法，而回溯不会撤消之前的展开并将 1,1,1 变回 3。我无法将列表拆分为第一个可整除的列表元素而不以更好的方式留下任何选择点，但可能有更好的方式。

spand(In, Psize, Out) :-
    once((append(Left, [Elem|Right], In),  % first divisible element, e.g. 3
          0 is Elem mod Psize)),
    
    length(Parts, Psize),    % make the partition list, e.g. [1,1,1]
    Pt is Elem / Psize,
    maplist(=(Pt), Parts),
    append(Left, Parts, Temp),
    
    ( append(Temp, Right, Out)    % choicepoint for backtracking
    ; append(Temp, Right, Out_),
      spand(Out_, Psize, Out)).

nary(Psize, Target, Parts) :-
    Parts = [Target]
    ;
    spand([Target], Psize, Parts).

例如

?- nary(3, 9, Parts).
Parts = [9] ;
Parts = [3, 3, 3] ;
Parts = [1, 1, 1, 3, 3] ;
Parts = [1, 1, 1, 1, 1, 1, 3] ;
Parts = [1, 1, 1, 1, 1, 1, 1, 1, 1] ;
false

例如

?- nary(2, 24, Parts).
Parts = [24] ;
Parts = [12, 12] ;
Parts = [6, 6, 12] ;
Parts = [3, 3, 6, 12] ;
Parts = [3, 3, 3, 3, 12] ;
Parts = [3, 3, 3, 3, 6, 6] ;
Parts = [3, 3, 3, 3, 3, 3, 6] ;
Parts = [3, 3, 3, 3, 3, 3, 3, 3] ;
false

您的示例太短，无法判断是 [6, 6, 12] -> [3, 3, 6, 12] 还是 [6, 6, 6, 6]。深度优先还是广度优先。

Answer 2

如何通过在 nary 中放置一个 returnPsize 的幂达到 Target 的函数来做同样的事情？因为对于您的代码，例如，如果您输入 nary(3,47,M) 它不会 return 任何东西。

我怎样才能得到分区？

How can I get partition?

prolog