ラケットのアルゴリズムは、リスト間の参照のハッシュを作成しますか？

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に得ることができます知っていますこれはeですVEN醜い：D

PS： - これは学校の割り当て ではありません - 私はハッシュが を命じていません知っている - 読書誰のおかげで、この

Answer 1

私のソリューションは、要素が先頭の要素のメンバーであるかどうかをテストするために、さらにパフォーマンスのためにハッシュセットを使用します。ここで

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

好ましくない場合は、フィルタリングして後処理することができます。

Answer 2

このはあなたが望むものであるかもしれない：

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