清除列表中的任何重复列表。 Lisp

这比标题所暗示的要复杂得多，但我无法将它压缩成一句话。清除列表中的任何重复列表。 Lisp

我正在使用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)) 
;  ^

我在什么方向借此大气压的损失。并希望我如何能够最好地解决这个

来源

2014-12-02 sam

的Common Lisp或计划？ – uselpa 2014-12-02 17:41:53

我会做的第一件事：用英文写一个版本。当你看起来很好，围绕它添加括号并使其工作... Stackoverflow是针对实际的编程问题（最好的代码和问题描述），而不是寻找设计和实现你的算法的人... – 2014-12-02 17:45:03

@LePetitPrince Clisp – sam 2014-12-02 17:53:34

在通用Lisp中，最简单的方法是使用散列表构建数据的直方图，然后遍历散列表以重新组合计数和键。下面直方图创建直方图哈希表：

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

：

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

然后，它不是太难从哈希表中写一个函数来获取列表对（价值的关键。）

若要将此你的数据，你需要一个等于哈希表，使得密钥（这是整数的列表）被正确比较，关键功能是休息，因为你比较的尾巴输入。增量键功能是第一个，因为您希望增加列表中第一个元素的“计数”。

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

来源

2014-12-02 19:06:10

糟糕，它应该是一个_weighted_直方图，所以一个简单的'incf'不会。特别是在OP的例子中，结果应该是'（2 1 1 0）'而不是'（1 1 1 0）'。 – 2014-12-02 19:08:37

@ ChrisJester-Young相应更新。 – 2014-12-02 19:12:14

哈希表对我来说是相当新的。我非常感谢答案，请问您是否可以添加一些评论，以便我更好地了解发生了什么？ – sam 2014-12-02 23:44:26

下面一些建议是对球拍版本（对不起，我不是一个普通的利斯佩尔，所以帮不了那里）：

(define (count-alist alist) 
    (define ht (for/fold ((ht (hash))) 
         ((ass (in-list alist))) 
       (hash-update ht (cdr ass) (curry + (car ass)) 0))) 
    (for/list (((key val) (in-hash ht))) 
    (cons val key)))

让我们打破问题英文问题：

要收集“三个数字”的实际计数，请使用“三个数字”作为关键字，并将0作为默认值构建一个哈希表。
对于传入列表中的每个项目，您需要将计数添加到该值，然后使用该新值更新哈希表。
然后迭代你的散列表来建立你的结果列表。

来源

2014-12-02 17:59:39

清除列表中的任何重复列表。 Lisp

回答

相关问题