list - 为什么我的 Prolog 练习没有尝试其他解决方案？

Question

我正在 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).

我想问题是我实例化了一个 L4无法更改的列表 shuffle谓词。
现在我同事的解决方案:

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最初具有与 L1 相同数量的元素(但未实例化)使用 same_length ，它不会添加另一个 1在 L2当我们到达 int_0_100我们得到一个 element not enough instantiated错误。

这是我试图解决的问题，但似乎如果我不专门使用 member ，而不是我的解决方案，它只是给出了一个可能的答案。
你能解释一下为什么会这样，以及谓词 member 的问题的可能解决方案吗？给？
提前感谢您的时间，我希望一切都足够清楚:英语不是我的母语，问题本身很难解释。

Answer 1

如果查看“洗牌”并提取它们:

% 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 只是在第一个参数位置上颠倒了列表，而你同事的“shuffle”确实在洗牌:
请注意，必须在第二个参数位置使用正确长度的列表调用两个 shuffle 谓词:

?- 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 call 能够选择 N 个可能的元素之一 X1出单 L2长度为 N。所以可以告诉 Prolog“重做”它的选择并选择另一个元素。
与...一样

?- member(X,[1,2,3]).
X = 1 ;
X = 2 ;
X = 3.

这给出了三个可能的答案。
附录
为了正确排列列表，请使用 permutation/2正如 Guy Coder 所说，或者可能像这样继续:A shuffle_c使用给 member/2 的索引列表 0...N-1从原始列表中精确跟踪拾取元素一次，然后使用 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

每当在 shuffle 期间尝试违反该约束的统一时，统一都会失败，即
调用 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 之间”约束)(因为有一个现成的“排列”约束 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]].