为什么我的 Prolog 练习没有尝试其他解决方案？
Why is my Prolog exercise not trying other solutions?
我正在尝试在 Prolog 中完成大学作业，我有一些问题。这是练习文本，我希望它是从意大利语翻译过来的：
Write a predicate arrange(List1, List2, K) that when given a List1 of at least two elements with only numbers between the range [0..100], is satisfied when List2 is a list obtained re-shuffling the elements of List1 in a way that the absolute difference between two consecutive elements is always greater than K.
示例：
?- arrange([1, 2, 3], L2, 0).
L2 = [1, 2, 3];
L2 = [1, 3, 2];
L2 = [2, 1, 3];
L2 = [2, 3, 1];
L2 = [3, 1, 2];
L2 = [3, 2, 1];
我尝试创建自己的解决方案，但它并没有给我所有可能的结果，相反，我只得到一个可能的结果。我也有一位同事的解决方案，它给出了所有结果，但它有一个问题我试图解决。
这是我的解决方案：
arrange(L1,L3,Diff):-
arrange(L1,[],L3,Diff).
arrange(L1,L2,L3,Diff):-
same_length(L1,L3),
shuffle(L1,L2,L3),
constraint(L3,Diff).
constraint([X1,X2],Diff):-
int_0_100(X1),
int_0_100(X2),
diff(X1,X2,Diff).
constraint([X1,X2|Others],Diff):-
int_0_100(X1),
int_0_100(X2),
diff(X1,X2,Diff),
constraint([X2|Others],Diff).
shuffle([],L2,L2).
shuffle([X1|Others],L2,L3):-
L4 = [X1 | L2],
shuffle(Others,L4,L3).
diff(X1,X2,Diff):-
X1 >= X2,
X1 - X2 > Diff.
diff(X1,X2,Diff):-
X1 < X2,
X2 - X1 > Diff.
int_0_100(N):-
N >= 0, N =< 100.
same_length([],[]).
same_length([_|Others1],[_|Others2]):-
same_length(Others1,Others2).
我想问题是我实例化了一个无法在 shuffle 谓词中更改的 L4 列表。
现在我同事的解决方案：
arrange(L1,L2,Diff):-
same_length(L1,L2),
shuffle(L1,L2),
constraint(L2,Diff).
constraint([X1,X2],Diff):-
int_0_100(X1),
int_0_100(X2),
diff(X1,X2,Diff).
constraint([X1,X2|Others],Diff):-
int_0_100(X1),
int_0_100(X2),
diff(X1,X2,Diff),
constraint([X2|Others],Diff).
shuffle([],_).
shuffle([X1|Others],L2):-
member(X1,L2),
shuffle(Others,L2).
diff(X1,X2,Diff):-
X1 >= X2,
X1 - X2 > Diff.
diff(X1,X2,Diff):-
X1 < X2,
X2 - X1 > Diff.
int_0_100(N):-
N >= 0, N =< 100.
same_length([],[]).
same_length([_|Others1],[_|Others2]):-
same_length(Others1,Others2).
如您所见，存在一个主要区别：
shuffle谓词中他用member(X1,L2)，我用L4 = [X1 | L2],shuffle(Other,L4,L3)。 member(X1,L2) 如果我们有一个包含两个（或更多）相等元素的列表，则会出错。
例如：arrange([1,2,3,4,1], List2, 1)。由于 member(1, L2) 已经是 true（第二次），并且由于 L2 最初具有与 same_length 相同数量的 L1 元素（但未实例化） ，它不会在 L2 中添加另一个 1，当我们到达 int_0_100 时，我们会收到 element not enough instantiated 错误。
这是我试图解决的问题，但似乎如果我不专门使用 member，而不是我的解决方案，它只会给出一个可能的答案。
你能解释一下为什么会这样吗，以及谓词 member 给出的问题的可能解决方案？
提前感谢您的宝贵时间，我希望一切都足够清楚：英语不是我的母语，问题本身很难解释。
如果查看“洗牌”并提取它们：
% Your shuffle:
shuffle_a(LI,LO) :-
shuffle_help(LI,[],LO).
shuffle_help([],L2,L2).
shuffle_help([X1|Other],L2,L3):-
shuffle_help(Other,[X1|L2],L3).
% Colleague's shuffle
shuffle_b([],_).
shuffle_b([X1|Others],L2):-
member(X1,L2),
shuffle_b(Others,L2).
然后你会看到你的洗牌只是在第一个参数位置反转列表，而你同事的“洗牌”确实是洗牌：
请注意，必须在第二个参数位置上使用正确长度的列表调用两个随机播放谓词：
?- shuffle_a([1,2,3],[S1,S2,S3]).
S1 = 3,
S2 = 2,
S3 = 1.
?- shuffle_b([1,2,3],[S1,S2,S3]).
S1 = 1, S2 = 2, S3 = 3 ;
S1 = 1, S2 = 3, S3 = 2 ;
S1 = 2, S2 = 1, S3 = 3 ;
S1 = 3, S2 = 1, S3 = 2 ;
S1 = 2, S2 = 3, S3 = 1 ;
S1 = 3, S2 = 2, S3 = 1 ;
false.
在shuffle_a/2中，任何时候都只有一种方法可以继续。
但是在 shuffle_b/2 中，member/2 调用能够从长度为 N 的列表 L2 中选择 N 个可能的元素 X1 之一。所以可以告诉 Prolog “重做”它的选择并选择另一个元素。
与
相同
?- member(X,[1,2,3]).
X = 1 ;
X = 2 ;
X = 3.
这给出了三个可能的答案。
附录
为了正确排列列表使用 permutation/2 正如 Guy Coder 所说或者可能像这样进行：使用索引列表 0...N 的 shuffle_c -1 给 member/2 以跟踪一次从原始列表中拾取元素，然后使用 nth0/3 统一第一个和第二个列表的元素：
shuffle_c(List,OtherList) :-
same_length(List,OtherList),
length(List,Length),
build_index_list(Length,IndexList),
shuffle_by_index(IndexList,[],List,OtherList).
build_index_list(Length,IndexList) :-
LengthAdj is Length-1,
bagof(Index,between(0,LengthAdj,Index),IndexList).
% shuffle_by_index(IndexList,UsedIndexList,List,OtherList).
shuffle_by_index(IndexList,UsedIndexList,_,_) :-
same_length(IndexList,UsedIndexList). % Success, shuffle_c will succeed with another answer
shuffle_by_index(IndexList,UsedIndexList,List,OtherList) :-
\+ same_length(IndexList,UsedIndexList), % Not done yet
member(ToIndex,IndexList), % Pick an "ToIndex" from IndexList
\+member(ToIndex,UsedIndexList), % ...that hasn't been used yet
length(UsedIndexList,FromIndex), % The "FromIndex" is just monotonically increasing
format("'to index' = ~d, 'from index' = ~d. The used index list is currently: ~q~n",[ToIndex,FromIndex,UsedIndexList]),
nth0(FromIndex,List,X), % Unifies List[FromIndex] and
nth0(ToIndex,OtherList,X), % OtherList[ToIndex]
shuffle_by_index(IndexList,[ToIndex|UsedIndexList],List,OtherList).
没有对原始列表中的相同元素进行特殊处理。
这实际上适用于任何未实例化的列表：
?- bagof(List,
shuffle_c(List,[1,2,3,4]),
Bag).
Bag = [[1,2,3,4],[1,2,4,3],[1,3,2,4],[1,3,4,2],
[1,4,2,3],[1,4,3,2],[2,1,3,4],[2,1,4,3],
[2,3,1,4],[2,3,4,1],[2,4,1,3],[2,4,3,1],
[3,1,2,4],[3,1,4,2],[3,2,1,4],[3,2,4,1],
[3,4,1,2],[3,4,2,1],[4,1,2,3],[4,1,3,2],
[4,2,1,3],[4,2,3,1],[4,3,1,2],[4,3,2,1]].
和
?- bagof(List,
shuffle_c([1,2,3,4],List),
Bag).
Bag = [[1,2,3,4],[1,2,4,3],[1,3,2,4],[1,4,2,3],
[1,3,4,2],[1,4,3,2],[2,1,3,4],[2,1,4,3],
[3,1,2,4],[4,1,2,3],[3,1,4,2],[4,1,3,2],
[2,3,1,4],[2,4,1,3],[3,2,1,4],[4,2,1,3],
[3,4,1,2],[4,3,1,2],[2,3,4,1],[2,4,3,1],
[3,2,4,1],[4,2,3,1],[3,4,2,1],[4,3,2,1]].
这甚至适用于“未实例化元素列表”。感觉就像洗牌孔。让我们看看如果两个孔完全相同会发生什么
?- bagof(List,shuffle_c([A,X,X,D],List),Bag).
Bag = [[A,X,X,D],[A,X,D,X],[A,X,X,D],[A,D,X,X],
[A,X,D,X],[A,D,X,X],[X,A,X,D],[X,A,D,X],
[X,A,X,D],[D,A,X,X],[X,A,D,X],[D,A,X,X],
[X,X,A,D],[X,D,A,X],[X,X,A,D],[D,X,A,X],
[X,D,A,X],[D,X,A,X],[X,X,D,A],[X,D,X,A],
[X,X,D,A],[D,X,X,A],[X,D,X,A],[D,X,X,A]].
这可以很容易地适应以解决原始问题。我们可以使用约束（即 libray(clpfd)）：我们在目标列表的后续元素 A、B 之间设置一个约束来强制执行约束：
abs(A - B) #> K
只要在洗牌期间尝试统一会违反该约束，统一就会失败，即
调用 nth0(ToIndex,OtherList,X) 将因仅从代码中看不出来的原因而失败：因为当前有效的约束否决了它。
在示踪剂中，你会看到
Call: (14) lists:nth0(1,[50,33,11,78],_40136) ? creep
Exit: (14) lists:nth0(1,[50,33,11,78],33) ? creep
Call: (14) lists:nth0(1,[50,_34818{clpfd = ...},_35522{clpfd = ...},_36226{clpfd = ...}],33) ? creep
Fail: (14) lists:nth0(1,[50,_34818{clpfd = ...},_35522{clpfd = ...},_36226{clpfd = ...}],33) ? creep
所以，新代码（这里不用担心“必须在 0 到 100 之间”的约束）（因为有现成的 'permutation' 约束 IIRC，可能可以做得更简单）：
:- use_module(library(clpfd)).
arrange(List,OtherList,K) :-
same_length(List,OtherList),
apply_constraints(OtherList,K), % <----- HERE
length(List,Length),
build_index_list(Length,IndexList),
shuffle_by_index(IndexList,[],List,OtherList).
% ADD THIS
apply_constraints([_],_).
apply_constraints([A,B|More],K) :-
abs(A - B) #> K,
apply_constraints([B|More],K).
% NOTHING BELOW HAS CHANGED
build_index_list(Length,IndexList) :-
LengthAdj is Length-1,
bagof(Index,between(0,LengthAdj,Index),IndexList).
% shuffle_by_index(IndexList,UsedIndexList,List,OtherList).
shuffle_by_index(IndexList,UsedIndexList,_,_) :-
same_length(IndexList,UsedIndexList). % Success, shuffle_c will succeed with another answer
shuffle_by_index(IndexList,UsedIndexList,List,OtherList) :-
\+ same_length(IndexList,UsedIndexList), % Not done yet
member(ToIndex,IndexList), % Pick an "ToIndex" from IndexList
\+member(ToIndex,UsedIndexList), % ...that hasn't been used yet
length(UsedIndexList,FromIndex), % The "FromIndex" is just monotonically increasing
format("'to index' = ~d, 'from index' = ~d. The used index list is currently: ~q~n",[ToIndex,FromIndex,UsedIndexList]),
nth0(FromIndex,List,X), % Unifies List[FromIndex] and
nth0(ToIndex,OtherList,X), % OtherList[ToIndex]
shuffle_by_index(IndexList,[ToIndex|UsedIndexList],List,OtherList).
等等：
?- bagof(List,arrange([50,33,11,78],List,20),Bag).
Bag = [[50,11,33,78],[50,78,33,11],[50,11,78,33],
[50,78,11,33],[11,50,78,33],[78,50,11,33],
[33,11,50,78],[33,78,50,11],[33,11,78,50],
[33,78,11,50],[11,33,78,50],[78,33,11,50]].
我正在尝试在 Prolog 中完成大学作业，我有一些问题。这是练习文本，我希望它是从意大利语翻译过来的：
Write a predicate
arrange(List1, List2, K)that when given aList1of at least two elements with only numbers between the range[0..100], is satisfied whenList2is a list obtained re-shuffling the elements ofList1in a way that the absolute difference between two consecutive elements is always greater thanK.
示例：
?- arrange([1, 2, 3], L2, 0).
L2 = [1, 2, 3];
L2 = [1, 3, 2];
L2 = [2, 1, 3];
L2 = [2, 3, 1];
L2 = [3, 1, 2];
L2 = [3, 2, 1];
我尝试创建自己的解决方案，但它并没有给我所有可能的结果，相反，我只得到一个可能的结果。我也有一位同事的解决方案，它给出了所有结果，但它有一个问题我试图解决。
这是我的解决方案：
arrange(L1,L3,Diff):-
arrange(L1,[],L3,Diff).
arrange(L1,L2,L3,Diff):-
same_length(L1,L3),
shuffle(L1,L2,L3),
constraint(L3,Diff).
constraint([X1,X2],Diff):-
int_0_100(X1),
int_0_100(X2),
diff(X1,X2,Diff).
constraint([X1,X2|Others],Diff):-
int_0_100(X1),
int_0_100(X2),
diff(X1,X2,Diff),
constraint([X2|Others],Diff).
shuffle([],L2,L2).
shuffle([X1|Others],L2,L3):-
L4 = [X1 | L2],
shuffle(Others,L4,L3).
diff(X1,X2,Diff):-
X1 >= X2,
X1 - X2 > Diff.
diff(X1,X2,Diff):-
X1 < X2,
X2 - X1 > Diff.
int_0_100(N):-
N >= 0, N =< 100.
same_length([],[]).
same_length([_|Others1],[_|Others2]):-
same_length(Others1,Others2).
我想问题是我实例化了一个无法在 shuffle 谓词中更改的 L4 列表。
现在我同事的解决方案：
arrange(L1,L2,Diff):-
same_length(L1,L2),
shuffle(L1,L2),
constraint(L2,Diff).
constraint([X1,X2],Diff):-
int_0_100(X1),
int_0_100(X2),
diff(X1,X2,Diff).
constraint([X1,X2|Others],Diff):-
int_0_100(X1),
int_0_100(X2),
diff(X1,X2,Diff),
constraint([X2|Others],Diff).
shuffle([],_).
shuffle([X1|Others],L2):-
member(X1,L2),
shuffle(Others,L2).
diff(X1,X2,Diff):-
X1 >= X2,
X1 - X2 > Diff.
diff(X1,X2,Diff):-
X1 < X2,
X2 - X1 > Diff.
int_0_100(N):-
N >= 0, N =< 100.
same_length([],[]).
same_length([_|Others1],[_|Others2]):-
same_length(Others1,Others2).
如您所见，存在一个主要区别：
shuffle谓词中他用
member(X1,L2)，我用L4 = [X1 | L2],shuffle(Other,L4,L3)。member(X1,L2)如果我们有一个包含两个（或更多）相等元素的列表，则会出错。例如：
arrange([1,2,3,4,1], List2, 1)。由于member(1, L2)已经是true（第二次），并且由于L2最初具有与same_length相同数量的L1元素（但未实例化） ，它不会在L2中添加另一个1，当我们到达int_0_100时，我们会收到element not enough instantiated错误。
这是我试图解决的问题，但似乎如果我不专门使用 member，而不是我的解决方案，它只会给出一个可能的答案。
你能解释一下为什么会这样吗，以及谓词 member 给出的问题的可能解决方案？
提前感谢您的宝贵时间，我希望一切都足够清楚：英语不是我的母语，问题本身很难解释。
如果查看“洗牌”并提取它们：
% Your shuffle:
shuffle_a(LI,LO) :-
shuffle_help(LI,[],LO).
shuffle_help([],L2,L2).
shuffle_help([X1|Other],L2,L3):-
shuffle_help(Other,[X1|L2],L3).
% Colleague's shuffle
shuffle_b([],_).
shuffle_b([X1|Others],L2):-
member(X1,L2),
shuffle_b(Others,L2).
然后你会看到你的洗牌只是在第一个参数位置反转列表，而你同事的“洗牌”确实是洗牌：
请注意，必须在第二个参数位置上使用正确长度的列表调用两个随机播放谓词：
?- shuffle_a([1,2,3],[S1,S2,S3]).
S1 = 3,
S2 = 2,
S3 = 1.
?- shuffle_b([1,2,3],[S1,S2,S3]).
S1 = 1, S2 = 2, S3 = 3 ;
S1 = 1, S2 = 3, S3 = 2 ;
S1 = 2, S2 = 1, S3 = 3 ;
S1 = 3, S2 = 1, S3 = 2 ;
S1 = 2, S2 = 3, S3 = 1 ;
S1 = 3, S2 = 2, S3 = 1 ;
false.
在shuffle_a/2中，任何时候都只有一种方法可以继续。
但是在 shuffle_b/2 中，member/2 调用能够从长度为 N 的列表 L2 中选择 N 个可能的元素 X1 之一。所以可以告诉 Prolog “重做”它的选择并选择另一个元素。
与
相同?- member(X,[1,2,3]).
X = 1 ;
X = 2 ;
X = 3.
这给出了三个可能的答案。
附录
为了正确排列列表使用 permutation/2 正如 Guy Coder 所说或者可能像这样进行：使用索引列表 0...N 的 shuffle_c -1 给 member/2 以跟踪一次从原始列表中拾取元素，然后使用 nth0/3 统一第一个和第二个列表的元素：
shuffle_c(List,OtherList) :-
same_length(List,OtherList),
length(List,Length),
build_index_list(Length,IndexList),
shuffle_by_index(IndexList,[],List,OtherList).
build_index_list(Length,IndexList) :-
LengthAdj is Length-1,
bagof(Index,between(0,LengthAdj,Index),IndexList).
% shuffle_by_index(IndexList,UsedIndexList,List,OtherList).
shuffle_by_index(IndexList,UsedIndexList,_,_) :-
same_length(IndexList,UsedIndexList). % Success, shuffle_c will succeed with another answer
shuffle_by_index(IndexList,UsedIndexList,List,OtherList) :-
\+ same_length(IndexList,UsedIndexList), % Not done yet
member(ToIndex,IndexList), % Pick an "ToIndex" from IndexList
\+member(ToIndex,UsedIndexList), % ...that hasn't been used yet
length(UsedIndexList,FromIndex), % The "FromIndex" is just monotonically increasing
format("'to index' = ~d, 'from index' = ~d. The used index list is currently: ~q~n",[ToIndex,FromIndex,UsedIndexList]),
nth0(FromIndex,List,X), % Unifies List[FromIndex] and
nth0(ToIndex,OtherList,X), % OtherList[ToIndex]
shuffle_by_index(IndexList,[ToIndex|UsedIndexList],List,OtherList).
没有对原始列表中的相同元素进行特殊处理。
这实际上适用于任何未实例化的列表：
?- bagof(List,
shuffle_c(List,[1,2,3,4]),
Bag).
Bag = [[1,2,3,4],[1,2,4,3],[1,3,2,4],[1,3,4,2],
[1,4,2,3],[1,4,3,2],[2,1,3,4],[2,1,4,3],
[2,3,1,4],[2,3,4,1],[2,4,1,3],[2,4,3,1],
[3,1,2,4],[3,1,4,2],[3,2,1,4],[3,2,4,1],
[3,4,1,2],[3,4,2,1],[4,1,2,3],[4,1,3,2],
[4,2,1,3],[4,2,3,1],[4,3,1,2],[4,3,2,1]].
和
?- bagof(List,
shuffle_c([1,2,3,4],List),
Bag).
Bag = [[1,2,3,4],[1,2,4,3],[1,3,2,4],[1,4,2,3],
[1,3,4,2],[1,4,3,2],[2,1,3,4],[2,1,4,3],
[3,1,2,4],[4,1,2,3],[3,1,4,2],[4,1,3,2],
[2,3,1,4],[2,4,1,3],[3,2,1,4],[4,2,1,3],
[3,4,1,2],[4,3,1,2],[2,3,4,1],[2,4,3,1],
[3,2,4,1],[4,2,3,1],[3,4,2,1],[4,3,2,1]].
这甚至适用于“未实例化元素列表”。感觉就像洗牌孔。让我们看看如果两个孔完全相同会发生什么
?- bagof(List,shuffle_c([A,X,X,D],List),Bag).
Bag = [[A,X,X,D],[A,X,D,X],[A,X,X,D],[A,D,X,X],
[A,X,D,X],[A,D,X,X],[X,A,X,D],[X,A,D,X],
[X,A,X,D],[D,A,X,X],[X,A,D,X],[D,A,X,X],
[X,X,A,D],[X,D,A,X],[X,X,A,D],[D,X,A,X],
[X,D,A,X],[D,X,A,X],[X,X,D,A],[X,D,X,A],
[X,X,D,A],[D,X,X,A],[X,D,X,A],[D,X,X,A]].
这可以很容易地适应以解决原始问题。我们可以使用约束（即 libray(clpfd)）：我们在目标列表的后续元素 A、B 之间设置一个约束来强制执行约束：
abs(A - B) #> K
只要在洗牌期间尝试统一会违反该约束，统一就会失败，即
调用 nth0(ToIndex,OtherList,X) 将因仅从代码中看不出来的原因而失败：因为当前有效的约束否决了它。
在示踪剂中，你会看到
Call: (14) lists:nth0(1,[50,33,11,78],_40136) ? creep
Exit: (14) lists:nth0(1,[50,33,11,78],33) ? creep
Call: (14) lists:nth0(1,[50,_34818{clpfd = ...},_35522{clpfd = ...},_36226{clpfd = ...}],33) ? creep
Fail: (14) lists:nth0(1,[50,_34818{clpfd = ...},_35522{clpfd = ...},_36226{clpfd = ...}],33) ? creep
所以，新代码（这里不用担心“必须在 0 到 100 之间”的约束）（因为有现成的 'permutation' 约束 IIRC，可能可以做得更简单）：
:- use_module(library(clpfd)).
arrange(List,OtherList,K) :-
same_length(List,OtherList),
apply_constraints(OtherList,K), % <----- HERE
length(List,Length),
build_index_list(Length,IndexList),
shuffle_by_index(IndexList,[],List,OtherList).
% ADD THIS
apply_constraints([_],_).
apply_constraints([A,B|More],K) :-
abs(A - B) #> K,
apply_constraints([B|More],K).
% NOTHING BELOW HAS CHANGED
build_index_list(Length,IndexList) :-
LengthAdj is Length-1,
bagof(Index,between(0,LengthAdj,Index),IndexList).
% shuffle_by_index(IndexList,UsedIndexList,List,OtherList).
shuffle_by_index(IndexList,UsedIndexList,_,_) :-
same_length(IndexList,UsedIndexList). % Success, shuffle_c will succeed with another answer
shuffle_by_index(IndexList,UsedIndexList,List,OtherList) :-
\+ same_length(IndexList,UsedIndexList), % Not done yet
member(ToIndex,IndexList), % Pick an "ToIndex" from IndexList
\+member(ToIndex,UsedIndexList), % ...that hasn't been used yet
length(UsedIndexList,FromIndex), % The "FromIndex" is just monotonically increasing
format("'to index' = ~d, 'from index' = ~d. The used index list is currently: ~q~n",[ToIndex,FromIndex,UsedIndexList]),
nth0(FromIndex,List,X), % Unifies List[FromIndex] and
nth0(ToIndex,OtherList,X), % OtherList[ToIndex]
shuffle_by_index(IndexList,[ToIndex|UsedIndexList],List,OtherList).
等等：
?- bagof(List,arrange([50,33,11,78],List,20),Bag).
Bag = [[50,11,33,78],[50,78,33,11],[50,11,78,33],
[50,78,11,33],[11,50,78,33],[78,50,11,33],
[33,11,50,78],[33,78,50,11],[33,11,78,50],
[33,78,11,50],[11,33,78,50],[78,33,11,50]].