Clojure:Wie erstelle ich einen „Versuch“?

Question

Angesichts der folgenden ...

(def inTree
 '((1 2)
   (1 2 3)
   (1 2 4 5 9)
   (1 2 4 10 15)
   (1 2 4 20 25)))

Wie würden Sie es in diesen Versuch umwandeln?

(def outTrie
 '(1
    (2 ()
       (3 ())
       (4 (5
            (9 ()))
          (10
            (15 ()))
          (20
            (25 ()))))))

Answer 1

Hier ist eine Lösung gereinigt. Dies behebt einen Fehler Brian Add-to-Trie-Methode, da es zur Zeit hängt von Ihnen den ASTA in zunehmender Länge, um das Einfügen. Es ermöglicht auch die Trie durch Präfix Abfragen, die ein gemeinsamer Anwendungsfall ist.

Beachten Sie die Speichernutzung ist hier höher, da es die Werte in den Blattknoten des Trie speichert, so dass Sie Suchen durchführen können.

(defn add-to-trie [trie x]
  (assoc-in trie x (merge (get-in trie x) {:val x :terminal true})))

(defn in-trie? [trie x]
  "Returns true if the value x exists in the specified trie."
  (:terminal (get-in trie x) false))

(defn prefix-matches [trie prefix]
  "Returns a list of matches with the prefix specified in the trie specified."
  (keep :val (tree-seq map? vals (get-in trie prefix))))

(defn build-trie [coll]
  "Builds a trie over the values in the specified seq coll."
  (reduce add-to-trie {} coll))

Answer 2

Listen sind sehr ungeschickt hier nicht ineffizient zu erwähnen. In Clojure ist es mehr idiomatische Vektoren zu verwenden und Hash-Karten und setzt bei Bedarf. Mit Hash-Karten:

(def in-tree
 '((1 2)
   (1 2 3)
   (1 2 4 5 9)
   (1 2 4 10 15)
   (1 2 4 20 25)))

(defn add-to-trie [trie x]
  (assoc-in trie `(~@x :terminal) true))

(defn in-trie? [trie x]
  (get-in trie `(~@x :terminal)))

Wenn Sie es wollten sortiert drucken Sie sorted-maps stattdessen verwenden könnte, aber man müsste eine eigene Version von assoc-in schreiben, die Karten nach unten die ganze Art und Weise sortiert eingesetzt. In jedem Fall gilt:

user> (def trie (reduce add-to-trie {} in-tree))
#'user/trie
user> trie
{1 {2 {4 {20 {25 {:terminal true}}, 10 {15 {:terminal true}}, 5 {9 {:terminal true}}}, 3 {:terminal true}, :terminal true}}}
user> (in-trie? trie '(1 2))
true
user> (in-trie? trie '(1 2 4))
nil
user> (in-trie? trie '(1 2 4 20 25))
true

Answer 3

Als allgemeiner Ansatz, hier ist was ich tun würde:

• ein paar Funktionen schreiben trie zu schaffen und neue Elemente in einen Trie eingefügt werden soll.
• Erstellen Sie eine neue trie.
• Iteration durch die Eingabeliste und fügen Sie jedes Element in die Trie.

Dieses Problem eignet sich sehr gut für eine rekursive Implementierung. Ich würde für das Ziel, wenn möglich.

Answer 4

Ich bin mir sicher, dass es einen schöneren Weg gibt (den gab es!siehe Brians Antwort, es ist besser):

(defn find-in-trie
  "Finds a sub trie that matches an item, eg:
  user=> (find-in-trie '(1 (2) (3 (2))) 3)
  (3 (2))"
  [tr item]
  (first (for [ll (rest tr) :when (= (first ll) item)] ll)))


(defn add-to-trie
  "Returns a new trie, the result of adding se to tr, eg:
  user=> (add-to-trie nil '(1 2))
  (1 (2))"
  [tr se]
  (cond
    (empty? se) tr
    (empty? tr) (add-to-trie (list (first se)) (rest se))
    :else (if-let [st (find-in-trie tr (first se))]
            (cons (first tr)
                  (cons (add-to-trie st (rest se))
                        (filter (partial not= st) (rest tr))))
            (cons (first tr)
                  (cons (add-to-trie (list (first se)) (rest se))
                        (rest tr))))))

(def in '((1 2)
          (1 2 3)
          (1 2 4 5 9)
          (1 2 4 10 15)
          (1 2 4 20 25)))

(reduce add-to-trie '(nil) in)

-> (null (1 (2 (4 (20 (25)) (10 (15)) (5 ​​(9))) (3))))

Beachten Sie, dass ich mich für die Verwendung von nil als Wurzelknoten entschieden habe und mir nicht die Mühe gemacht habe, leere Listen zu führen, um anzuzeigen, dass es keine untergeordneten Knoten gibt.Tatsächlich ist es nicht korrekt, es auf diese Weise zu tun, da dadurch die Teilstringidentität nicht gewahrt bleibt.