Prolog: wie Schreibe (und Verwendung) einer Funktion, die Listen alle Listen-Permutationen?

Habe ich gefunden, so ein Beispiel der naiven Art, geschrieben in prolog und ich bin versucht, es zu verstehen:

naive_sort(List,Sorted):-perm(List,Sorted),is_sorted(Sorted).

is_sorted([]).
is_sorted([_]).
is_sorted([X,Y|T]):-X=<Y,is_sorted([Y|T]).


perm(List,[H|Perm]):-delete(H,List,Rest),perm(Rest,Perm).
perm([],[]).

delete(X,[X|T],T).
delete(X,[H|T],[H|NT]):-delete(X,T,NT).

Naive_sort Aufruf korrekt funktioniert, aber ich kann einfach nicht herausfinden, warum. Das Hauptproblem ist die permutation. Wenn Sie aufgerufen wird, implizit, es gibt immer nur einen Wert. Wie ist es dann möglich, dass in naive_sort Funktion rufen Sie alle Permutationen überprüft werden? Auch, wie könnte ich das ändern perm-Funktion schreiben, die alle Permutationen?

InformationsquelleAutor agnieszka | 2010-02-04
  1. 9

    Dies ist wirklich eine naive Art-es durchläuft den Baum von allen möglichen Permutationen, bis es zum Glück findet eine sortierte ein. Das ist eine Komplexität von O(n!) ich nehme an :>

    Über die permutation-Funktion -- es funktioniert "rückwärts" - beachten Sie, dass die definition nimmt den Kopf aus dem Ergebnis. Wenn Sie rund um Ihren point of view, werden Sie feststellen, dass anstatt zu löschen es tatsächlich fügt Werte durch arbeiten rückwärts. Wie der Algorithmus arbeitet nach hinten, damit die Head gewählt, kann alles sein, die es erlauben, ein Ergebnis erstellt werden, damit alle verwendeten Wert aus der Liste.

    Grundsätzlich die permutation Algorithmus übersetzt die folgenden verfahrenstechnischen Umsetzung:

    1. wählen Sie ein Element aus der Liste
    2. legen Sie es in vor Sortiert

    Diese Art der Erzeugung von Permutationen. Alle von Ihnen.

    Kurz - perm erzeugt, die den gesamten Raum der möglichen Lösungen, indem Sie ausgehend von einem leeren Lösung und überprüfen, wie die gegebene Lösung möglich ist, aus einer gültigen löschen.

    ?-  perm( [ 1, 2, 3 ] , P ) 
P = [1, 2, 3]; 
P = [1, 3, 2]; 
P = [2, 1, 3]; 
P = [2, 3, 1]; 
P = [3, 1, 2]; 
P = [3, 2, 1]; 
no
    • warum also whe Aufruf dieser Funktion zeigt nur EIN Ergebnis, nicht alle von Ihnen?
    • es ist nicht eine Funktion! Es ist ein Prädikat, die ist NUR wahr, wenn das erste argument eine permutation des zweiten.
    • verwenden GNU Prolog oder SWI?
    • YESSS, ich weiß noch, du hast geschrieben "es erzeugt Permutationen. Ihnen allen ist." - es funktioniert nicht. es findet die erste Kombination des unbekannten Argumente erfüllt, dass die Prädikat - dass also nur EINE permutation. also, wie, wie ist es möglich, dass es funktioniert beim Aufruf naive_sort?
    • mit SWI - - - - - - - -
    • da hält es "calling" perm, bis entweder is_sorted ist wahr, oder es schlägt fehl.
    • 1. aber wenn ich anrufen perm viele Male, die ich bekomme immer das gleiche Ergebnis. 2. nach deinem edit: mein Ergebnis ist anders nach diesem Anruf zeigt es nur ein Ergebnis und ich weiß nicht, wie es zu ändern so zeigen Sie alle
    • tylko ze wielokrotne wywolywanie perm zawsze daje te gleiche wyniki
    • bo wielokrotnie wywołujesz, eine nie ściągasz ein weiterer wyniki :). Wpisz średnik ich enter po pierwszym wyniku -- będziesz miała szukanie dalszych rozwiązań -- csupomona.edu/~jrfisher/www/prolog_tutorial/1.html
    • z nieba mi spadles dzien przed egzaminem... 😀 czyli po prostu prolog wie ze rozwiazan perm-eine wyolaniu naive_sort jest wiele ich skoro jedno nie dziala zu probuje drugie. 2 dni na nauczenie prologa to jednak waren ein wenig za malo - wielkie dzieki! 😉
    • Prolog wie, że póki perm mu nie powie "Nein", um może próbować czerpać z niego vorschlagen. 2 dni zu zdecydowanie za mało, bo prolog inny paradygmat programowania (programowanie logiczne) który znacząco różni się od szeroko znanych... powowdzenia!
    • 😀 Łojczysty język na stacku. keine patrzcie... 😀
    • zbliżający się egzamin zmusza tun radykalnych rozwiązań ;>

    InformationsquelleAutor Kornel Kisielewicz
  2. 10

    Das Hauptproblem ist die permutation
    Funktion. Wenn Sie aufgerufen wird, implizit
    es ist immer retrns nur einen Wert.

    Prolog ist eine Sprache, die immer versucht, die an den Nachweis der Wahrheit einer Aussage, durch die sich diese mithilfe der Axiome (Fakten oder Regeln) gegeben.

    perm ist nicht eine Funktion im Sinne der prozeduralen Programmierung. perm ist ein Prädikat, über die wir erzählen prolog zwei Dinge:

    1. Die leere Liste ist eine permutation von sich selbst.
    2. List ist eine permutation von [H|Perm] wenn es eine Liste Rest so dass Rest erhält man durch löschen von H aus List, und Rest ist eine permutation von Perm.

    Wenn Sie gefragt werden, ob einige Liste ist eine permutation eines anderen, prolog versucht, diese ableitungsschritte (rekursiv), um es zu beweisen. Wenn diese Rekursion erreicht eine Sackgasse, d.h. eine Aussage kann nicht bewiesen werden, da keine Regeln auf Sie angewendet werden kann, es backtracks.

    • ich kannte alle, außer die Rückverfolgung, wenn alles andere versagt - das erklärt vieles
    • Beschreibung es ist so viel einfacher, wenn Englisch Muttersprache -_-
    • Ich nehme das als Kompliment, denn es ist nicht meine Muttersprache entweder 🙂
    • +1: wenn das der Fall ist 😉
    InformationsquelleAutor meriton
  3. 1

    verwenden Sie ein Semikolon (;) am Ende jeder permutation prolog geben würde Sie, bis es keine andere permutation, prolog sollte sagen Kein

    • Ja, der Grund, warum Die OP ist zu sehen nur eine Lösung, wenn Sie aufgerufen wird, ist wahrscheinlich, weil Sie nicht eingeben ; der ? Aufforderung zu sehen, die andere (Kräfte zu Versagen und wieder ansetzen, um eine andere Lösung finden).
    InformationsquelleAutor cenyo
Schreibe einen Kommentar