使用Prolog对一个大整数进行分区

Question

我一直在试图自学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 

从而找出所有的方法，使4 1，第2和3.像[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。

Answer 1

您这里有一个问题，与N到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失败。检查partition(1,[2,3],OT)。
5. partition(1,[2,3],OT)会将第四个谓词匹配到最后，并在列表为空时失败。