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.

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

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

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

So this

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

would become this

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

回答1:

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

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

回答2:

Here's a version for Racket (sorry, I'm not a Common Lisper, so can't help there):

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

Let's break the problem down in English:

1. To collect up the actual counts of your "three numbers", build a hash table using the "three numbers" as the key, and 0 as the default value.
2. For each item in your incoming list, you'd add the count to the value, then update the hash table with that new value.
3. Then iterate through your hash table to build your result list.