4

我一直在尝试将给定列表拆分为两个不同的列表：唯一列表和重复列表。例如，如果我们有一个列表，[1, 1, 2, 3, 3, 4, 5]我希望 Unique list 是[2, 4, 5]并且 Duplicate 是[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'。任何帮助，将不胜感激。谢谢。

4

4 回答 4

5

我们可以通过在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).

这是OP给出的查询：

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

好的！以下非常一般的查询怎么样？

?- list_uniqs_dups([],Us,Ds)。
Ds = []，我们 = []。

?- list_uniqs_dups([A],Us,Ds)。
Ds = []，我们 = [A]。

?- list_uniqs_dups([A,B],Us,Ds)。
  Ds = [B]，我们 = []，A=B
; Ds = []，Us = [A，B]，差异（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)。
于 2015-10-04T16:41:07.643 回答
5

回答使用(=)/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).

样品问：

 ?- 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].
于 2015-10-09T19:31:49.653 回答
3

这是一个解决方案，关键是 take/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).
于 2013-04-06T16:12:37.797 回答
3

你可以这样写：

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).
于 2013-04-06T16:34:21.267 回答