Prolog - kumulative Duplikate in einer Liste erstellen?

Question

Ich habe eine Liste L gegeben und meine Aufgabe ist es, kumulative Duplikate zu erstellen, je nachdem, wie viele ich will.

ich die Liste [a,b,c,d] zum Beispiel habe und will das erste Element 4 mal dupliziert werden (optional), dann hat jedes nachfolgendes Element wie die vorherigen + 1.

Lassen Sie sich mein Prädikat übernimmt dupliziert werden aufgerufen list_copy(L,N,R), das Ergebnis mit L = [a,b,c,d] und K = 2 sollte sein:

?- list_copy([a,b,c,d],2,R). 
R = [a,a,b,b,b,c,c,c,c,d,d,d,d,d] 

ich habe es geschafft, zum Duplizieren einer Liste zweimal einen universellen Code zu erstellen:

dupl([],[]). 
dupl([O|U],[O,O|U1]) :- dupl(U,U1). 

Je nachdem, wie viele O 's ich in meine zweite Zeile stecke, bekomme ich so viele Duplikate.

Meine Frage ist jedoch: Wie kann ich eine dritte Variable als kumulativen Zähler implementieren, um das gewünschte Ergebnis zu erhalten?

Answer 1

Wenn Sie die Dateien nacheinander "zählen" müssen, verwenden Sie succ/2. Es hat die nette Eigenschaft, dass es in beide Richtungen funktioniert, und schlägt fehl, wenn Sie es mit succ(X, 0) aufrufen.

So Zuerst wird das Prädikat, das "cumulative Dubletten" tut:

cum_dup([], _, []). 
cum_dup([X|Xs], N, Ys) :- 
    repeat_n(X, N, Ys, Back), 
    succ(N, N1), 
    cum_dup(Xs, N1, Back). 

Dieses Prädikat verwendet repeat_n/4, die ein Element erfolgt, eine nicht negative ganze Zahl ist, und wiederholt das Element. Es hinterlässt ein "Loch" in der Rückseite der Liste, das Sie mit dem Rest des Ergebnisses unter Verwendung cum_dup/3 füllen können. Hier ist ein Straight-Forward-Implementierung von repeat_n/4:

repeat_n(_, 0, L, L). 
repeat_n(X, N, [X|Xs], Rest) :- 
    succ(N0, N), 
    repeat_n(X, N0, Xs, Rest). 

Dies wird bereits geben Sie das Ergebnis benötigen Sie:

?- cum_dup([a,b,c,d], 2, R). 
R = [a, a, b, b, b, c, c, c, c, d, d, d, d, d] ; 
false 

Es hinterlässt eine harmlose Wahl Punkt.Es gibt zu viele Möglichkeiten, um eine repeat_n/4 zu machen, dass nicht unnötig Wahl Punkte nicht verlassen:

• Verwendung CLP (FD)
• verwenden, um einen Schnitt
• eine bedingte verwenden (if-then-else)
• verwenden, um eine Struktur anstelle einer ganzen Zahl

ein Beispiel:

repeat_n(X, N, L, Back) :- 
    length(Ns, N), 
    repeat_n_(Ns, X, L, Back). 

repeat_n_([], _, L, L). 
repeat_n_([_|Ns], X, [X|Xs], L) :- 
    repeat_n_(Ns, X, Xs, L). 

Hier, anstatt mit einer Ganzzahl zu zählen, verwenden Sie (ab) eine Liste dieser Länge.

Ich denke, Sie können selbst darüber nachdenken und eine andere Frage stellen, wenn Sie wirklich brauchen.

Answer 2

--- EDIT --- modifiziert mit succ/2, wie von Boris vorgeschlagen (danke!).

Ich nehme an, Sie können eine Hilfsklausel verwenden. Wie list_copy_h/4 im folgende Beispiel

list_copy_h([], _, _, []). 

list_copy_h([_ | Tin], 0, Num, Lout) :- 
    succ(Num, Np1), 
    list_copy_h(Tin, Np1, Np1, Lout). 

list_copy_h([H | Tin], Count, Num, [H | Tout]) :- 
    succ(Cm1, Count), 
    list_copy_h([H | Tin], Cm1, Num, Tout). 

list_copy(Lin, Num, Lout) :- 
    list_copy_h(Lin, Num, Num, Lout). 

Die Idee ist, einen Zähler verwenden (das zweite Argument), die auf Null zu verringern. Wenn Null ist, wird der Kopf der Eingabeliste entladen und der Zyklus beginnt erneut mit dem folgenden Element der Eingabeliste, aber erhöht den Startwert des Zählers. Das dritte Argument ist der Startwert.