長さNのすべての異なるビットパターンを取り、それぞれのパターンがN - 1ビットの2つの近隣ノードと重複するようにサイクル内に配置します。その後、 サイクルをPrologリストにフラット化します。プロローグ内のパターン
上記の規則に従って長さN> 0のビット のすべてのビットを含むビットのリストを返す述語pattern(N,L)を記述します。複数の可能な解決法があることに注意してください。あなたは1つだけを生産する必要があります。これらを生成するため
?- pattern(1, L).
L = [0,1]
?- pattern(2, L).
L = [0,0,1,1]
?- pattern(3, L).
L = [0,0,0,1,1,1,0,1]
ニート方法はアバスAlkahimによってA Simple Combinatorial Algorithm for De Bruijn Sequencesで与えられます。
これはおそらくマイナーな適応を伴うPrologの実装に適しています。パターン長Nのために次のようにザ・アルゴリズム向かい優先彼のメソッドを呼び出す、説明された手順は次のとおり
これは、長さNのすべてのバイナリパターン、 N 1のパターン以外を含むシーケンスをもたらす、及びN-1のN-1 0が続くパターンで終了します。完全なDe Bruijnシーケンスを得るには、それらの最終N-1 0を単一の1つのエントリに置き換えます（シーケンスはそのポイントで長さ2^Nのサイクルにラップアラウンドする必要があります）。
Prologの実装では、ビットが最後ではなくリストの先頭に追加されれば、最も簡単に処理が進むと思われます。とにかく私はそれを試してみると、それがうまくいくかどうか私はそれが望むように動作するかどうかをお知らせします。
私が最初に反対のパリティビットをしようと、リストの先頭にビットを追加して、最後の夜私のコードを書き、今朝それをテストしました。 N = 1の場合はちょっと変わったように見え、N> 1の場合と同じようにコードする努力の後、N = 1の場合[1,0]を返すだけに戻った。
もう一つの良い練習は、difference list技術を使ってシーケンスの最後にビットを追加するコードを書くことです。
を追加しました：（コード）
ここではリストの先頭にエントリを追加することによって、デBruijnグラフのシーケンスを表すリストを構築する実装の、決定論的述語binaryDeBruijnSeq/2取りますパターン長さの正の整数Nと第2引数として前記リストを返す：
/*
Prolog implementation of PreferOpposite
"A Simple Combinatorial Algorithm
for De Bruijn Sequences"
by Abbas Alkahim:
http://duch.mimuw.edu.pl/~rytter/TEACHING/TEKSTY/PreferOpposite.pdf
Construct binary De Bruijn sequence for all N bit patterns
(a list construed as cycle) by adding to front of list:
1. If N = 1, return [1,0]; otherwise begin the sequence
with N zeros.
2. For next bit, first try one of parity opposite to the
previous one, then try one of the same parity, so that
an N bit pattern not already found results. Repeat.
3. When no further bits can be added, the final N-1 bits
will be zeros. Replace them with a single one bit.
*/
binaryDeBruijnSeq(1,[1,0]).
binaryDeBruijnSeq(N,[1|ZeroStrip]) :-
N > 1,
zeroNFill(N,ZeroNBits),
accrueDeBruijn(ZeroNBits,ZeroNBits,Accrue),
zeroStrip(Accrue,ZeroStrip).
zeroNFill(0,[ ]).
zeroNFill(N,[0|Fill]) :-
N > 0,
M is N-1,
zeroNFill(M,Fill).
accrueDeBruijn(NBits,SoFar,Final) :-
NBits = [Bit|_],
shorten(NBits,Short),
Opp is 1 - Bit,
not(alreadyFound([Opp|Short],SoFar)),
!,
accrueDeBruijn([Opp|Short],[Opp|SoFar],Final).
accrueDeBruijn(NBits,SoFar,Final) :-
NBits = [Bit|_],
shorten(NBits,Short),
not(alreadyFound([Bit|Short],SoFar)),
!,
accrueDeBruijn([Bit|Short],[Bit|SoFar],Final).
accrueDeBruijn(_,Final,Final).
shorten([_],[ ]) :- !.
shorten([H|T],[H|S]) :- shorten(T,S).
/* alreadyFound(NBits,DeBruijn) */
alreadyFound(NBits,DeBruijn) :-
initialSeq(NBits,DeBruijn).
alreadyFound(NBits,[_|DeBruijn]) :-
alreadyFound(NBits,DeBruijn).
initialSeq([ ],_).
initialSeq([H|T],[H|L]) :-
initialSeq(T,L).
zeroStrip([0|T],S) :- !, zeroStrip(T,S).
zeroStrip(S,S).
私のフォローアップエクササイズのコードもありますが、 パターン/ 2は、テールに追加してリストを作成します。
/* follow-up, build De Bruijn sequence by adding to tail */
pattern(1,[0,1]).
pattern(N,DeBruijn) :-
N > 1,
zeroNFront(N,[1|X],DeBruijn),
DeBruijn = [0|NBits],
patternAux(N,DeBruijn,NBits,[1|X],1),
!.
zeroNFront(0,Last,Last).
zeroNFront(N,List,Last) :-
N > 0,
M is N-1,
zeroNFront(M,[0|List],Last).
patternAux(N,DeBruijn,_,[1,1],C) :-
C is N-1,
!.
patternAux(N,DeBruijn,NBits,[Bit|X],C) :-
Opp is 1-Bit,
X = [Opp|Y],
NBits = [_|MBits],
not(alreadyFoundAux(DeBruijn,MBits,Y)),
patternAux(N,DeBruijn,MBits,[Opp|Y],Opp).
patternAux(N,DeBruijn,NBits,[Bit|X],C) :-
X = [Bit|Y],
NBits = [_|MBits],
(Bit = 1 -> D is C+1 ; D = 0),
patternAux(N,DeBruijn,MBits,[Bit|Y],D).
alreadyFoundAux(L,L,[ ]) :- !, fail.
alreadyFoundAux(K,L,[ ]) :-
initialSeq(L,K).
alreadyFoundAux([_|K],L,Y) :-
alreadyFoundAux(K,L,Y).
注：偶数/ 2上方から再利用されるinitialSeq を述語事実を占め、結果として得られる実装がやや小型で同じNについて/ 2はbinaryDeBruijnSeqなりの結果パターン/ 2の逆のリスト。
これは宿題のように見えます。あなたは何をしていましたか、どこにいらっしゃいましたか、あなたの質問は何ですか？ –
[De Bruijn sequences]（http://en.wikipedia.org/wiki/De_Bruijn_sequence）と呼ばれていませんか？サイクルの生成やリストへのフラット化に問題がありますか？ – hardmath