algorithm - 生成列表 [1, 1, 2, 2, ..., n, n] 的所有排列，其中每对之间的元素数在 Prolog 中为偶数

Question

我最近开始学习 Prolog，我接到了一个任务，要编写一个谓词 list(N, L) 来生成列表 L，这样:

• L 的长度为 2N，
• 1 到 N 之间的每个数字在 L 中恰好出现两次，
• 在每对相同元素之间有偶数个其他元素，
• 每个数字第一次出现的顺序是递增的。

作者说有N!这样的列表。

例如，对于 N = 3，所有解决方案都是:

?- list(3, L).
L = [1, 1, 2, 2, 3, 3] ;
L = [1, 1, 2, 3, 3, 2] ;
L = [1, 2, 2, 1, 3, 3] ;
L = [1, 2, 2, 3, 3, 1] ;
L = [1, 2, 3, 3, 2, 1] ;
L = [1, 2, 3, 1, 2, 3] ;
false.

我目前的解决方案是这样的:

even_distance(H, [H | _]) :-
   !.
even_distance(V, [_, _ | T]) :-
   even_distance(V, T).

list(N, [], _, Length, _, _) :-
   Length =:= 2*N,
   !.
list(N, [New | L], Max, Length, Used, Duplicates) :-
   select(New, Duplicates, NewDuplicates),
   even_distance(New, Used),
   NewLength is Length + 1,
   list(N, L, Max, NewLength, [New | Used], NewDuplicates).
list(N, [New | L], Max, Length, Used, Duplicates) :-
   Max < N,
   New is Max + 1,
   NewLength is Length + 1,
   list(N, L, New, NewLength, [New | Used], [New | Duplicates]).

list(N, L) :-
   list(N, L, 0, 0, [], []).

它做了两件事:

• 如果当前最大值小于N，将该数添加到列表中，将其放入重复列表中，并更新最大值；
• 选择一些重复项，检查它与列表中已有的数字之间是否有偶数个元素(即该数字在奇数位置)，然后将其添加到列表中并将其从重复项中删除。<

它可以工作，但它很慢而且看起来不太好。

这个练习的作者表明，对于 N < 12，他的解决方案生成一个列表，平均有 ~11 个推理(使用 time/1 并将结果除以 N!)。通过我的解决方案，它增长到 ~60。

我有两个问题:

1. 如何改进这个算法？
2. 能否将此问题推广到其他已知问题？我知道基于多重集 [1, 1, 2, 2, ..., n, n](例如 Langford 配对)的类似问题，但找不到类似的问题。

我问是因为最初的问题是关于枚举自相交闭合曲线中的交点。您绘制这样的曲线，选择一个点和方向并沿着曲线行驶，在第一次相遇时枚举每个交叉点并在第二次相遇时重复数字:example (答案为 [1, 2, 3, 4, 5, 3, 6, 7, 8, 1, 9, 5, 4, 6, 7, 9, 2, 8])。

作者声明每条这样的曲线都满足谓词 list，但并非每个列表都对应一条曲线。

Answer 1

我不得不求助于算术来满足关于由偶数个元素分隔的整数对的要求。如果完全不用算术就能解决问题就好了……

list(N,L) :- numlist(1,N,H), list_(H,L), even_(L).list_([D|Ds],[D|Rs]) :-    list_(Ds,Ts),    select(D,Rs,Ts).list_([],[]).even_(L) :-    forall(nth0(P,L,X), (nth0(Q,L,X), abs(P-Q) mod 2 =:= 1)).

select/3 is used in 'insert mode'.

edit to avoid arithmetic, we could use this more verbose schema

even_(L) :-
    maplist(even_(L),L).
even_(L,E) :-
    append(_,[E|R],L),
    even_p(E,R).
even_p(E,[E|_]).
even_p(E,[_,_|R]) :- even_p(E,R).

编辑

这是一个基于空“槽”的预建列表中分配的片段。根据我的测试，它比您的解决方案快 - 大约 2 倍。

list(N,L) :-
    N2 is N*2,
    length(L,N2),
    numlist(1,N,Ns),
    pairs(Ns,L).

pairs([N|Ns],L) :- first(N,L,R),even_offset(N,R),pairs(Ns,L).
pairs([],_).

first(N,[N|R],R) :- !.
first(N,[_|R],S) :- first(N,R,S).

even_offset(N,[N|_]).
even_offset(N,[_,_|R]) :- even_offset(N,R).

我的第一次尝试是在每次插入后使用 even_/1 进行过滤，但速度要慢得多。我最初专注于在 select/3 之后立即推送过滤器，并且性能确实与最后一个片段几乎一样好，但是，唉，它失去了 6 的解决方案......