如何在 prolog 列表中三个三个地交换元素？

Question

我正在用 Prolog 做一个练习，但卡住了。我需要用另外三个元素交换列表中的三个相邻项。

即：

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

基本上这可以分成两个子问题：

首先取一个包含三个个元素的序列；和
取另一个三个元素的序列并生成我们交换这些元素的列表。

我们可以这样来实现这两个问题：

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

其中 L 是我们需要执行交换的列表，X 与结果统一的列表， S1 和 S2 序列我们 select 交换，T 第一个 selection 之后的剩余元素，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.

这里因此提出了八种方法来挑选三个相邻的序列来交换。

那么第二次swap需要在剩下的list中找三个相邻的元素进行swap，把swap1/6已经pick过的放在它pick过元素的地方，比如：

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 2

看来您对描述 RNA 序列很感兴趣。三元组，这听起来很像反密码子。为了使这些序列更具可读性，请使用：

:- set_prolog_flag(double_quotes, chars).

允许您用 "attac" 代替 [a,t,t,a,c]。请参阅 this 如何获得紧凑的答案。

现在进行交换。最简单的方法是先画出你想要的东西：

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

顺便说一句，自 1980 年代以来，dcgs 就被用于分子生物学。从

开始

David B. Searls, Investigating the Linguistics of DNA with Definite Clause Grammars, NACLP 1989

以及同一作者和 Ross Overbeek 的其他作品。所有这一切都发生在 Human Genome Project.

的黎明

Answer 3

我认为permutation/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.

注意：triples/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).

如何在 prolog 列表中三个三个地交换元素？

How to swap three by three elements in a prolog list?

swap

list

bioinformatics

prolog

dcg