仅包括非唯一元素 [英] Include non-unique elements only

问题描述

有人问了这个问题，但没有答案:此处.我阅读了评论并尝试以两种方式实施，但是还有更多我不理解的问题.

This question was asked but there are no answers: here. I read the comments and tried to implement in both ways, but there are more problems that I don't understand.

我首先尝试了一种不保持原始顺序的简单方法:

I first tried the easy way that doesn't keep original order:

list_repeated(L, Ds) :-
    msort(L, S),
    sorted_repeated(S, Ds).

sorted_repeated([], []).
sorted_repeated([X|Xs], Ds) :-
    first(Xs, X, Ds).

first([], _, []).
first([X|Xs], X, [X|Ds]) :-
    more(Xs, X, Ds).
first([X|Xs], Y, Ds) :-
    dif(X, Y),
    first(Xs, X, Ds).

more([], _, []).
more([X|Xs], X, Ds) :-
    more(Xs, X, Ds).
more([X|Xs], Y, Ds) :-
    dif(X, Y),
    first(Xs, X, Ds).

在对列表进行排序而又不删除重复项的情况下，使用first和more，如果该元素至少出现两次，则将其添加到第二个参数中，并跳过该元素的所有连续副本.

Once the list is sorted without removing duplicates, using first and more I add the element to the second argument if it occurs at least twice and skip all consecutive copies of the element.

这不能正常工作，因为如果有:

This is not working properly because if I have:

?- list_duplicates([b,a,a,a,b,b], Ds).

我得到的答案是[a,b]而不是[b,a]，而且我得到的答案也是; false.

I get answer [a,b] instead of [b,a] and also I get ; false after the answer.

我也尝试了另一种方法，但这不起作用，因为累加器是不可变的?

I also tried another way, but this doesn't work because the accumulator is immutable?

list_duplicates(L, Ds) :-
    ld_acc(L, [], Ds).

ld_acc([], _, []).
ld_acc([X|Xs], Acc, Ds) :-
    (   memberchk(X, Acc)
    ->  Ds = [X|Ds0],
        ld_acc(Xs, Acc, Ds0)
    ;   Acc1 = [X|Acc],
        ld_acc(Xs, Acc1, Ds)
    ).

这不起作用，因为当我检查某个元素是否是累加器的成员时，我仅删除每个元素的一次出现:如果我在第一个参数中具有相同元素的三倍，则剩下两个.如果我可以更改累加器中的元素，那么我可以在其上放置一个计数器吗?在第一个版本中，我使用了不同的状态first和more，但是在这里我必须将状态附加到累加器的元素上，这可能吗?

This cannot work because when I check that an element is member of accumulator I remove only one occurrence of each element: if I have three times the same element in the first argument, I am left with two. If I could change the element in the accumulator then I could maybe put a counter on it? In the first version I used different states, first and more, but here I have to attach state to the elements of the accumulator, is that possible?

推荐答案

追求纯洁

在Prolog中进行编程时，主要的吸引力是通用性，我们从纯亲戚中受益.

A plea for purity

When programming in Prolog, a major attraction is the generality we enjoy from pure relations.

这使我们可以在多个方向上使用我们的代码，并对我们的程序和答案进行声明性说明.

This lets us use our code in multiple directions, and reason declaratively over our programs and answers.

如果您将程序保持为纯，则可以享受这些好处.

You can enjoy these benefits if you keep your programs pure.

一如往常，在描述列表时，还应考虑使用 DCG表示法.有关更多信息，请参见 dcg 的问题.

As always when describing lists, also consider using DCG notation. See dcg for more information.

例如，要纯粹地描述重复项的列表，请考虑:

For example, to describe the list of duplicates in a pure way, consider:

list_duplicates([]) --> [].
list_duplicates([L|Ls]) -->
        list_duplicates_(Ls, L),
        list_duplicates(Ls).

list_duplicates_([], _) --> [].
list_duplicates_([L0|Ls], L) -->
        if_(L0=L, [L], []),
        list_duplicates_(Ls, L).

这使用 if_//3 来保留通用性 和 确定性(如果适用).

This uses if_//3 to retain generality and determinism (if applicable).

以下是一些示例查询和答案.我们从简单的地面案例开始:

