Wie Sie access-Liste Permutationen in prolog?

Ich möchte die access-Liste permutation und übergeben Sie Sie als argument an andere Funktionen übergeben werden.

Dies ist die permutation code:

takeout(X,[X|R],R).  
takeout(X,[F|R],[F|S]) :-
   takeout(X,R,S),
   write(S).

perm([X|Y],Z) :-
   perm(Y,W),
   takeout(X,Z,W).  
perm([],[]).

Bitte erklären Sie Ihr problem klar werden. Was werden Sie ausgeführt, was nicht funktioniert? Was wollen Sie sehen, aber nicht sehen, oder sehen, dass Sie nicht sehen wollen?
Ich möchte, um eine Liste der Anzahl von Benutzer, und zeigen Sie alle max-heap-Bäume, so brauche ich die Vertauschung der Liste und senden Sie es als ein parametr max-heap-Funktion,(sorry für mein schlechtes Englisch)

InformationsquelleAutor BeginnerProgrammer | 2012-02-03

9

So starten Sie mit, lassen Sie uns definieren Sie Ihre Prädikate, so dass Sie nicht tun, jede unnötige I/O:
```
takeout(X,[X|R],R).  
takeout(X,[F |R],[F|S]) :- takeout(X,R,S).

perm([X|Y],Z) :- perm(Y,W), takeout(X,Z,W).  
perm([],[]).
```
Nun haben Sie alles, was gelten könnte als einen "reinen" permutation-Funktion:
```
?- perm([1,2,3], X).
X = [1, 2, 3] ;
X = [2, 1, 3] ;
X = [2, 3, 1] ;
X = [1, 3, 2] ;
X = [3, 1, 2] ;
X = [3, 2, 1] ;
false.
```
So, angenommen, Sie haben eine max_heap Funktion, die eine Liste von Werten und erzeugt einen Baum. Ich lasse Sie befürchten, dass, so lasst uns einfach postulieren, dass es vorhanden ist und genannt wird max_heap/2 und lassen Sie uns weiter daran arbeiten, dass Sie einen Weg, um dieses attraktiv genannt display_heap/1. Zu "nehmen", die permutation und "senden" Sie es als parameter an diese Funktionen, sind Sie wirklich sagen, in Mathe-ese: angenommen, P ist eine permutation von X, let ' s machen ein max_heap mit es und zeigt es an. Oder, angenommen, P ist eine permutation von X, H ist ein max-heap aus X, let ' s display H:
```
show_heaps(List) :- perm(List, P), max_heap(P, H), display_heap(H).
```
Dieser sagt das gleiche wie meine englischen Satz: angenommen, P ist eine permutation der Liste, dann H ist ein heap-Darstellung, dann zeigt es. Technisch display_heap/1 ist immer noch ein Prädikat, das könnte wahr sein, oder falsch für eine bestimmte heap. In der Praxis, es wird immer wahr sein, und wenn Sie diese ausführen, müssen noch die Treffer ; immer wieder zu sagen, gib mir eine andere Lösung, es sei denn, Sie verwenden einen failure-driven-loop oder ein extralogical Prädikat wie findall/3 zu verursachen, dass alle Lösungen gefunden werden.

Bearbeiten: Lassen Sie uns besprechen, failure-driven-loops und findall/3. Zunächst lassen Sie mich fügen Sie einige neue Prädikate, weil ich nicht genau wissen, was Sie tun, aber es spielt keine Rolle, für unsere Zwecke.
```
double([X|Xs], [Y|Ys]) :- Y is X*2, double(Xs, Ys).
double([],[]).

showlist(Xs) :- print(Xs).
```
So, jetzt habe ich ein Prädikat double/2 eine Verdoppelung der Werte in der Liste und ein Prädikat showlist/1 druckt die Liste auf der standard-Ausgabe aus. Wir können es ausprobieren, wie so:
```
?- perm([1,2,3], X), double(X, Y), showlist(Y).
[2,4,6]
X = [1, 2, 3],
Y = [2, 4, 6] ;
[4,2,6]
X = [2, 1, 3],
Y = [4, 2, 6] ;
[4,6,2]
X = [2, 3, 1],
Y = [4, 6, 2] ;
[2,6,4]
X = [1, 3, 2],
Y = [2, 6, 4] ;
[6,2,4]
X = [3, 1, 2],
Y = [6, 2, 4] ;
[6,4,2]
X = [3, 2, 1],
Y = [6, 4, 2] ;
false.
```
Wenn Sie ; du sagst, "oder?" zu Prolog. In anderen Worten, Sie sagen, "was sonst?" Du erzählst Prolog, in der Tat, dies ist nicht die Antwort, die ich will, versuchen Sie und finden Sie mir eine andere Antwort, die ich besser gefällt. Sie können formalisieren diesen Prozess mit einem failure-driven loop:
```
?- perm([1,2,3], X), double(X, Y), showlist(Y), fail.
[2,4,6][4,2,6][4,6,2][2,6,4][6,2,4][6,4,2]
false.
```
So, jetzt siehst du die Ausgabe von jeder permutation durchgelaufen double/2 da, und dann Prolog berichtet falsch. Das ist, was man mit etwas wie dieses:
```
show_all_heaps(List) :- perm(List, X), double(X, Y), showlist(Y), nl, fail.
show_all_heaps(_).
```
Schauen, wie das funktioniert:
```
?- show_all_heaps([1,2,3]).
[2,4,6]
[4,2,6]
[4,6,2]
[2,6,4]
[6,2,4]
[6,4,2]
true.
```
Die andere option ist die Verwendung findall/3, das sieht eher aus wie diese:
```
?- findall(Y, (perm([1,2,3], X), double(X, Y)), Ys).
Ys = [[2, 4, 6], [4, 2, 6], [4, 6, 2], [2, 6, 4], [6, 2, 4], [6, 4, 2]].
```
Verwenden diese um Ihr problem zu lösen, ist wahrscheinlich über den Rahmen was auch immer Hausaufgaben ist es, Sie arbeiten aber.

