Prolog: Wie schreibe ich (und verwende) eine Funktion, die alle Listenpermutationen auflistet?

8

Ich habe ein Beispiel für naive Art gefunden, das in Prolog geschrieben ist, und ich versuche es zu verstehen:

%Vor%

Naive_sort Call funktioniert korrekt, aber ich kann einfach nicht herausfinden warum. Das Hauptproblem ist die Permutation. Wenn es implizit aufgerufen wird, gibt es immer nur einen Wert zurück. Wie ist es dann möglich, dass im naive_sort Funktionsaufruf alle Permutationen überprüft werden? Wie könnte ich auch die Perm-Funktion ändern, um alle Permutationen zu schreiben?

    
agnieszka 04.02.2010, 00:32
quelle

3 Antworten

9

Dies ist wirklich eine naive Art - es durchquert den Baum aller möglichen Permutationen, bis es glücklicherweise einen sortierten findet. Das ist eine Komplexität von O (n!) Ich nehme an: & gt;

Über die Permutationsfunktion - sie funktioniert "rückwärts" - beachten Sie, dass die Definition den Kopf aus dem Ergebnis entfernt. Wenn Sie Ihren Standpunkt umkehren, werden Sie bemerken, dass Sie Werte löschen, anstatt sie zu löschen, indem Sie rückwärts arbeiten. Da der Algorithmus rückwärts arbeitet, kann die H ead also alles sein, was es erlaubt, ein Ergebnis zu erzeugen, also einen unbenutzten Wert aus List.

Grundsätzlich wird der Permutationsalgorithmus in die folgende prozedurale Implementierung übersetzt:

  1. Wählen Sie einen Eintrag aus der Liste
  2. setze es vor Sorted

Auf diese Weise erzeugen Sie Permutationen. Alle von ihnen.

Kurz gesagt - perm erzeugt den gesamten Raum möglicher Lösungen, indem er aus einer leeren Lösung heraus startet und prüft, wie die gegebene Lösung aus einem gültigen Löschen möglich ist.

%Vor%     
Kornel Kisielewicz 04.02.2010, 00:50
quelle
10
  

Das Hauptproblem ist die Permutation   Funktion. Wenn es implizit aufgerufen wird   es ruft immer nur einen Wert ab.

Prolog ist eine Sprache, die immer versucht, die Wahrheit einer Aussage zu beweisen, indem sie sie anhand der gegebenen Axiome (Fakten oder Regeln) ableitet.

perm ist keine Funktion im Sinne einer prozeduralen Programmierung. perm ist ein Prädikat, über das wir zwei Dinge erzählen:

  1. Die leere Liste ist eine Permutation von sich selbst.
  2. List ist eine Permutation von [H|Perm] , wenn es eine Liste Rest gibt, so dass Rest erhalten wird, indem H von List gelöscht wird und Rest eine Permutation von Perm ist.

Wenn gefragt wird, ob eine Liste eine Permutation eines anderen ist, wird prolog versuchen, diese Ableitungsschritte (rekursiv) anzuwenden, um es zu beweisen. Wenn diese Rekursion eine Sackgasse erreicht, d. H. Eine Anweisung, die nicht bewiesen werden kann, da keine Regeln auf sie angewendet werden können, rückt sie zurück.

    
meriton 04.02.2010 01:13
quelle
1

Verwenden Sie ein Semikolon (;) am Ende jeder Permutation, die prolog Ihnen geben würde, solange es keine andere Permutation gibt, sollte Prolog Nein

sagen     
cenyo 16.03.2015 14:46
quelle

Tags und Links