Here are a few example queries and answers. We start with simple ground cases:

?- phrase(list_duplicates([a,b,c]), Ds).
Ds = [].

?- phrase(list_duplicates([a,b,a]), Ds).
Ds = [a].

即使是最不纯正的版本也能够正确处理这些情况.因此，稍微有趣一点:

Even the most impure version will be able to handle these situations correctly. So, slightly more interesting:

?- phrase(list_duplicates([a,b,X]), Ds).
X = a,
Ds = [a] ;
X = b,
Ds = [b] ;
Ds = [],
dif(X, b),
dif(X, a).

很好，不是吗?最后一部分说:Ds = []是解决方案，如果 X与b和a 不同.请注意，纯关系dif/2自动出现在这些残差目标中，并保留了该关系的一般性.

Pretty nice, isn't it? The last part says: Ds = [] is a solution if X is different from b and a. Note the pure relation dif/2 automatically appears in these residual goals and retains the relation's generality.

这是一个有两个变量的示例:

Here is an example with two variables:

?- phrase(list_duplicates([X,Y]), Ds).
X = Y,
Ds = [Y] ;
Ds = [],
dif(Y, X).

最后，考虑使用迭代加深对任意长度的列表进行枚举答案:

Finally, consider using iterative deepening to fairly enumerate answers for lists of arbitrary length:

?- length(Ls, _), phrase(list_duplicates(Ls), Ds).
Ls = Ds, Ds = [] ;
Ls = [_136],
Ds = [] ;
Ls = [_136, _136],
Ds = [_136] ;
Ls = [_156, _162],
Ds = [],
dif(_162, _156) ;
Ls = Ds, Ds = [_42, _42, _42] ;
Ls = [_174, _174, _186],
Ds = [_174],
dif(_186, _174) .

多次出现

这里是处理同一元素的任意多次出现的一种版本，当(且仅)当该元素出现时，会保留恰好一次出现至少两次:

Multiple occurrences

Here is a version that handles arbitrary many occurrences of the same element in such a way that exactly a single occurrence is retained if (and only if) the element occurs at least twice:

list_duplicates(Ls, Ds) :-
        phrase(list_duplicates(Ls, []), Ds).

list_duplicates([], _) --> [].
list_duplicates([L|Ls], Ds0) -->
        list_duplicates_(Ls, L, Ds0, Ds),
        list_duplicates(Ls, Ds).

list_duplicates_([], _, Ds, Ds) --> [].
list_duplicates_([L0|Ls], L, Ds0, Ds) -->
        if_(L0=L, new_duplicate(L0, Ds0, Ds1), {Ds0 = Ds1}),
        list_duplicates_(Ls, L, Ds1, Ds).

new_duplicate(E, Ds0, Ds) -->
        new_duplicate_(Ds0, E, Ds0, Ds).

new_duplicate_([], E, Ds0, [E|Ds0]) --> [E].
new_duplicate_([L|Ls], E, Ds0, Ds)  -->
        if_(L=E,
            { Ds0 = Ds },
            new_duplicate_(Ls, E, Ds0, Ds)).

@fatalize在注释中显示的查询现在产生:

The query shown by @fatalize in the comments now yields:

?- list_duplicates([a,a,a], Ls).
Ls = [a].

其他示例产生相同的结果.例如:

The other examples yield the same results. For instance:

?- list_duplicates([a,b,c], Ds).
Ds = [].

?- list_duplicates([a,b,a], Ds).
Ds = [a].

?- list_duplicates([a,b,X], Ds).
X = a,
Ds = [a] ;
X = b,
Ds = [b] ;
Ds = [],
dif(X, b),
dif(X, a).

?- list_duplicates([X,Y], Ds).
X = Y,
Ds = [Y] ;
Ds = [],
dif(Y, X).

我将案件?- list_duplicates(Ls, Ls).留作练习.

理想情况下，我们希望能够在所有方向上使用关系.

Ideally, we want to be able to use a relation in all directions.

例如，我们的程序应该能够回答以下问题:

For example, our program should be able to answer questions like:

如果列表的重复项是[a,b]， 会是什么样?

使用上面显示的版本，我们得到:

With the version shown above, we get:

