Пролог - Создание списка всех возможных смен другого списка?

Question

Для моего задания мне нужно создать список всех возможных сдвигов (поворотов) другого списка в прологе.Например,

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]].

В настоящее время у меня есть программа, которая сдвигает ее влево один раз.

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

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

Однако мне нужно создать другую программу, в которой конечный результат (R) содержит все возможные смены.Рекурсия в прологе действительно начинает смущать меня, но я почти уверен, что это необходимо.Любая помощь будет очень признательна.

Answer 1

Сохраняйте логическую чистоту, используя same_length/2 и 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).

Пример запроса:

?- list_rotations([A,B,C,D], Xss).
Xss = [[B,C,D,A],
         [C,D,A,B],
           [D,A,B,C]].           % succeeds deterministically

Answer 2

Решением вашей проблемы может быть:

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]]

Просто поворачивает список и проверяет, был ли этот список уже вставлен в список вывода.Если не рекурсия продолжается, в противном случае она возвращает список в L.Я вставил вырез !, чтобы иметь только список со всеми возможными поворотами.Если вы хотите сгенерировать и другие списки, просто удалите его ...

Если вместо этого вам нужно решение с предоставленным вами прототипом, оно может быть:

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]]

Идея в основном заключается втак же, как и раньше ... Обратите внимание, что это второе решение не является хвостовой рекурсивной.