Prolog

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

您的问题的解决方案可能是：

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

简单地旋转列表并检查此列表是否已插入到输出列表中。如果不是递归继续，否则它 returns 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]]

思路和之前基本一样...注意这第二种方案不是尾递归的

Answer 2

使用 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

Prolog - 创建另一个列表的所有可能移位的列表？

Prolog - Creating a list of all the possible shifts of another list?

list

rotation