Удалите все повторяющиеся списки в списке. 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)) 

Теперь каждый внутренний список состоит из 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

В общем 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))) 

чтобы применить это к вашим данным, вам нужно равное хэш-таблицу, так что ключи (которые являются списки целых чисел) сравниваются должным образом, а функция ключ остальное, потому что вы сравниваете хвосты вход. Функция дельта-ключа - - первая, потому что вы хотите увеличить «счет» первым элементом в списке.

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

Answer 2

Вот версия для Ракетки (извините, я не Common Lisper, поэтому не могу помочь там):

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

Давайте разорвать problem down in English:

1. Чтобы собрать фактические подсчеты ваших «трех чисел», постройте хеш-таблицу с использованием «трех чисел» в качестве ключа и 0 в качестве значения по умолчанию.
2. Для каждого элемента входящего списка вы должны добавить счетчик к значению, а затем обновить таблицу хэша с этим новым значением.
3. Затем перейдите в свою таблицу хешей, чтобы создать список результатов.