生成列表[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,则将该数字添加到列表中,将其放在重复列表中,然后更新max;
• 选择一些副本,检查它与列表中已有的数字之间是否有偶数个元素(即该数字位于奇数位置),然后将其添加到列表中并从重复项中删除.

它有效,但它很慢,看起来不太好.

本练习的作者表明,对于N <12,他的解决方案生成一个平均约有11个推断的单个列表(使用time/1并将结果除以N!).随着我的解决方案,它增长到~60.

我有两个问题:

1. 如何改进这个算法？
2. 这个问题可以推广到其他已知问题吗？我知道基于multiset的类似问题[1, 1, 2, 2, ..., n, n](例如Langford配对),但找不到这样的东西.

我问,因为最初的问题是关于在自相交的闭合曲线中枚举交点.您绘制这样的曲线,选择一个点和方向并跟随曲线,在第一次遇到时枚举每个交叉点并在第二次会议上重复该数字:示例(带答案[1, 2, 3, 4, 5, 3, 6, 7, 8, 1, 9, 5, 4, 6, 7, 9, 2, 8]).

作者指出,每条这样的曲线都满足谓词list,但不是每个列表都对应一条曲线.

Answer 1

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

列表（N，L）：- numlist（1，N，H），list_（H，L），even_（L）。

list_([D|Ds],[D|Rs]) :-
    列表_(Ds,Ts),
    选择（D，Rs，Ts）。
列表_（[]，[]）。

偶_（L）：-
    forall（nth0（P，L，X），（nth0（Q，L，X），abs（PQ）mod 2 =：= 1））。

select/3 用于“插入模式”。

编辑以避免算术，我们可以使用这个更详细的模式

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 个解决方案......