?- list_duplicates(Ls, [a,b]).
nontermination

幸运的是，通过一个非常简单的更改就可以 answer 这样的问题！

Luckily, a very simple change allows as to answer such questions!

其中一项更改就是简单地写:

One such change is to simply write:

list_duplicates(Ls, Ds) :-
        length(Ls, _),
        phrase(list_duplicates(Ls, []), Ds).

显然，这在声明上是可允许的，因为Ls必须是列表. 操作上，这有助于我们公平地枚举列表.

This is obviously declaratively admissible, because Ls must be a list. Operationally, this helps us to enumerate lists in a fair way.

我们现在得到:

?- list_duplicates(Ls, [a,b]).
Ls = [a, a, b, b] ;
Ls = [a, b, a, b] ;
Ls = [a, b, b, a] ;
Ls = [a, a, a, b, b] ;
Ls = [a, a, b, a, b] ;
Ls = [a, a, b, b, a] ;
Ls = [a, a, b, b, b] ;
Ls = [a, a, b, b, _4632],
dif(_4632, b),
dif(_4632, a) ;
etc.

这是一个更简单的情况，仅使用一个元素:

Here is a simpler case, using only a single element:

?- list_duplicates(Ls, [a]).
Ls = [a, a] ;
Ls = [a, a, a] ;
Ls = [a, a, _3818],
dif(_3818, a) ;
Ls = [a, _3870, a],
dif(_3870, a) ;
Ls = [_4058, a, a],
dif(a, _4058),
dif(a, _4058) ;
Ls = [a, a, a, a] ;
etc.

也许更有趣:

没有重复的列表是什么样的?

What does a list without duplicates look like?

我们的程序答案:

?- list_duplicates(Ls, []).
Ls = [] ;
Ls = [_3240] ;
Ls = [_3758, _3764],
dif(_3764, _3758) ;
Ls = [_4164, _4170, _4176],
dif(_4176, _4164),
dif(_4176, _4170),
dif(_4170, _4164) .

因此，列表中所有元素都不同的特殊情况自然而然地作为我们实现的更一般关系的特殊情况存在.

Thus, the special case of a list where all elements are distinct naturally exists as a special case of the more general relation we have implemented.

我们可以使用此关系来生成答案(如上所示)，也可以测试 列表是否包含不同的元素:

We can use this relation to generate answers (as shown above), and also to test whether a list consists of distinct elements:

?- list_duplicates([a,b,c], []).
true.

?- list_duplicates([b,b], []).
false.

不幸的是，以下甚至更通用的查询仍然产生:

Unfortunately, the following even more general query still yields:

?- list_duplicates([b,b|_], []).
nontermination

从好的方面来说，如果列表的长度固定为 ，则在这种情况下，我们会得到:

On the plus side, if the length of the list is fixed, we get in such cases:

?- length(Ls, L), maplist(=(b), Ls),
   ( true ; list_duplicates(Ls, []) ).
Ls = [],
L = 0 ;
Ls = [],
L = 0 ;
Ls = [b],
L = 1 ;
Ls = [b],
L = 1 ;
Ls = [b, b],
L = 2 ;
Ls = [b, b, b],
L = 3 ;
Ls = [b, b, b, b],
L = 4 .

这表明该程序确实在这种情况下终止.请注意，答案现在太笼统.

This is some indication that the program indeed terminates in such cases. Note that the answers are of course now too general.

在高性能计算界众所周知，只要您的程序足够快，其正确性就几乎不值得考虑.

It is well known in high-performance computing circles that as long as your program is fast enough, its correctness is barely worth considering.

因此，关键问题当然是:我们怎样才能使其更快?

So, the key question is of course: How can we make this faster?

我离开这是一个非常容易的练习.在特定情况下加快此速度的一种方法是 first 检查给定列表是否被实例化.在这种情况下，您可以应用 ad 解决方案，该解决方案在更一般的情况下会严重失败，但是具有极大的好处，即快速！

I leave this is a very easy exercise. One way to make this faster in specific cases is to first check whether the given list is sufficiently instantiated. In that case, you can apply an ad hoc solution that fails terribly in more general cases, but has the extreme benefit that it is fast!

这篇关于仅包括非唯一元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！