1

我想做的是从给定列表中生成元素的所有组合。例如：从 [a,b,c]，我可能想要：

[]
[a]
[b]
[c]
[a,a]
[a,b]
[a,c]
[b,a]
...

等等。也许有一个神奇的序言单线可以做到这一点。如果是这样，我很想听听。

但是，我的问题与其说是解决这个特定问题，不如说是请求有人为我解释 Prolog 搜索算法的一些微妙之处。

所以这是我首先解决上述问题的方法：

members([], _).
members([X|Xs], List) :-
  member(X,List),
  members(Xs, List).

这很好用，但会返回所有可能的结果，而且顺序不是很好：

[]
[a]
[a,a]
[a,a,a]

好的，这没问题。我真的只是想要所有组合达到一定的长度。所以我决定首先得到具有特定长度的那些：

membersWithLength(Members, List, Bound) :-
  L = Bound,
  length(Members, L),  members(Members, List).

这很好用，例如长度为 2：

[a,a]
[a,b]
[a,c]
...

等等。现在，我尝试使用 clpfd 来利用上述函数来使所有列表达到一定长度，但结果出错了：

:- use_module(library(clpfd)).


membersLessThan(Members, List, Bound) :-
  L in 0..Bound,  % I also tried L #=< Bound
  membersWithLength(Members, List, L).

一类的作品。找到正确的结果（长度小于 Bound 的列表）。但是在找到它们之后，它会不断循环搜索更多结果。例如长度 2：

[]
[a]
[b]
[c]
[a,a]
[a,b]
...
[c,c]
Hangs looking for more solutions.

我想这是我问题的核心。有人可以解释为什么（根据跟踪）prolog 继续检查越来越大的列表作为可能的解决方案，即使它们都注定要失败？有人可以告诉我是否有办法帮助 prolog 避免这个注定的旅程？

我最终使用下面的代码解决了这个问题，但是我很失望我无法弄清楚如何使用 clpfd 的整数约束来约束列表的大小。

membersLessThan_(Members, List, Bound) :-
  numlist(0,Bound,ZeroToBound),
  member(L, ZeroToBound),
  membersWithLength(Members, List, L).

以下是关于 SWISH 的所有相关代码：http: //swish.swi-prolog.org/p/allcombos.pl

4

1 回答 1

0

有了成员的原始实现，如果您想列举所有可以做的答案：

length(L, _), members(L, [a,b,c]).

这给了你答案：

L = [] ;
L = [a] ;
L = [b] ;
L = [c] ;
L = [a, a] ;
L = [a, b] ;
L = [a, c] ;
L = [b, a] ;
L = [b, b] ;
L = [b, c] ;
L = [c, a] ;
L = [c, b] ;
L = [c, c] ;
L = [a, a, a] ;
L = [a, a, b] ;
L = [a, a, c] ;
L = [a, b, a]

这是迭代深化的常用习语，它可以让你公平地列出所有答案。在这种情况下，我认为 clpfd 不能帮助你。

编辑

我在标题中看到您明确询问 CLPFD。您的代码不起作用的原因是当您这样做时

L in 0..Bound

您实际上并没有枚举这些值。对于下一个谓词，L 仍然是未绑定的并且带有约束。所以 membersWithLength 将不断循环尝试新的长度，一旦实例化了它的长度，它将看到约束失败并重试。您可以在以下示例中看到它：

L in 0..2, length(X, L)

像你的代码一样循环，因为长度一直在尝试。如果你想限制它，L必须在调用长度之前被实例化。您可以为此使用标签。下一个示例不循环：

L in 0..2, label([L]), length(X, L)
于 2016-12-15T17:02:38.750 回答