清除列表中的任何重复列表.口齿不清

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

现在每个内部列表由2个部分组成,第一个项目是"乘数".最后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)))))

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

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

要将此应用于您的数据,您需要一个相等的哈希表,以便正确地比较键(它们是整数列表),并且键函数是休息的,因为您正在比较输入的尾部.delta-key函数是第一个,因为您希望通过列表中的第一个元素递增"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))