如何在序言列表中交换三乘三元素？

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

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

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 = [a, t, t, c, g, g, g, c, a, a] ;
X = [t, t, g, a, c, g, g, c, a, a] ;
X = [t, g, c, a, t, c, g, g, a, a] ;
X = [g, c, a, a, t, t, c, g, g, a] ;
X = [c, a, a, a, t, t, g, c, g, g] ;
X = [c, t, t, g, g, g, a, c, a, a] ;
X = [c, t, g, c, t, g, g, a, a, a] ;
X = [c, g, c, a, t, t, g, g, a, a] ;
X = [c, c, a, a, t, t, g, g, g, a] ;
X = [c, g, t, g, c, g, a, t, a, a] ;
X = [c, g, g, c, a, t, g, a, t, a] ;
X = [c, g, c, a, a, t, g, g, a, t] ;
X = [c, g, g, g, c, a, a, t, t, a] ;
X = [c, g, g, c, a, a, g, a, t, t] ;
X = [c, g, g, a, c, a, a, t, t, g] ;
false.

这里交换的地方用黑体字表示。