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

标签 list prolog shuffle

我正在尝试使用 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).

正如您所看到的，有一个主要区别:

  • 在随机谓词中，他使用 member(X1,L2)，我使用L4 = [X1 | L2]，随机播放(其他，L4，L3)。如果我们有一个包含两个(或更多)相等元素的列表，member(X1,L2) 会给出错误。

  • 例如:arrange([1,2,3,4,1], List2, 1)。由于 member(1, L2) 已经为 true(第二次)，并且由于 L2 最初具有与 相同数量的元素>L1(但未实例化)具有 same_length，它不会在 L2 中添加另一个 1，当我们到达 int_0_100 我们收到一个元素未充分实例化错误。

这是我试图解决的问题，但似乎如果我不专门使用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个可能的元素X1之一L2 长度为 N。因此，人们可以告诉 Prolog“重做”其选择并选择另一个元素。

与

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

给出了三个可能的答案。

附录

为了正确排列列表，请使用 permutation/2正如 Guy Coder 所说，或者可以像这样继续:一个 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

每当在洗牌期间尝试进行违反该约束的统一时，统一就会失败，即 调用 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]].

关于list - 为什么我的 Prolog 练习没有尝试其他解决方案？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/68058584/

上一篇： flutter 'owner!._debugCurrentBuildTarget == this' : is not true. #87

下一篇：sql - 使用 SQL 查询根据连续值更新最小值

相关文章：

c# - 我应该更喜欢封闭式还是开放式列表<>系统？

python - 从整数列表中过滤最多 20 个值

list - lisp 列表中对子集的组合

json - 如何在 Prolog 中读取 JSON 文件

java - Android随机播放按钮位置onClick

java - 自己的Shuffle方法在Java中不起作用

python - 无限嵌套列表中到底发生了什么？

prolog - Prolog的模式匹配问题

prolog - 在 Prolog 中定义避免算术错误 is/2 的规则

java - 从数组中随机播放特定对象

©2024 IT工具网  联系我们