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

Question

Я пытался разбить данный список на два разных списка: Уникальный и Дубликат. Например, если у нас есть список [1, 1, 2, 3, 3, 4, 5] Я хочу, чтобы Уникальный список был [2, 4, 5] и Дубликат был [1, 3]. Я не хочу, чтобы все 1 в списке были в списке Дубликат. Мне просто нужно одно. код я прямо сейчас:

compareL([_|[]], Unique, Dup).  
compareL([X3,Y3 | Tail], [X3 | Unique], Dup) :- 
    X3 =\= Y3, 
    compareL([Y3 | Tail], Unique, Dup). 
compareL([X3,Y3 | Tail], Unique, [X3 | Dup]) :- 
    X3 = Y3, 
    skipDups(X3, Tail, Unique, Dup). 

skipDups(_, [], Unique, Dup). 
skipDups(X3,[Y3 | Tail], Unique, Dup) :- 
    X3 =\= Y3, 
    compareL([Y3 | Tail], Unique, Dup). 
skipDups(X3,[Y3 | Tail], Unique, Dup) :- 
    X3 = Y3, 
    skipDups(X3, Tail, Unique, Dup). 

Используя пример списка, приведенного выше, если я бегу compareL([1, 1, 2, 3, 3, 4, 5], Unique, Dup). я получаю:

Unique = [2, 4|_G1954], 
Dup = [1, 3|_G1948]. 

Я не могу понять, почему в конце обоих списках я нахожусь получение '_G1954' и '_G1948'. Любая помощь будет оценена по достоинству. Благодарю.

Answer 1

здесь есть решение, ключ взять/4, потребляющие все соответствующие ведущие позиции, что позволяет легко тестировать список ([_|_] матчей любого списка по крайней мере, 1 элемент)

compareL([], [], []). 
compareL([X|Xs], U, D) :- 
    ( take(X, Xs, [_|_], Ys) 
    -> compareL(Ys, U, B), D = [X|B] 
    ; compareL(Xs, A, D), U = [X|A] 
    ). 

take(X, [X|Xs], [X|R], Ys) :- 
    !, take(X, Xs, R, Ys). 
take(_, Ys, [], Ys). 

Answer 2

Вы можете написать что:

split_seq([], [], []). 

split_seq([H | T], L1_out, L2_out) :- 
    split_seq(T, L1, L2), 
    ( select(H, L1, L1_out) 
    -> ( member(H, L2) 
     -> L2_out = L2 
     ; L2_out = [H | L2]) 
    ; L1_out = [H | L1], 
     L2_out = L2). 

Answer 3

Мы можем сохранить logical-purity построив на if_/3, (=)/3 и tpartition/4!

list_uniqs_dups([],[],[]). 
list_uniqs_dups([X|Xs0],Us0,Ds0) :- 
    tpartition(=(X),Xs0,Es,Xs), 
    if_(Es=[], 
     Us0+Ds0=[X|Us]+Ds, 
     Ds0+Us0=[X|Ds]+Us), 
    list_uniqs_dups(Xs,Us,Ds). 

Вот запрос ОП дал:

?- list_uniqs_dups([1,1,2,3,3,4,5],Us,Ds). 
Ds = [1,3], Us = [2,4,5].     % succeeds deterministically 

OK! Как насчет следующих довольно общих запросов?

 
?- list_uniqs_dups([],Us,Ds). 
Ds = [], Us = []. 

?- list_uniqs_dups([A],Us,Ds). 
Ds = [], Us = [A]. 

?- list_uniqs_dups([A,B],Us,Ds). 
    Ds = [B], Us = [] ,  A=B 
; Ds = [] , Us = [A,B], dif(A,B). 

?- list_uniqs_dups([A,B,C],Us,Ds). 
    Ds = [C], Us = []  ,  A=B ,    B=C 
; Ds = [B], Us = [C] ,  A=B ,   dif(B,C) 
; Ds = [C], Us = [B] ,    A=C , dif(B,C) 
; Ds = [C], Us = [A] ,   dif(A,C),  B=C 
; Ds = [] , Us = [A,B,C], dif(A,B), dif(A,C), dif(B,C). 

Answer 4

Ответ с помощью (=)/3

list_uniqs_alldups(Es,Us,Ds) : 
    tpartition(list_uniqmember_t(Es),Es,Us,Ds). 

list_uniqmember_t(Es,X,T) :- 
    tfilter(=(X),Es,Xs), 
    =(Xs,[X],T). 

Примеры запросов:

?- list_uniqs_alldups([1,1,2,1,1,3,4,3],Us,Ds). 
Us = [2, 4], 
Ds = [1, 1, 1, 1, 3, 3]. 

?- list_uniqs_alldups([1,1,2,3,3,1,1,3,4,3],Us,Ds). 
Us = [2, 4], 
Ds = [1, 1, 3, 3, 1, 1, 3, 3]. 

?- list_uniqs_alldups([8,1,1,2,3,3,1,1,3,4,3],Us,Ds). 
Us = [8, 2, 4], 
Ds = [1, 1, 3, 3, 1, 1, 3, 3]. 

?- list_uniqs_alldups(X,Us,Ds). 
X = Us, Us = Ds, Ds = [] ; 
X = Us, Us = [_A], Ds = [] ; 
X = Ds, Us = [], Ds = [_A,_A] ; 
X = Ds, Us = [], Ds = [_A,_A,_A] ; 
... 

Для кодирования длин серий я использовал splitlistIfAdj/3.

list_rle(List,Rle) :- 
    splitlistIfAdj(dif,List,Rle0), 
    maplist(rle_length,Rle0,Rle). 

rle_length([H|T],RleLen) :- 
    length([H|T],L), 
    RleLen = L*H. 

Запрос:

?- list_rle([a,a,b,a,a,c,d,c],X). 
X = [2*a, 1*b, 2*a, 1*c, 1*d, 1*c]. 

Я не знаю, как это изменить так, что он работает в обоих направлениях.

Вы могли бы также сделать:

new_list_uniqs_alldups(List,Us,Ds):- 
    list_rle(List,Rle), 
    tpartition(singlelist_t,Rle,Us,Ds). 

singlelist_t(L,T) :- 
    L=N*_, 
    if_(N=1,T=true,T=false). 

Образец Q:

?- new_list_uniqs_alldups([1,1,2,1,1,3,4,1,1,7,8],U,D). 
U = [1*2, 1*3, 1*4, 1*7, 1*8], 
D = [2*1, 2*1, 2*1]. 

?- new_list_uniqs_alldups([7,7,7,2,1,1,3,4,1,1,7,8],U,D). 
U = [1*2, 1*3, 1*4, 1*7, 1*8], 
D = [3*7, 2*1, 2*1].