1

几个星期以来,我一直在尝试自学 Prolog。现在,我正在尝试使用partition/3我想要使用的谓词从几个较小的整数中找到所有方法来生成一个大整数:

| ?- partition(4, [1, 2, 3], X).

X = [1, 1, 1, 1] ? ;
X = [1, 1, 2] ? ;
X = [1, 3] ? ;
X = [2, 2] ? ;
no

从而找到从 1、2 和 3 生成 4 的所有方法。像 [1, 2, 1] 和 [2, 1, 1] 这样的重复解决方案很好,但可能不难避免。这是我现在拥有的:

partition(N, _, []) :- N = 0.
partition(N, [], _) :- fail.

partition(N, [IH|IT], [OH|OT]) :-
  N =< 0, fail;
  N > IH, M is N-IH, OH = IH,
  partition(M, [IH|IT], OT).
% if the first input IH can be subtracted from N,
% do so into M and push IH into the output list [OH|OT]

partition(N, [_|IT], Output) :-
  N =< 0, fail;
  partition(N, IT, Output). 
% after trying the first input term, try the others

这个想法是 N 最终会变为零,并且得到它的减法将作为列表放在第三个参数中。第三和第四条规则只对正整数起作用,第二条规则说不要用完输入,第一条规则表示当 N 达到零时分区有效。问题是,我只得到:

| ?- partition(4, [1, 2, 3], X).

no

第一条和第二条规则对我来说很有意义,第三条和第四条似乎有问题,但我找不到它们有什么特别的问题。我认为OT当 M 变为零时,输出尾部可能不会被实例化,但第一条规则会解决这个问题。还是对 Prolog 的工作方式存在一些根本性的误解(这对我来说似乎经常发生)?

另外,N =< 0, fail;零件是多余的吗?它们似乎是多余的,但在我得到一些有用的东西之前我不能确定。

编辑:我正在使用 GNU Prolog。

4

1 回答 1

2

您在这里遇到一个问题,与Nto进行比较IH

partition(N, [IH|IT], [OH|OT]) :-
  N =< 0, fail;
  N > IH, [...]

应该是N >= IH

考虑你的例子partition(4, [1, 2, 3], X)

  1. 它匹配谓词 3,后者依次检查partition(3,[1,2,3],OT)
  2. partition(3,[1,2,3],OT)匹配第三个谓词,即检查partition(2,[1,2,3],OT).
  3. partition(2,[1,2,3],OT)匹配第三个谓词,即检查partition(1,[1,2,3],OT).
  4. partition(1,[1,2,3],OT)匹配第四个谓词,因为 1 > 1 failed。检查partition(1,[2,3],OT)
  5. partition(1,[2,3],OT)将第四个谓词匹配到最后,当列表为空时失败。
于 2012-02-11T07:18:48.010 回答