以紧凑形式实现列表的分配 [英] Assignment that implements a list in compact form

问题描述

我在课程分配中有一个问题.

I have a question in a course assignment.

考虑形式为[a,a,a,b,b,c,a,a,a,a]及其紧凑形式的重复列表，定义为夫妇列表[[a,3],[b,2],[c,1],[a,4]].

Consider repetitive lists of the form [a,a,a,b,b,c,a,a,a,a] and their compact form, defined as lists of couples, [[a,3],[b,2],[c,1],[a,4]].

定义谓词compress/2，以便在给定列表L1的情况下，L2是其紧凑形式，则满足compress(+L1, ?L2).

Define the predicate compress/2 such that compress(+L1, ?L2) is satisfied if, given a list L1, L2 is its compact form.

到目前为止，我想出了以下代码:

So far, I have come up with the code below:

compress(X,[[X,1]]).
compress([H1,H2|T1],[[H1,C]|T2]):-
   H1 = H2,
   compress(T1,T2),
   C is R + 1.

我不确定我是否做对了.有人可以指出正确的方向.

I am not sure if I am doing it right. Could someone please point to the right direction.

推荐答案

以下是一些帮助您入门的想法.

Here are some ideas to get you started.

由于结果有计数器，因此您需要对重复元素进行连续计数.因此，马上考虑包含计数器的辅助谓词，这是在Prolog中处理计数器的一种典型方式.计数器的这种用法通常称为累加器.

You're going to need to keep a running count of repeated elements since your results have counters. So right off, consider an auxiliary predicate that includes the counter, which is a typical way of handling it in Prolog. This use of a counter is commonly referred to as an accumulator.

compress(L, C) :-
    compress(L, 1, C).   % Start counter at 1

现在，您需要考虑几种不同的情况:

Now you'll need to consider a few different cases:

compress([], _, []).                 % This is an easy one!

这表示如果我压缩一个空列表，我会得到一个空列表.

This says that if I compress an empty list, I get an empty list.

compress([H], Count, [[H,Count]]).   % This is an easy one!

这句话说，如果我压缩一个元素的列表，而我当前的运行计数是Count，那么结果是[[H, Count]].

This one says if I compress a list of one element and my current running count is Count, then the result is [[H, Count]].

compress([H, H|T], Count, TC) :-
    ...

在这种情况下，我有一个连续的计数并且该元素仍在重复.结果将是列表TC，但是我还不知道它是什么样子，因为我们仍处于重复循环中，需要通过递归来确定.该谓词应该是什么样?在您的示例中，在前两个元素相同的情况下，您在结果中包括了一个计数，这不是包括该计数的正确时间(请参见下面的子句).

This is the case where I have a running count and the element is still repeating. The result is going to be a list TC but I don't know what it looks like yet since we're still in a repeating cycle and it will need to be determined through recursion. What should this predicate look like? In your example, you included a count in the result when the first two elements were the same, which is not the right time to include the count (see the clause below).

compress([H1, H2|T], Count, [[H1,Count]|TC]) :-
    dif(H1, H2),
    ...

在这种情况下，我有一个连续的计数，并且重复次数在H1处停止.由于当前循环的重复以H1结尾，因此我们知道结果看起来像[[H1, Count]|TC]，因为H1已经重复了Count次.我们还没有通过递归确定列表TC的其余部分.这种谓词实现应该是什么样的?

This is the case where I have a running count and the repeating stops at H1. Since the repeating of the current cycle ends with H1, we know the result looks like [[H1, Count]|TC] because H1 has repeated Count times. We just have yet to determine the rest of the list TC through recursion. What should this predicate implementation look like?

还有其他执行上述逻辑的方法(例如，使用->和;构造等)，但这将使其保持简单.

There are other ways of doing the above logic (e.g., with -> and ; construct, etc), but this will keep it simple.

尝试将其视为规则，其中谓词子句的开头是断言，如果该子句的以下元素为true，则该断言为true.然后递归思考.

Try to think of these as rules where the head of the predicate clause is the assertion which will be true if the following elements of the clause are true. And think recursively.

---

事后考虑，可以通过使用结果携带累加器而无需单独的累加器来完成此操作:

---

As an afterthought, this could be done without a separate accumulator by using the result to carry the accumulator:

compress([], []).
compress([H], [[H,1]]).
compress([H1,H2|T], [[H1,1]|R]) :-
    dif(H1, H2),
    compress(...).                 % left as an exercise
compress([H,H|T], [[H,N]|R]) :-
    N #= N1 + 1,
    compress(...).                 % left as an exercise

这篇关于以紧凑形式实现列表的分配的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！