길이가 N 인 모든 개별 비트 패턴을 가져 와서 각 패턴이 N - 1 비트의 두 이웃과 겹치도록 주기로 배열합니다. 그런 다음 주기를 Prolog 목록으로 전개하십시오.프롤로그의 패턴
위의 규칙에 따라 길이가 N> 0 인 모든 비트 패턴을 포함하는 비트 목록을 반환하는 조건자인 pattern(N,L)을 작성하십시오. 여러 개의 가능한 솔루션이 있습니다. 하나만 생산하면됩니다.
?- 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 구현의 경우, 비트가 목록의 시작 부분에 추가되는 경우가 아니라 끝 부분에 항목이 추가되는 것이 가장 쉽습니다. 어쨌든 나는 그것을 시도해 볼 것이고 그것이 희망을 품을 때 좋게 작동한다면 당신에게 알려줄 것입니다.
또 다른 좋은 연습은 difference list 기술을 사용하여 시퀀스 끝에 비트를 추가하는 코드를 작성하는 것입니다.
라이트 (코드) 여기서
는 복용리스트의 전방에 항목을 추가하여 드 브루 인 순서를 나타내는 목록을 작성 구현 결정적 술어 binaryDeBruijnSeq/2있어 패턴 길이 양의 정수 N을 (구속)와 두 번째 인수로 말했다리스트를 돌려 : 여기
/*
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 시퀀스] (http://en.wikipedia.org/wiki/De_Bruijn_sequence)라고하지 않습니까? 주기를 생성하거나 목록을 병합하는 데 문제가 있습니까? – hardmath