3

こんにちはみんなplsは言語の誤用を許します

myPermutation（L1、L2）を作成する必要があります。リストL1（多くの連続した外観を持つ要素を含む）を指定すると、同じである2つの連続した要素がないようにソートされたL1であるリストL2が返されます）

例：リストL1 [1,1,1,1,1,2,2,3,3,4,4,5,5]が与えられた場合、L2は[1,2,1,5,1,3,1 、4,1,2,3,5,4]ランダム順列を試し、各順列の整合性をチェックしましたが、非常に低速です（12個を超える要素を持つL1の場合は約24 CPU）

唯一の可能な解決策は、順列をチェックするのではなく、一貫した順列を作成することですが、どうすればこれを行うことができますか？

それは標準的なプロローグでも実行できますが、論理プログラミングの理解が十分でないため、頭を悩ませることはできません。

ありがとう：D

4

3 に答える 3

4

リストを調べて、そのような順列を作成できます。

myPermutation([], []).
myPermutation(L, [H|P]):-
  select(H, L, NL), % Select one item from the list
  myPermutation(NL, H, P).

myPermutation([], _, []).
myPermutation(L, H, [I|P]):-
  select(I, L, NL), % Select another item
  I \= H, % Enforce restriction of no duplicate consecutive items
  myPermutation(NL, I, P).

このコードは、バックトラック時に、すべての有効な順列を提供します。重複する順列を破棄する方法を演習として残しておきます。

于 2011-04-08T17:11:57.280 に答える
4

を使用すると、これを非常に迅速に行うことができます。これによりdif/2、2つの変数が、事前にそれらの値を知らなくても、異なる値を持つように制限されます。

?- dif(X,Y).
dif(X, Y).

?- dif(X,Y), X=1.
X = 1,
dif(1, Y).

?- dif(X,Y), X=1, Y=1.
false.

これを使用して、2つの要素が同じにならないようにリストを制約する述語を作成できます。

conseq_dif([]).
conseq_dif([_]).
conseq_dif([X,Y|Xs]) :-
    dif(X,Y),
    conseq_dif([Y|Xs]).

次に、必要な制約付き順列を見つけます。

constrained_perm(Lst,Prm) :-
    length(Lst,N),
    length(Prm,N),           % make list of N unbound variables
    conseq_dif(Prm),
    permutation(Lst,Prm).    % "ordinary" (library) permutation finding

標準のPrologかどうかはわかりませんdif/2が、主要な実装にはあります。

于 2011-04-15T15:06:03.820 に答える
2

、、、 および：にmy_perm/2基づいて定義します。same_length/2list_permuted/2mapadj/2

my_perm(Xs,Ys) :-
   same_length(Xs,Ys),
   mapadj(dif,Ys),
   list_permuted(Xs,Ys).

用途の mapadj/2は、次のように定義できます。

:- meta_predicate mapadj(2,?), list_mapadj(?,2), list_prev_mapadj(?,?,2).
mapadj(P_2,Xs) :-
   list_mapadj(Xs,P_2).

list_mapadj([],_).
list_mapadj([A|As],P_2) :-
   list_prev_mapadj(As,A,P_2).

list_prev_mapadj([],_,_).
list_prev_mapadj([A1|As],A0,P_2) :-
   call(P_2,A0,A1),
   list_prev_mapadj(As,A1,P_2).

これがOPによって与えられたサンプルクエリ1、2です。

call_time/2ミリ秒単位の実行時間を測定するために使用しますT_ms。

?- call_time(my_perm([1,1,1,1,1,2,2,3,3,4,4,5,5],[1,2,1,5,1,3,1,4,1,2,3,5,4]),T_ms).
T_ms = 0.

最初のいくつかの解決策を見つけるのにどのくらい時間がかかりますか？

?- call_time(my_perm([1,2,1,5,1,3,1,4,1,2,3,5,4],Xs),T_ms).
  T_ms =  0, Xs = [1,2,1,5,1,3,1,4,1,2,3,5,4]
; T_ms =  0, Xs = [1,2,1,5,1,3,1,4,1,2,3,4,5]
; T_ms = 10, Xs = [1,2,1,5,1,3,1,4,1,2,5,3,4]
; T_ms = 10, Xs = [1,2,1,5,1,3,1,4,1,2,4,3,5]
; T_ms = 10, Xs = [1,2,1,5,1,3,1,4,1,2,5,4,3]
; T_ms = 10, Xs = [1,2,1,5,1,3,1,4,1,2,4,5,3]
; T_ms = 10, Xs = [1,2,1,5,1,3,1,4,1,3,2,5,4]
; T_ms = 20, Xs = [1,2,1,5,1,3,1,4,1,3,2,4,5]
; T_ms = 20, Xs = [1,2,1,5,1,3,1,4,1,5,2,3,4]
; T_ms = 20, Xs = [1,2,1,5,1,3,1,4,1,4,2,3,5]
; T_ms = 20, Xs = [1,2,1,5,1,3,1,4,1,5,2,4,3]
; T_ms = 20, Xs = [1,2,1,5,1,3,1,4,1,4,2,5,3]
; T_ms = 20, Xs = [1,2,1,5,1,3,1,4,1,3,5,2,4]
; T_ms = 20, Xs = [1,2,1,5,1,3,1,4,1,3,4,2,5]
; T_ms = 20, Xs = [1,2,1,5,1,3,1,4,1,5,3,2,4]
; T_ms = 20, Xs = [1,2,1,5,1,3,1,4,1,4,3,2,5]
; T_ms = 30, Xs = [1,2,1,5,1,3,1,4,1,5,4,2,3]
; T_ms = 30, Xs = [1,2,1,5,1,3,1,4,1,4,5,2,3]
...

単調に増加することに注意してくださいT_ms。これは、指定された目標を最初に呼び出してから費やされた時間を測定します。

すべてのソリューションを列挙するのにどのくらい時間がかかりますか？

?- call_time(\+((my_perm([1,1,1,1,1,2,2,3,3,4,4,5,5],_),false)),T_ms).
T_ms = 4030.

ソリューションはいくつありますか？

?- use_module(library(aggregate)),
   aggregate(count,Xs,my_perm([1,2,1,5,1,3,1,4,1,2,3,5,4],Xs),N).
N = 197664.

脚注1：SICStus Prologバージョン4.3.2（x86_64-linux-glibc2.12）を使用します。
脚注2：Prologプロセッサーによって与えられた回答シーケンスは、読みやすさのために適合されています。

于 2015-10-19T11:06:46.147 に答える