2

这个问题是在回答StackOverflow上的另一个问题时出现的，该问题是（概括一点）生成由有限元素集形成的所有序列，没有重复出现。

正如鲍里斯在评论中正确指出的那样，这个问题有许多现有的解决方案。但是，我对不使用累加器（即，与新选择的元素进行比较的已选择元素的列表）但使用dif/2语句的解决方案感兴趣。

为了说明，在我的以下程序中，我有 4 个元素，并且在 4 次递归调用之后，有几个div/2语句声明到目前为止已经选择的 4 个元素是成对不同的。由此可以推断，继续递归并寻找第五个元素是没有意义的，因为给定的div/2语句已经没有元素了。有没有办法将这些“知识”编码到程序中，使其不再循环？

:- use_module(library(apply)).
:- use_module(library(dif)).

sequences([]).
sequences([H|T]):-
  maplist(dif(H), T),
  between(1, 4, H),
  sequences(T).

当前的循环行为：

?- sequences(X).
X = [] ;
X = [1] ;
...
X = [4, 3, 1, 2] ;
X = [4, 3, 2, 1] ;
<LOOP>
4

2 回答 2

2

开始的小问题 - 名称：sequences/1建议一个序列列表（无论序列是什么），它应该是sequence/1.

你需要很多糟糕的 Prolog 系统：你需要更强的一致性。无论如何，我想。

我的即时反应（使用library(clpfd)！）不起作用，让我们看看为什么

?- length(Xs,N),Xs ins 1..4, all_distinct(Xs).

它和你的版本一样循环，这可以通过这个最好地看到：

?- length(Xs,N), false , Xs ins 1..4, all_distinct(Xs)。

所以已经length/2单独是错误的。也许我重申您的程序，并尝试确定您的程序没有终止的原因：

序列（[]）：-假。
序列（[H|T]）：-
  maplist(dif(H), T)，false 
  between(1, 4, H)，
   sequence(T)。

?- 序列（X），假。

我们最亲爱的声明式海报孩子maplist/2陷入了flagranti！好吧，也许我们不应该那么苛刻。毕竟，诚实的不终止谓词总是比不道德的不健全或不完整的破解更可取。

我们需要了解的是，这all_distinct/1需要知道列表的长度，并且所有域也必须存在。

sequence(Xs) :-
   sequence_aux(Xs, []).

sequence_aux([], _).
sequence_aux([X|Xs], Ys) :-
   X in 1..4,
   all_distinct([X|Ys]),
   sequence_aux(Xs, [X|Ys]).

 ?- sequence(X).

现在终止。

@mat 可能会注意到all_distinct([_])可能会被删除。或许还不止于此。

如果你不喜欢这个解决方案，因为它使用了一个额外的参数，你需要实现一个更安全的maplist/2.

fmaplist(C_1, Xs) :-
    freeze(Xs, fmaplist_aux(C_1, Xs)).

fmaplist_aux(_C_1, []).
fmaplist_aux(C_1, [X|Xs]) :-
   call(C_1, X),
   freeze(Xs, fmaplist_aux(C_1, Xs)).

现在您可以逐字使用您的原始程序。但我感觉不是很好。理解冻结程序中不终止的精确边界要困难得多。

顺便说一句：您可能会尝试在 SWI 中获取正确的变量名称以进行答案替换，因为_G772类似的编号不允许将答案重新粘贴回顶层 shell 并获得正确的结果。

于 2014-12-06T23:45:12.187 回答
2

不是一个真正的答案，但评论太长了：

您的问题是您希望将元素保留为事实。将它们放在一个列表中，您可以使用select/3它从该列表中取出一个元素。只要你把它们当作事实，这将比它需要的更迂回（我觉得）。一个排序列表（一个基数通常有一个顺序）是在 Prolog 中表示一个集合的完美方式。

编辑：

由于我仍然不确定我是否理解您的问题，以下是我认为您所问问题的实际答案：

不要使用dif/2，因为没有必要。相反，例如：

combination([], _).
combination([X|Xs], Set) :-
    select(X, Set, Set0),
    combination(Xs, Set0).

在这里，您必须使用setof/3或其他构建所有解决方案列表的谓词来构建您的初始集合。dif/2如果您可以使用列表并select/3从中提取，我看不出有必要。

但如果你真的坚持，我会这样做：

set_el(a).
set_el(b).
set_el(c).

set_el_combination(Combination) :-
    set_el_combination_1([], Combination).

set_el_combination_1(C, R) :-
    reverse(C, R).
set_el_combination_1(C0, C) :-
    maplist(dif(X), C0),
    set_el(X),
    set_el_combination_1([X|C0], C).

正如预期的那样，您会注意到解决方案的顺序不同（正确的字典顺序）。如果您想避免最后反转，您可以使用差异列表。我相信这也可以写成 DCG。

这些帮助有用？

于 2014-12-06T21:17:34.570 回答