Как поменять три на три элемента в списке пролога?

Question

Я делаю упражнение в Прологе и застрял. Мне нужно поменять три соседних элемента в списке с другими тремя элементами.

То есть:

| ?- swap([c,g,g,a,t,t,g,c,a,a], X).

X = [a,t,t,c,g,g,g,c,a,a]
X = [g,c,a,a,t,t,c,g,g,a]
X = [c,g,g,g,c,a,a,t,t,a]
X = [c,a,a,a,t,t,g,c,g,g]
.
.
.

Это то, что у меня есть:

swap([H1, H2, H3, H4, H5, H6|T1], X) :-
     X = [H4, H5, H6, H1, H2, H3|T1];
     swap([H2, H3, H4, H5, H6|T1], X);
     swap([H1, H2, H3, H4, H5|T1], X).

И вывод для этого:

| ?- swap([c,g,g,a,t,t,g,c,a,a], X).

X = [a, t, t, c, g, g, g, c, a, a] ;
X = [t, t, g, g, g, a, c, a, a] ;
X = [t, g, c, g, a, t, a, a] ;
X = [g, c, a, a, t, t, a] ;
X = [c, a, a, t, t, g] ;
X = [c, a, a, a, t, t] ;
X = [g, c, a, g, a, t, a] ;
X = [c, a, a, a, t, g] ;
X = [c, a, a, g, a, t] ;
X = [t, g, c, g, g, a, a, a] ;
X = [g, c, a, g, a, t, a] ;
X = [c, a, a, a, t, g] ;
X = [c, a, a, g, a, t] ;
X = [g, c, a, g, g, a, a] ;
X = [c, a, a, g, a, g] ;
X = [c, a, a, g, g, a] ;
X = [t, t, g, c, g, g, c, a, a] ;
X = [t, g, c, g, g, t, a, a] ;
X = [g, c, a, g, t, t, a] ;
X = [c, a, a, t, t, g] ;
X = [c, a, a, g, t, t] ;
X = [g, c, a, g, g, t, a] ;
X = [c, a, a, g, t, g] ;
X = [c, a, a, g, g, t] ;
X = [t, g, c, c, g, g, a, a] ;
X = [g, c, a, g, g, t, a] ;
X = [c, a, a, g, t, g] ;
X = [c, a, a, g, g, t] ;
X = [g, c, a, c, g, g, a] ;
X = [c, a, a, g, g, g] ;
X = [c, a, a, c, g, g] ;
false.

Единственная проблема, которую я имею, состоит в том, что с каждой рекурсией я теряю некоторую часть списка и не знаю, как ее вернуть.

Answer 1

Кажется, вы заинтересованы в описании РНК-последовательностей. Тройки, это очень похоже на антикодоны. Чтобы сделать эти последовательности более читабельными, используйте:

:- set_prolog_flag(double_quotes, chars).

, что позволяет писать "attac" вместо [a,t,t,a,c]. См. этот , как получить также компактные ответы.

Теперь для обмена. Самый простой способ - сначала набросать то, что вы хотите:

... Triple1 ... Triple2 ...  is the OldSequence

... Triple2 ... Triple1 ...  is the NewSequence

Где ... одинаковы для обеих последовательностей. Все это можно легко перевести с помощью DCG.

tripleswap(OldSequence, NewSequence) :-
   dif(T1,T2),
   phrase( ( seq(A), triple(T1), seq(B), triple(T2), seq(C) ), OldSequence),
   phrase( ( seq(A), triple(T2), seq(B), triple(T1), seq(C) ), NewSequence).

seq([]) --> [].
seq([B|Bs]) --> [B], seq(Bs).

triple([A,B,C]) --> [A,B,C].

Всякий раз, когда вы не доверяете определению DCG, просто попробуйте его с помощью phrase/2. Как и

?- phrase(triple(T1), Bs).
T1 = Bs, Bs = [_A,_B,_C].

Нетерминал triple//1 описывает последовательность из 3 элементов (предположительно нуклеотидов).

seq//1 - произвольно длинная последовательность.

Там являются решениями с лучшими условиями завершения, но они менее читабельны и часто требуют определенных допущений, которые трудно поддерживать в общем случае. Вот такое простое улучшение:

samelength([], []).
samelength([_|Xs], [_|Ys]) :-
   samelength(Xs, Ys).

и добавьте samelength(OldSequence, NewSeqence) в качестве первой цели. Теперь tripleswap/2 завершается, если samelength/2 завершается. Поэтому одним из аргументов должен быть список фиксированной длины.

Также обратите внимание, что я думаю, что "cccccc" не имеет подкачки. Вот почему я добавил dif(T1,T2).

?- tripleswap("cggattgcaa", Bs).
      Bs = "attcgggcaa"
   ;  Bs = "ttgacggcaa"
   ;  Bs = "tgcatcggaa"
   ;  Bs = "gcaattcgga"
   ;  Bs = "caaattgcgg"
   ;  Bs = "cttgggacaa"
   ;  Bs = "ctgctggaaa"
   ;  Bs = "cgcattggaa"
   ;  Bs = "ccaattggga"
   ;  Bs = "cgtgcgataa"
   ;  Bs = "cggcatgata"
   ;  Bs = "cgcaatggat"
   ;  Bs = "cgggcaatta"
   ;  Bs = "cggcaagatt"
   ;  Bs = "cggacaattg"
   ;  false.

Кстати, dcg s используются в молекулярной биологии с 1980-х годов. Начните с

Дэвида Б. Сирлса, «Изучение лингвистики ДНК с помощью грамматики с определенным предложением», NACLP 1989

