Я пытаюсь получить задание в колледже по Прологу, и у меня есть несколько вопросов. Это текст упражнения, надеюсь, вам ясно, что я перевожу с итальянского:

Напишите предикат arrange(List1, List2, K) , который при задании List1 по крайней мере двух элементов с только числами между диапазонами [0..100] удовлетворяется, когда List2 получается список, перетасовывающий элементы List1 таким образом, чтобы абсолютная разница между двумя последовательными элементами всегда была больше, чем 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).
 

I guess that the problem is that I instantiate a L4 list that can’t change in the shuffle predicate.

Now my colleague’s solution:

 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],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 ?

Заранее спасибо за ваше время, я надеюсь, что все достаточно ясно: английский не мой родной язык, и сама проблема довольно сложна для объяснения.

Если посмотреть на «перетасовки» и извлечь их:

 % 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_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. Таким образом, можно сказать Прологу «повторить» свой выбор и выбрать другой элемент.

Так же, как

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

что дает три возможных ответа.

Дополнение

Чтобы правильно переставить список, используйте перестановку/2, как говорит кодер, или, может быть, поступите так: A shuffle_c , который использует список индексов 0…N-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» здесь) (вероятно, это можно сделать еще проще, так как есть готовое ограничение «перестановка» 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]].