Racket 中的一种算法，它对列表之间的引用进行哈希处理？

Question

让我们考虑一下这个列表：

(define parts '(("a" "b" "c" "d" "e" "1")
                ("x" "y" "z" "a")
                ("q" "w" "e" "x")
                ("1" "2" "3" "4" "q")))

我需要创建一个散列，其中每个第一个元素都是一个键，它的值是一个列表，该键的引用出现在另一个列表中。这是我想要的结果的一个例子：

(define desired-result '#hash(("a" . ("x"))
                              ("x" . ("q"))
                              ("q" . ("1"))
                              ("1" . ("a"))))

如您所见，"a"（第一个列表中的第一个）被 "x" 提及（"a" 出现在以 "x" 开头的第二个列表中）。 "x" 被 "q" 等提及

我想出了这段代码来更完整地了解“引用”的东西，但这不是我需要的，而且它也很丑陋（而且可能很慢）查看完整代码：

#lang racket/base

(require racket/list)

(define parts '(("a" "b" "c" "d" "e" "1")
                ("x" "y" "z" "a")
                ("q" "w" "e" "x")
                ("1" "2" "3" "4" "q")))

(define my-hash (make-hash '()))

; This will initialize a key for every single element in parts
(for-each (λ (x)
            (hash-set! my-hash x '()))
          (remove-duplicates (flatten parts)))

(define (put x y)
  (hash-set! my-hash x y))

(define (get x)
  (hash-ref my-hash x))

(define (insert a n)
  (let ([aList (get a)]
        [nList (get n)])
    (unless (member n aList)
      (put a (append aList (list n))))
    (unless (member a nList)
      (put n (append nList (list a))))))

(define (iterate l)
  (let ([a (car l)]
        [r (cdr l)])
    (for-each (λ (n) (insert a n)) r)))

(for-each iterate parts)

my-hash

这将导致：

'#hash(("c" . ("a"))
       ("e" . ("a" "q"))
       ("2" . ("1"))
       ("a" . ("b" "c" "d" "e" "1" "x"))
       ("w" . ("q"))
       ("4" . ("1"))
       ("y" . ("x"))
       ("d" . ("a"))
       ("3" . ("1"))
       ("1" . ("a" "2" "3" "4" "q"))
       ("b" . ("a"))
       ("q" . ("w" "e" "x" "1"))
       ("x" . ("y" "z" "a" "q"))
       ("z" . ("x")))

肯定有更好的方法来获得它（我很好奇是否有人可以提出一些建议）并且我知道我可以从中得到 desired-result，但这会更丑陋。

PS:

这不是学校作业
我知道哈希没有排序

Answer 1

这可能就是您想要的：

(define dwim
  (lambda (parts)
    (let loop ((todo parts)
               (done '())
               (result '()))
      (if (null? todo)
          result
          (let* ((key (caar todo))
                 (value
                  (fold
                   (lambda (lst previous)
                     (if (member key lst)
                         (cons (car lst) previous)
                         previous))
                   '()
                   (append (cdr todo) done))))
            (loop (cdr todo)
                  (cons (car todo) done)
                  (cons (cons key value) result)))))))

Answer 2

我的解决方案还使用哈希集来提高性能，以测试元素是否是前导元素的成员。

(define (process parts)
  (define leading-list (map first parts))
  (define leading-set (list->set leading-list))
  (define in-leading-set? (curry set-member? leading-set))
  (define my-hash (make-hash (map (curryr cons empty) leading-list)))
  (for-each
   (λ (lst)
     (for-each
      (λ (e)
        (hash-set! my-hash e (cons (first lst) (hash-ref my-hash e))))
      (filter in-leading-set? (rest lst))))
   parts)
  my-hash)

这是输出

> (process parts)
'#hash(("1" . ("a")) ("x" . ("q")) ("q" . ("1")) ("a" . ("x")))

需要注意的是，可能有一些元素映射到空列表。例如：

> (define parts2 '(("a" "b")))
> (process parts2)
'#hash(("a" . ()))

如果您不喜欢它们，您可以post-通过过滤掉它们进行处理。

Racket 中的一种算法，它对列表之间的引用进行哈希处理？

An algorithm in Racket which make an hash of references between lists?

algorithm

hash

scheme

racket