プロローグで各ペア間の要素数が偶数であるリスト[1、1、2、2、...、n、n]のすべての順列を生成します

Question

最近Prologの学習を開始しました。 Lは1とNの間のすべての数が偶数である同じ要素の各対の間

、Lに正確に2回出現する長さ2N、

を有する

• ：なるようにリストLを生成述語list(N, L)他の要素の数は、
• 各番号の最初の出現は増加ordにありますエル。

N！そのようなリスト。例えば

は、N = 3のために、すべてのソリューションは、以下のとおりです。現在の最大値がある場合

• ：それは2つのことを行い

  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, [], []). 
  

  ：よう

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

  私の現在のソリューションに見えますNより小さい値をリストに追加し、重複のリストに入れ、maxを更新します。

• いくつかの重複を選択して、すでにリストにある番号と偶数の要素があるかどうかを確認します（つまり、その番号が奇数の位置にある場合）。それをリストに追加して重複から削除します。

これは動作しますが、速度が遅くて見栄えが良くありません。

この演習の著者は、N < 12の場合、平均が〜11回の推論（time/1を使用し、結果をNで除算）を持つ単一のリストを生成することを示しています。私のソリューションでは、〜60まで成長します。

1. どのようにこのアルゴリズムを改善する：

   私は2つの質問がありますか？

2. この問題は、他の既知の問題に一般化できますか？私はマルチセット[1, 1, 2, 2, ..., n, n]（Langfordペアリングなど）に基づいた同様の問題について知っていますが、このようなものは見つかりませんでした。

元の問題は、自己交差閉曲線の交差点を列挙することであるため、私は尋ねています。このようなカーブを描き、ポイントと方向を選んでカーブをたどり、最初に会ったときに各交差点を列挙し、2番目の会議で数字を繰り返す：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が使用されます。ここで

算術を回避するために編集、我々はこのより詳細なスキーマを使用することができます

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回です。 even_/1 後のすべての挿入によるフィルタリング

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

私の最初の試みは、非常に遅かったです。私は当初select/3の直後にフィルタを押すことに焦点を絞っていましたが、最後のスニペットとしてパフォーマンスは実際にはほとんど良好でしたが、残念ながら、6のうち解を失います...