如何通过使用dif/2来防止生成的序列中出现重复？

Question

在回答another question on 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> 

Answer 1

^{微小的问题入手—名称：sequences/1暗示序列的列表（任何一个序列），它应该是相当sequence/1。}

您需要相当多的Prolog系统：您要求更高的一致性。我认为，不惜任何代价。

我立即reactio（使用library(clpfd)！）不工作，让我们来看看为什么

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

它循环一样多，你的版本，可以用这个failure-slice可最好地看到：

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

所以已经有length/2一个人是错的。也许我再次向你的程序，并尝试找出为什么你的程序不会终止：

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

?- sequences(X), false. 

我们最亲爱的声明海报孩子maplist/2因·弗拉格兰蒂陷入！好的，也许我们不应该那么苛刻。毕竟，一个谓词的诚实不终止总是比一个不合理的不完整或不完整的黑客更可取。

我们需要了解的是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般的编号不允许一个答案重新粘贴到顶层外壳，并得到正确的结果。

Answer 2

不是一个真正的答案，但过长的注释：

你的问题是，你要保持你的元素的事实。把它们放在一个列表中，你可以使用select/3从列表中取出一个元素。只要你把它们作为事实，这将会比它需要的更多（我感觉）。有序列表（通常是红衣主教有一个命令）是在Prolog中表示集合的最佳方式。

编辑：

因为我仍然不知道如果我明白你的问题，这里是真正的答案，我想你问的问题：

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

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

在这里，你将不得不使用建立您的setof/3初始设置，或者建立所有解决方案的列表另一个谓词。如果您可以使用列表并从中选择select/3，我无法看到需要dif/2。

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

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。

这有帮助吗？