W moim zadaniu muszę utworzyć listę wszystkich możliwych zmian (obrotów) innej listy w Prologu. Na przykład,

Prototype: all_shifts(+A,-R,+L,+S)  *S will always start at 1*

?- length([1,2,3,4],L), all_shifts([1,2,3,4],R,L,1).
L = 4,
R = [[2, 3, 4, 1], [3, 4, 1, 2], [4, 1, 2, 3]].

Obecnie mam program, który przesuwa go w lewo raz.

one_shift(A, R) :-
   rotate(left, A, R).

rotate(left, [H|T], L) :- append(T, [H], L).

Muszę jednak stworzyć inny program, w którym końcowy wynik (R) zawiera wszystkie możliwe zmiany. Rekursja w Prologu jest naprawdę zaczyna mnie mylić, ale jestem pewien, że to wymagane. Każda pomoc byłaby naprawdę doceniona.

1
nhlyoung 23 luty 2019, 03:11

2 odpowiedzi

Najlepsza odpowiedź

Bądź logicznie czysty przy użyciu same_length/2 i append/3!

list_rotations(Es, Xss) :-
   same_length(Es, [_|Xss]),
   rotations_of(Xss, Es).

rotations_of([], _Es).
rotations_of([Xs|Xss], Es) :-
   same_length([_|Xss], Suffix),
   same_length(Es, Xs),
   append(Suffix, Prefix, Xs),
   append(Prefix, Suffix, Es),
   rotations_of(Xss, Es).

Przykładowe zapytanie:

?- list_rotations([A,B,C,D], Xss).
Xss = [[B,C,D,A],
         [C,D,A,B],
           [D,A,B,C]].           % succeeds deterministically
3
repeat 26 luty 2019, 12:19

Rozwiązanie twojego problemu może być:

rotatelist([H|T], R) :- append(T, [H], R).

rotate(L,LO,LL):-
    rotatelist(L,L1),
    \+member(L1,LO),!,
    append([L1],LO,L2),
    rotate(L1,L2,LL).
rotate(_,L,L).

?- rotate([1,2,3,4],[],L).
L = [[1, 2, 3, 4], [4, 1, 2, 3], [3, 4, 1, 2], [2, 3, 4, 1]]

Po prostu obraca listę i sprawdza, czy ta lista została już wstawiona na liście wyjściowa. Jeśli nie rekurencja będzie kontynuowana, w przeciwnym razie zwróci listę L. Włożyłem cięcie !, aby mieć tylko listę ze wszystkimi możliwymi obrotami. Jeśli chcesz wygenerować również inne listy, usuń go ...

Jeśli zamiast tego chcesz rozwiązać o prototypie, który zapewnisz, może to być:

rotatelist([H|T], R) :- append(T, [H], R).

all_shifts(_,[],I,I).
all_shifts(L,Result,Len,I):-
    I < Len,
    rotatelist(L,LO),
    I1 is I+1,
    all_shifts(LO,R1,Len,I1),
    append([LO],R1,Result).

?- length([1,2,3,4],L), all_shifts([1,2,3,4],R,L,1).
L = 4,
R = [[2, 3, 4, 1], [3, 4, 1, 2], [4, 1, 2, 3]]

Pomysł jest zasadniczo taki sam jak przed ... zauważ, że to drugie rozwiązanie nie jest rekurencyjne.

1
damianodamiano 23 luty 2019, 12:59