Прокручивая список, пока не найду правильную последовательность?

Question

Мне нужно перебирать список в Прологе, пока не появится правильная последовательность.В этом случае последовательность идет "u" "r" "d" "l".Списки будут состоять только из этих символов.У меня уже есть метод, который возвращает список всех возможных циклов, например, такой:

?- all_cases(["l", "u", "r", "d"], S).
S = [["l", "u", "r", "d"], ["u", "r", "d", "l"], ["r", "d", "l", "u"], ["d", "l", "u", "r"]].

Как видите, второй список находится в нужном мне порядке.Теперь проблема в том, что мне нужно пройти по этому списку (S), пока я не найду тот, который мне нужен.Конечный результат должен выглядеть следующим образом.«Циклический сдвиг» - это правильный вывод, а «Что» содержит все сдвиги.

 all_cases(["u","r","r","d","d","l","l","u"],What),try_all_sqA(What).
 cyclic shift: ["u","u","r","r","d","d","l","l"] is correct
 What = [["u", "r", "r", "d", "d", "l", "l", "u"], ["r", "r", "d", "d", "l", "l", "u"|...], ["r", "d", "d", "l", "l", "u"|...], ["d", "d", "l", "l", "u"|...], ["d", "l", "l", "u"|...], ["l", "l", "u"|...], ["l", "u"|...]["u"|...]].

Я уже пробовал сортировать / 4 , но это только дает мне списокв алфавитном или обратном алфавитном порядке, и мне нужно отсортировать его по уникальной последовательности (u, r, d, l).

Answer 1

Хорошо, давайте разберем проблему на более мелкие части.Сначала мы создадим предикат, который соответствует элементам списка, пока список не будет исчерпан или пока он не достигнет элемента, который больше не является искомым элементом, мы можем реализовать это с помощью предиката seq/3:

seq([], _, []).
seq([H|T], H, R) :-
    seq(T, H, R).
seq([H|T], X, [H|T]) :-
    dif(H, X).

Например:

?- seq(["u", "r", "d", "l"], "u", R).
R = ["r", "d", "l"] ;
false.

?- seq(["u", "r", "d", "l"], "r", R).
R = ["u", "r", "d", "l"].

Это означает, что мы можем проверить, что последовательность имеет ноль или более "u" с, затем ноль или более "r" с, а затем нольили больше "d" с и, наконец, ноль или более "l" с:

sequrdl(LA) :-
    seq(LA, "u", LB),
    seq(LB, "r", LC),
    seq(LC, "d", LD),
    seq(LD, "l", []).

Например:

?- sequrdl(["u","u","r","r","d","d","l","l"]).
true ;
false.

?- sequrdl(["u","u","r","r","d","d","l","l", "u"]).
false.

?- sequrdl(["u","u","r","r","d","d"]).
true ;
false.

Так что теперь нам нужно искать только до тех пор, поканайдите повернутый список, для которого это выполняется, и затем мы можем напечатать этот список, например:

try_all_sqA(What) :-
    member(SubList, What),
    sequrdl(SubList),
    print('cyclic shift: '),
    print(SubList),
    nl.

Например:

?- try_all_sqA([["l", "u", "r", "d"], ["u", "r", "d", "l"], ["r", "d", "l", "u"], ["d", "l", "u", "r"]]).
'cyclic shift: '["u","r","d","l"]
true ;
false.