и других работ того же автора, а также Росса Овербика вокруг то время. Все это произошло на заре проекта Геном человека .

Answer 2

В основном это можно разделить на две подзадачи:

1. сначала взять последовательность из трех элементов; и
2. взять другую последовательность из трех элементов и создать список, в котором мы их поменяли.

Таким образом, мы можем реализовать две проблемы следующим образом:

swap(L, X) :-
    swap1(L, S1, S2, T, X, Q),
    swap2(T, S1, S2, Q).

где L - это список, в котором нам нужно выполнить обмен, X список, объединенный с результатами, S1 и S2 последовательности, которые мы выбираем для обмена, T остальные элементы после первый выбор и Q часть после второй последовательности списка для замены.

Первый swap1, таким образом, может быть реализован как:

swap1([A1, A2, A3|T], [A1, A2, A3], [B1, B2, B3], T, [B1, B2, B3|Q], Q).
swap1([A1|T], A, B, R, [A1|Rest], S) :-
    swap1(T, A, B, R, Rest, S).

Для данного списка образцов таким образом, это приведет к:

?- swap1([c,g,g,a,t,t,g,c,a,a], A, [B1, B2, B3], T, X, R).
A = [c, g, g],
T = [a, t, t, g, c, a, a],
X = [B1, B2, B3|R] ;
A = [g, g, a],
T = [t, t, g, c, a, a],
X = [c, B1, B2, B3|R] ;
A = [g, a, t],
T = [t, g, c, a, a],
X = [c, g, B1, B2, B3|R] ;
A = [a, t, t],
T = [g, c, a, a],
X = [c, g, g, B1, B2, B3|R] ;
A = [t, t, g],
T = [c, a, a],
X = [c, g, g, a, B1, B2, B3|R] ;
A = [t, g, c],
T = [a, a],
X = [c, g, g, a, t, B1, B2, B3|R] ;
A = [g, c, a],
T = [a],
X = [c, g, g, a, t, t, B1, B2, B3|...] ;
A = [c, a, a],
T = [],
X = [c, g, g, a, t, t, g, B1, B2|...] ;
false.

Здесь, таким образом, предлагается восемь способов выбора трех смежных последовательностей, которые можно использовать для обмена.

Затем при втором обмене необходимо найти три соседних элемента в остальные списки, которые нужно поменять местами, и поместить те, которые были выбраны swap1/6, в места, из которых он выбирает элементы, например:

swap2([B1,B2,B3|R], [A1,A2,A3], [B1, B2, B3], [A1,A2,A3|R]).
swap2([B1|R], As, Bs, [B1|T]) :-
    swap2(R, As, Bs, T).

Для данных данного примера это дает нам:

?- swap([c,g,g,a,t,t,g,c,a,a], X).
X = [<b><i>a, t, t, c, g, g</i></b>, g, c, a, a] ;
X = [<b><i>t, t, g</i></b>, a, <b><i>c, g, g</i></b>, c, a, a] ;
X = [<b><i>t, g, c</i></b>, a, t, <b><i>c, g, g</i></b>, a, a] ;
X = [<b><i>g, c, a</i></b>, a, t, t, <b><i>c, g, g</i></b>, a] ;
X = [<b><i>c, a, a</i></b>, a, t, t, g, <b><i>c, g, g</i></b>] ;
X = [c, <b><i>t, t, g, g, g, a</i></b>, c, a, a] ;
X = [c, <b><i>t, g, c</i></b>, t, <b><i>g, g, a</i></b>, a, a] ;
X = [c, <b><i>g, c, a</i></b>, t, t, <b><i>g, g, a</i></b>, a] ;
X = [c, <b><i>c, a, a</i></b>, t, t, g, <b><i>g, g, a</i></b>] ;
X = [c, g, <b><i>t, g, c, g, a, t</i></b>, a, a] ;
X = [c, g, <b><i>g, c, a</i></b>, t, <b><i>g, a, t</i></b>, a] ;
X = [c, g, <b><i>c, a, a</i></b>, t, g, <b><i>g, a, t</i></b>] ;
X = [c, g, g, <b><i>g, c, a, a, t, t</i></b>, a] ;
X = [c, g, g, <b><i>c, a, a</i></b>, g, <b><i>a, t, t</i></b>] ;
X = [c, g, g, a, <b><i>c, a, a, t, t, g</i></b>] ;
false.

Здесь поменялись местами жирным шрифтом.

Answer 3

Я думаю, что перестановка / 2 поможет:

swap(Es,Sw) :- triples(Es,Ts),permutation(Ts,Sw0),append(Sw0,Sw).

triples([A,B,C|Es],[[A,B,C]|Ts]) :- !, triples(Es,Ts).
triples([],[]) :- !.
triples(R,[R]).

урожайность

?- swap([c,g,g, a,t,t, g,c,a], X).
X = [c, g, g, a, t, t, g, c, a] ;
X = [c, g, g, g, c, a, a, t, t] ;
X = [a, t, t, c, g, g, g, c, a] ;
X = [a, t, t, g, c, a, c, g, g] ;
X = [g, c, a, c, g, g, a, t, t] ;
X = [g, c, a, a, t, t, c, g, g] ;
false.

примечание: тройки / 2 допускают не тройные данные в хвосте, но вы можете отбросить это (возможно нежелательные) функция, просто удаляющая последнее предложение:

triples(R,[R]). % drop this

Тогда сокращения становятся бесполезными, просто бросьте их:

triples([],[]). % just for style in this case, move to first clause
triples([A,B,C|Es],[[A,B,C]|Ts]) :- triples(Es,Ts).