Программа Prolog для создания списка с первыми дублирующимися элементами - PullRequest
Новая
       29

Программа Prolog для создания списка с первыми дублирующимися элементами

0 голосов
/ 03 апреля 2019

Мне нужно реализовать эту функцию: 

cod_first(X, L, Lrem, Lfront).

Lfront содержит все копии X, которые находятся в начале L, включая X;Lrem - это список остальных элементов.

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

Ожидаемый вывод для программы примерно такой: 

?- cod_first(1, [1, 1, 2, 3], Lrem, Lfront) 
Lrem = [2, 3],
Lfront = [1, 1, 1];
false.

?- cod_first(1, [2, 3, 4], Lrem, Lfront)
Lrem = [2, 3, 4],
Lfront = [1];
false.

Обновление: я нашел эту функцию, которая упаковывает те же элементы в список: 

pack([], []).
pack([X], [[X]]).
pack([X, X| L], [[X| Xs]| R]) :-
    pack([X| L], [Xs| R]).
pack([X, Y| L], [[X]| R]) :-
    X \= Y,
    pack([Y| L], R).

Я думаю, что эта функцияможет быть адаптирована к тому, что я ищу, любая помощь?

1 Ответ

1 голос
/ 04 апреля 2019

Сначала давайте проверим код, который вы нашли!Я протестирую его, рассмотрев все списки, начиная с самого короткого: 

?- N=N, length(Xs,N), pack(Xs, Xss).
   N = 0, Xs = [], Xss = []
;  N = 1, Xs = [_A], Xss = [[_A]]
;  N = 2, Xs = [_A,_A], Xss = [[_A,_A]]
;  N = 3, Xs = [_A,_A,_A], Xss = [[_A,_A,_A]]
;  N = 4, Xs = [_A,_A,_A,_A], Xss = [[_A,_A,_A,_A]]
;  ...

Итак, согласно этому запросу, ваш код работает только для списков, в которых все элементы одинаковы.На самом деле, цель X \= Y отвечает за это.Лучше выразить неравенство с dif(X, Y).С этим небольшим изменением мы получаем: 

 ?- N=N, length(Xs,N), pack(Xs, Xss).
    N = 0, Xs = [], Xss = []
 ;  N = 1, Xs = [_A], Xss = [[_A]]
 ;  N = 2, Xs = [_A,_A], Xss = [[_A,_A]]
 ;  N = 2, Xs = [_A,_B], Xss = [[_A],[_B]], dif(_A,_B)
 ;  N = 3, Xs = [_A,_A,_A], Xss = [[_A,_A,_A]]
 ;  N = 3, Xs = [_A,_A,_B], Xss = [[_A,_A],[_B]], dif(_A,_B)
 ;  N = 3, Xs = [_A,_B,_B], Xss = [[_A],[_B,_B]],  dif(_A,_B)
 ;  N = 3, Xs = [_A,_B,_C], Xss = [[_A],[_B],[_C]], dif(_A,_B), dif(_B,_C)
 ;  N = 4, Xs = [_A,_A,_A,_A], Xss = [[_A,_A,_A,_A]]
 ;  ...

Теперь мы получаем действительно все решения.Давайте рассмотрим два ответа для N = 2.Первое говорит о том, что для элементов Xs все равны, Xss содержит только один элемент.Второй говорит, что когда элементы Xs различны, они отображаются в отдельных элементах Xss.Обратите внимание на dif(_A,_B), который гарантирует, что будут выбраны только разные термины.

Однако вас интересует только одно такое разбиение: 

cod_first(X, [], [], [X]).
cod_first(X, [X|Es], Lrem, [X|Xs]) :-
   cod_first(X, Es, Lrem, Xs).
cod_first(X, [E|Es], [E|Es], [X]) :-
   dif(X,E).

?- N=N, length(Xs, N), cod_first(X, Xs, Lrem, Lfront).
   N = 0, Xs = [], Lrem = [], Lfront = [X]
;  N = 1, Xs = [X], Lrem = [], Lfront = [X,X]
;  N = 1, Xs = [_A], Lrem = [_A], Lfront = [X], dif(_A,X)
;  N = 2, Xs = [X,X], Lrem = [], Lfront = [X,X,X]
;  N = 2, Xs = [X,_A], Lrem = [_A], Lfront = [X,X], dif(_A,X)
;  N = 2, Xs = [_A,_B], Lrem = [_A,_B], Lfront = [X], dif(_A,X)
;  N = 3, Xs = [X,X,X], Lrem = [], Lfront = [X,X,X,X]
;  N = 3, Xs = [X,X,_A], Lrem = [_A], Lfront = [X,X,X], dif(_A,X)
;  N = 3, Xs = [X,_A,_B], Lrem = [_A,_B], Lfront = [X,X], dif(_A,X)
;  N = 3, Xs = [_A,_B,_C], Lrem = [_A,_B,_C], Lfront = [X], dif(_A,X)
;  N = 4, Xs = [X,X,X,X], Lrem = [], Lfront = [X,X,X,X,X]
;  ...

Вот еще одна версия, которую я предпочитаюиспользование library(reif) доступно для SICStus и SWI . 

cod_first2(X, Es, Lrem, [X|Xs]) :-
   cod_first2i(Es, X, Xs, Lrem).

cod_first2i([], _, [], []).
cod_first2i([E|Es], X, Xs0, Ys) :-
   if_( E = X
      , ( Xs0 = [X|Xs], cod_first2i(Es, X, Xs, Ys) )
      , ( Xs0 = [], Ys = [E|Es] )
      ).

Это гораздо более эффективно, но дает точно такие же ответы.

...