ich Verstand nicht Ihr bedeuten ", es sei denn, Sie verwenden einen failure-driven-loop oder ein extralogical Prädikat wie findall/3, um zu verursachen, dass alle Lösungen gefunden werden."???????
Ich fügte hinzu, eine Erklärung, die auf meine Antwort.

InformationsquelleAutor Daniel Lyons

Können wir definieren list_permutation/2 basierend auf same_length/2 und select/3 wie diese:

:- use_module(library(lists),[same_length/2,select/3]).

list_permutation(As,Bs) :-
   same_length(As,Bs),          % redundant goal helps termination
   list_permutation_(As,Bs).

list_permutation_([],[]).
list_permutation_([A|As],Bs0) :-
    select(A,Bs0,Bs),
    list_permutation_(As,Bs).

Dank same_length/2, die folgenden beiden Abfragen^1,2 beenden universell:

?- list_permutation([1,2,3],Ys).
  Ys = [1,2,3]
; Ys = [1,3,2]
; Ys = [2,1,3]
; Ys = [3,1,2]
; Ys = [2,3,1]
; Ys = [3,2,1]
; false.

?- list_permutation(Xs,[1,2,3]).
  Xs = [1,2,3]
; Xs = [1,3,2]
; Xs = [2,1,3]
; Xs = [2,3,1]
; Xs = [3,1,2]
; Xs = [3,2,1]
; false.

So weit, So gut. Aber was hat die Antwort-Reihenfolge Aussehen, wenn es doppelte Elemente der Liste?

?- list_permutation([1,1,1],Ys).
  Ys = [1,1,1]
; Ys = [1,1,1]
; Ys = [1,1,1]
; Ys = [1,1,1]
; Ys = [1,1,1]
; Ys = [1,1,1]
; false.

5/6 Antworten sind überflüssig! Was können wir tun? Wir haben einfach verwenden selectd/3 statt select/3!

list_permuted(As,Bs) :- 
same_length(As,Bs), 
list_permuted_(As,Bs). 

list_permuted_([],[]). 
list_permuted_([A|As],Bs0) :- 
selectd(A,Bs0,Bs), % selectd/3, nicht wählen/3 
list_permuted_(As,Bs).

Let ' s re-run über Abfrage, gab uns 5 redundante Lösungen vor!

?- list_permuted([1,1,1],Ys).
  Ys = [1,1,1]
; false.

?- list_permuted(Xs,[1,1,1]).
  Xs = [1,1,1]
; false.

Besser! Alle redundanten Antworten verschwunden sind.

Vergleichen wir die Lösung für einige Beispiel-Fall:

?- _Xs = [1,2,1,1,2,1,1,2,1], 
setof(Ys,list_permutation(_Xs,Ys),Yss), 
setof(Ys,list_permuted(_Xs,Ys),Yss), 
Länge(Yss,N). 
N = 84, Yss = [[1,1,1,1,1,1,2,2,2],[1,1,1,1,1,2,1,2,2],[...|...]|...].

OK! Wie über empirische Messungen zur Laufzeit mit einem problem von einer etwas größeren Größe?

Wir verwenden call_time/2 für die Messung der Laufzeit in milli-Sekunden T_ms.

?- call_time(\+ (list_permutation([1,2,1,1,1,2,1,1,1,2,1],_),false),T_ms).
T_ms = 8110.

?- call_time(\+ (list_permuted(   [1,2,1,1,1,2,1,1,1,2,1],_),false),T_ms).
T_ms = 140.

OK! Und mit der richtigen Zusammenstellung von if_/3 und (=)/3, list_permuted/2 ist noch schneller!

^{Fußnote 1: Mit SICStus Prolog version 4.3.2 (x86_64-linux-glibc2.12).}

^{Fußnote 2: Die Antworten von Prolog toplevel wurden, nach der Verarbeitung, der Lesbarkeit zuliebe.}

InformationsquelleAutor repeat

1

Wenn Sie wollen einfach nur erkunden Sie die Permutationen ohne die "False" am Ende, dieser code könnte hilfreich sein,
```
takeout(X,[F |R],[F|S]) :- F\=X, takeout(X,R,S).
takeout(X,[X|R],R).
perm([X|Y],Z) :- perm(Y,W), takeout(X,Z,W).  
perm([],[]).
```
So, die Ausgabe von perm([a,b],B) wäre
```
B=[a,b]
B=[b,a]
```
InformationsquelleAutor Tabare

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.