删除列表中的所有重复列表。 Lisp [英] Erase any duplicate lists in a list. Lisp

问题描述

这比标题所建议的要复杂一些，但我无法将其简化为一个句子。

It's a tad more complicated than the title suggests, but I couldn't condense it to one sentence.

我正在使用Clisp，目前有一个列表列表。外部列表任意长，而内部列表长4个整数。这是我可能拥有的示例。

I am using Clisp and currently have a list of lists. The outer list is arbitrarily long, while the inner lists are 4 integers long. Here is an example of what I may have.

((2 1 1 0) (1 1 0 0) (1 0 0 1) (1 1 0 0) (1 0 1 0) (1 0 0 0))

现在每个内部列表由两部分组成，第一项是乘数。最后3项只是列表中包含的值。因此，在某种意义上，（10 1 1 0）与（5 1 1 0）（5 1 1 0）相同。

Now each inner list is made up of 2 parts, the first item is the 'multiplier'. And the last 3 items are just values the list holds. So in a sense, (10 1 1 0) is the same as (5 1 1 0) (5 1 1 0).

我需要一个可以凝聚的函数此列表向下，这样就没有2个列表包含相同的最后3个项目。但是，每3个唯一项中只有一个列表，并且第一个空格中的值是此列表中有多少个。如果这有道理...

I need a function which can condense this list down, so that there is no 2 lists that contain the same last 3 items. But only one list for every unique last 3 items, and a value in the first space which is 'how many' of this list there is. If that makes sense...

所以这

((2 1 1 0) (1 1 0 0) (1 0 0 1) (1 1 0 0) (1 0 1 0) (1 0 0 0))
;          ^                   ^

会变成这样

((2 1 1 0) (2 1 0 0) (1 0 0 1) (1 0 1 0) (1 0 0 0))
;          ^

我不知该采取哪种自动取款机。并希望获得一些有关如何最好地解决此问题的建议

I am at a loss of what direction to take this atm. And would like some advice on how I could best tackle this

推荐答案

在Common Lisp中，最简单的方法可能是使用哈希表构建数据的直方图，然后迭代哈希表以重新组合计数和键。以下将直方图创建为哈希表的直方图：

In Common Lisp, the easiest way to do this is probably to build a histogram of your data using a hash table, and then to iterate through the hash table to recombine the counts and the keys. The following histogram that creates the histogram as a hash table:

(defun histogram (sequence &key hash-args key delta-key)
  "Create a histogram (hash-table) mapping elements to their frequencies.

* sequence---a proper sequence
* hash-args---a list of initargs for MAKE-HASH-TABLE, default is NIL
* key---a designator for a function of one argument, or NIL
* delta-key---a designator for a function of one argument, or NIL

HISTOGRAM returns a hash table mapping keys hash-keys extracted from
the elements of SEQUENCE by KEY to frequencies computed using
DELTA-KEY.  The hash table is created using HASH-ARGS as initargs.
The default is the empty list, in which case the hash-table will
compare hash keys with EQL.  HISTOGRAM iterates through the elements
of SEQUENCE, using KEY to extract a hash key from the element and
DELTA-KEY to extract an increment value, and increments the entry for
the hash key in the histogram by the increment value.

### See Also:
Section 17.2 (Rules about Test Functions), Section 3.6 (Traversal
Rules and Side Effects)"
  (flet ((key (x)
           (if (null key) x
               (funcall key x)))
         (delta (x)
           (if (null delta-key) 1
               (funcall delta-key x))))
    (let ((histogram (apply 'make-hash-table hash-args)))
      (prog1 histogram
        (map nil #'(lambda (element)
                     (incf (gethash (key element) histogram 0)
                           (delta element)))
             sequence)))))

然后编写一个从哈希表中获取（值。键）对列表的函数并不难：

Then it's not too hard to write a function to get a list of (value . key) pairs from a hash table:

(defun hash-table-to-list (table)
  "Return a list of (VALUE . KEY) pairs based on TABLE."
  (loop 
     for k being each hash-key in table 
     using (hash-value v)
     collect (cons v k)))

要将其应用于您的数据，您需要一个等于哈希表，以便键（是整数列表） ）进行比较，并且关键功能是 rest ，因为您正在比较输入的尾部。增量键功能是 first ，因为您想将 count增加列表中的第一个元素。

To apply this to your data, you need an equal hash table so that the keys (which are lists of integers) are compared properly, and the key function is rest, because you're comparing the tails of the input. The delta-key function is first, because you want to increment the "count" by the first element in the list.

CL-USER> (histogram '((2 1 1 0) (1 1 0 0) (1 0 0 1)
                      (1 1 0 0) (1 0 1 0) (1 0 0 0))
                    :hash-args '(:test equal)
                    :key 'rest
                    :delta-key 'first)
;=> #<HASH-TABLE :TEST EQUAL :COUNT 5 {10051558E3}>

CL-USER> (hash-table-to-list *)
;=> ((2 1 1 0) (2 1 0 0) (1 0 0 1) (1 0 1 0) (1 0 0 0))

CL-USER> (histogram '((5 1 1 0) (3 1 1 0) (1 0 0 1) (1 0 0 1))
                    :hash-args '(:test equal)
                    :key 'rest
                    :delta-key 'first)
;=> #<HASH-TABLE :TEST EQUAL :COUNT 2 {100527DA53}>

CL-USER> (hash-table-to-list *)
;=> ((8 1 1 0) (2 0 0 1))

这篇关于删除列表中的所有重复列表。 Lisp的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！