Prolog：将一个列表分成两个列表（唯一项/重复项）

Question

我一直在尝试将给定的列表分成两个不同的列表：Unique 和 Duplicate。例如，如果我们有列表 [1, 1, 2, 3, 3, 4, 5]，我想让 Unique 列表为 [2, 4, 5]，Duplicate 列表为 [1, 3]。我不希望列表中所有的 1 都在 Duplicate 列表中，我只需要其中一个。目前我拥有的代码如下：

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'。如有帮助，请谢谢。

- saviok

---

尝试使用 compareL([_], [], []) 替换 compareL([_|[]], Unique, Dup)。 - CapelliC

谢谢。这样就摆脱了“_G1954”和“_G1948”。但是当列表末尾有两个5时，它又会出现。不知道为什么？ - saviok

我认为您的谓词过于复杂......我会发布一份带有替代代码的答案。 - CapelliC

如果可以的话，那就太好了。谢谢！ - saviok

Answer 1

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

- user27815

---

不错的尝试！但是，我希望看到一种实现方式，使得所有三个查询都能在确定性情况下成功，而不会因为元逻辑内容破坏逻辑含义（当使用非常通用的术语时）。 - repeat

那三个查询都是没问题的！如果你仔细观察使用 [tag:swi-prolog] 这样的 [tag:prolog-toplevel] 获得的答案序列，你会发现它们看起来都像是 Us = ..., Ds = ... ; false.。尾随的 ; false. 表示 Prolog 不知道是否存在其他答案。现在，我们 知道在这些情况下是 没有 的。我假设这三个示例目标已经被充分实例化，因此如果我们使用适当的谓词定义，Prolog 也可以知道这一点。答案应该看起来像 Us = [...], Ds = [...].！另一方面，它仍应该保持逻辑纯粹。清楚吗？ - repeat

考虑查询?- list_uniqmember_t([1,2],X,T).。您之前的版本正确回答：X = 1，T = true; X = 2，T = true; T = false，dif(X, 2)，dif(X, 1)。而“新”版本的答案不完整，仅为X = 1，T = true。 - repeat

зұ»дјјдәҺ(!)/0гҖҒ(->)/2е’Ң(*->)/2иҝҷж ·зҡ„Prologжһ„йҖ пјҢеҫҲе®№жҳ“з ҙеқҸд»Јз ҒпјҒжҲ‘дёҚжғіе‘ҠиҜүдҪ пјҢдҪҶдҪ еҲҡеҲҡз ҙеқҸдәҶдҪ зҡ„д»Јз Ғ... - repeat

请查看此答案中的 list_RLE/2！http://stackoverflow.com/a/33180378/4609915 - repeat

Answer 2

我们可以通过基于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

好的！那么下面的一些相当通用的查询怎么样？

- 是否有空列表的不同项和重复项？
Ds = []，Us = []。
- 是否有只有一个元素的列表的不同项和重复项？
Ds = []，Us = [A]。
- 是否有只有两个元素的列表的不同项和重复项？
  Ds = [B]，Us = []，     A=B
; Ds = [] ，Us = [A,B]， dif(A,B)。
- 是否有只有三个元素的列表的不同项和重复项？
  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)。

- repeat

---

我们需要一个通用的缩进规则，适用于跨越多行的 if_/3。 - false

@false。没错！我也不喜欢 X+Y=A+B 这种写法。 - repeat

Answer 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).

- CapelliC

---

不使用 -> 是可能的吗？ - saviok

compareL([X|Xs], U, D) :- take(X, Xs, [_|_], Ys), !, compareL(Ys, U, B), D = [X|B] ; compareL(Xs, A, D), U = [X|A]. 这个代码是可以实现的，但有些繁琐。 - CapelliC

Answer 4

你可以写成这样：

您可以这样编写：

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).

- joel76