Permutationen eines binären Baums

Betrachten einen binären Baum:

  1. n ist ein Knoten, wenn n ist eine ganze Zahl
  2. (+ eine b) ist ein Knoten, wenn eine und b sind Knoten.

Wir haben die folgenden drei Operationen:

  1. (+ eine b) -> (+ b eine)
  2. (+ (+ eine b) c) -> (+ eine (+ b c))
  3. (+ eine (+ b c)) -> (+ (+ eine b) c) -- (2. in umgekehrter Reihenfolge)

Brauche ich einen Algorithmus für die, die alle möglichen Permutationen einer gegebenen Struktur mit diesen Operationen. Jeder Betrieb, vielleicht bei jedem Teilbaum. Mit eine permutation, die ich meine, jeder Baum, der hat den exakt gleichen Satz von Blättern. Es ist wahrscheinlich nicht sehr schwierig, aber ich kann einfach nicht scheinen, um es herauszufinden.

[Bearbeiten] Die Blätter können auch Namen (d.h. Variablen), so verlassen sich auf Ihre Eigenschaften als ganze zahlen ist keine option. Die Bäume repräsentieren Summen.

[Edit2] Der Sinn dieser übung ist zu reduzieren, eine Summe finden, indem Bezug auf die form Eine und -Ein, swizzling den Baum, um Sie in einen Teilbaum (+ Eine -Ein), um Sie zu beseitigen. Die drei Operationen sind die oben Axiome in meinem system, und Sie müssen alle Weg, sonst ist es nicht möglich zu beweisen, dass die reduzierte Baum ist dem original gleich. Da bin ich mit Zwölf Logik-Programmiersprache, wenn ich herausfinden kann, einen Algorithmus zu tun, was ich ursprünglich gefragt, der rest folgt leicht, aber alternative Lösungen sind natürlich willkommen.

  • Was die offensive ist in dieser Frage? Und warum es downvoted?
  • Ich denke, jemand ist beleidigt von Leuten posten Hausaufgaben.
  • Ich versichere Ihnen, es ist nicht ein Hausaufgaben problem. Es ist für eine automatisierte theorembeweiser ich mache.
  • Sorry, wusste nicht, es war tagged Hausaufgaben von jemand anderem.
  • Es sieht aus wie Hausaufgaben
  • Was meinst du, wie es aussieht, Hausaufgaben? Es sieht nicht nach Hausaufgaben zu mir.
  • "n ist ein Knoten, wenn n ist eine Ganzzahl". Es gibt unendlich viele ganze zahlen, so dass heißt, Sie müssen eine unendliche Anzahl von Knoten in Ihrem Baum.

InformationsquelleAutor TrayMan | 2009-03-16
  1. 2

    Scheint, wie die einfachste Lösung wäre eine Tiefe-ersten traversal des Baums zu sammeln alle Knoten in eine Liste generieren, die alle Permutationen der Liste, dump jede permutation in binärer Baum.

    So, da die Liste (+ a (+ b c) ), haben wir den Knoten [a; b; c], die die folgenden Permutationen:

    [a; b; c]
[a; c; b]
[b; a; c]
[b; c; a]
[c; a; b]
[c; b; a]

    Das erste Element in der Liste ist dein Kopf, die beiden folgenden Elemente sind die untergeordneten Knoten, die nächsten vier Elemente der Kind-Kind-Knoten, und so weiter.

    Die Komplexität dieses drastisch erhöht wenn Sie benötigen eine Liste aller möglichen Bäume, anstatt nur ausgewogensten. In diesem Fall würden Sie brauchen, um Sie zu gruppieren, wie diese:

    [a; b; c; d]
