common-lisp - 删除列表中的所有重复列表。口齿不清

Question

它比标题所暗示的要复杂一点，但我无法将其浓缩为一句话。

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

((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) 相同。

我需要一个可以压缩这个列表的函数，这样就不会有 2 个列表包含相同的最后 3 个项目。但是每个唯一的最后 3 个项目只有一个列表，第一个空格中的值是该列表的“数量”。如果这是有道理的...

所以这个

((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))
;          ^

我不知道该往哪个方向走这台自动取款机。并想就如何最好地解决这个问题提出一些建议

Answer 1

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

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

然后编写一个函数来从哈希表中获取(值.键)对的列表并不难:

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

要将此应用于您的数据，您需要一个equal 哈希表，以便正确比较键(整数列表)，键函数是rest，因为您正在比较输入的尾部。 delta-key 函数是first，因为您希望通过列表中的第一个元素来增加“count”。

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