[(a; b); c; d]
[(a; b; c); d]
[a; (b; c); d]
[a; (b; c; d)]
[a; b; (c; d)]
[a; b; d; c]
//first permutation
[(a; b); d; c]
[(a; b; d); c]
...

    Wobei jedes n-Tupel ist eine Menge von Knoten. Für mehr als ein paar Knoten, das Universum, erlebt eine Hitze-Tod, bevor Ihr Algorithmus immer abgeschlossen.

    • Ich betrachtete dies als eine mögliche Lösung, jedoch hat es bestimmte Komplikationen. Ich werde ellaborate in meiner Frage.
    InformationsquelleAutor Juliet
  2. 1

    Die Lösung für dieses problem ist wohl noch Catalan-zahlen. Es gibt Cn-1 möglich binäre Bäume mit n Blätter, und es gibt n! mögliche Ordnungen der Blätter, so gibt es n! * Cn-1 möglich, Bäume. Aufzählen Ihnen ist es etwas schwieriger, aber.

    • Glücklicherweise ist die Anzahl der Blätter wird relativ gering sein.
    InformationsquelleAutor Adam Rosenfield
  3. 1

    Diese Operationen sind Analog zu addition mit den folgenden Eigenschaften: - Verschluss, Assoziativität, commutativity. Für einen passenden Knoten, jeder verlässt die Menge der Blätter derselben, und können angewendet werden in einer rekursiven Weise. Um die Anzahl der Permutationen von einem gegebenen Knoten x (in einer seltsamen Mischung von Haskell und F#)

    let count x = match x with
  | LeafNode -> 1
  | TreeNode (a,b) -> 2 * count a * count b
    • naja anscheinend Haskell + F# = ocaml... weil Sie schrieb, dass. 🙂
    • oh yeah! ich soll ich vergessen habe das rec-Deklaration, und dann ist es nur F#
    • Die Bäume repräsentieren Beträge, jedoch sind die eigentlichen Blätter sind nicht alle zahlen. Ich denke, ich sollte haben legen Sie, dass in der Frage.
    • außerdem impliziert nicht zahlen, ich war aus der Perspektive der Gruppe, Theorie und Veranschaulichung der Analogie des Problems zu zählen in die abelsche Gruppe, da die besagten Operationen erfüllen die Eigenschaften.
    • Natürlich. Ich konnte deinen post falsch gelesen.
    InformationsquelleAutor eulerfx
  4. 1

    Haben Sie Assoziativität und commutativity, so dass Sie bewegen können Elemente frei herum.
    Einen praktischen Ansatz für dieses problem ist so etwas wie die folgenden:

    • Kamm der Baum auf der einen Seite, erhalten Sie eine Liste.

    • Sortieren Sie die Liste, so dass sich die Elemente aufheben, sind neben einander.

    • Verschieben Sie die Elemente in einen Teilbaum und Abbrechen.

    Um Ihren gewünschten Beweise, die Sie haben zu bauen, kleine Beweise für diese operation, die Sie dann kombinieren.

    Alternativ kann man sich bis AC-matching.

    Versuchen alle Permutationen, wie Sie Sie vorschlagen wird nur erhalten Sie eine große kombinatorische explosion.

    • Ich kann leider nicht eine Bestellung für die Blätter, also die Sortierung ist nicht möglich. Die Anzahl der Blätter ist klein (etwa 5), das ist, warum ich bin nicht besonders besorgt, mit der großen Anzahl von Permutationen.
    • Ich bin nicht vertraut mit AC-matching und ein flüchtiger Blick zeigt, dass es im Zusammenhang, aber ich weiß nicht, wie es gilt für dieses problem.
    InformationsquelleAutor starblue
  5. 1

    Als wies darauf hin, wenn Sie wirklich die commutativity und Assoziativität der Operatoren Axiome, sind Sie am besten aus, indem Sie nur sammeln die Summanden und der Verarbeitung wie ein set oder eine Liste.

    Wenn das nicht zufriedenstellend, die nächste Sache ist zu beachten, dass eigentlich nicht zu benötigen scheinen alle der Permutationen, aber Sie wollen schreiben Sie Ihre Ausdrücke, um zu vereinfachen. Das kann gemacht werden viel effizienter, als die Erzeugung aller Permutationen!

    Jedoch zu wiederholen :), wenn Sie NUR commutativity und Assoziativität von Operatoren, Verfahren der Begriffe in einem Satz.

    • Es ist wahr, dass ich nicht alle Permutationen. Es schien nur wie ein einfacher brute-force-Weg, es zu tun.
    InformationsquelleAutor Antti Huima
  6. 0

    Ich entdeckt habe, eine Lösung für das zugrunde liegende problem der Verringerung Bäume:

    1. Finden Sie ein paar Blätter A und-A aus dem Baum.
    2. a), Wenn A und-A sind in der gleichen Kind, recurse.
    3. b) 'Blase' A und-A an die Spitze Ihrer jeweiligen childs. Es gibt acht mögliche resultierende Fällen, aber Sie sehen alle so etwas wie dieses (+ (x-A) (-y)). Gehen aus, die zu (+ (+ x y) (+ A,- A)) ist ganz einfach.

    Wie vorgeschlagen, einen anderen Weg, es zu tun wäre, um zuerst konvertieren den Baum in eine Liste: (+ A (+ B (+ ...)) X), dann finden Sie ein paar Ein-und -Ein und bringen Sie nach oben. Ich vermute, dass dies möglicherweise eine längere Beweis (was unerwünscht ist) als die oben genannten Algorithmus, allerdings habe ich es nicht probiert.

    Dennoch finde ich die ursprüngliche Frage faszinierend und ich würde gerne versuchen, wie ein Algorithmus, basierend auf den vergleichen zu den oben genannten.

    InformationsquelleAutor TrayMan
Schreibe einen Kommentar