0

取所有长度为 N 的不同位模式，并将它们排列在一个循环中，以使每个模式与 N - 1 位中的两个相邻模式重叠。然后将循环扁平化为 Prolog 列表。

编写一个谓词pattern(N,L)，返回一个包含所有长度为 N > 0 的位模式的位列表，遵循上述规则。请注意，有多种可能的解决方案。你只需要生产一个。

?- 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]
4

1 回答 1

1

Abbas Alkahim在A Simple Combinatorial Algorithm for De Bruijn Sequences中给出了生成这些的简洁方法。

它可能适用于稍作调整的 Prolog 实现。将他的方法称为 Prefer Opposite Algorithm，对于模式长度 N，概述的步骤如下：

  1. 将列表的前 N ​​个“位”设置为 0。
  2. 对于下一个“位”，考虑与前一个相反的奇偶校验位。
  3. 如果生成的 N 位模式以前不存在于列表中，则将该位连接到列表的末尾并继续。（返回第 2 步）
  4. 另一方面，如果该模式确实存在，请尝试下一个与前一个相等的奇偶校验位。
  5. 如果该 N 位模式不存在，则将该位连接到列表的末尾并继续。（返回步骤 2）。
  6. 否则停止。

这导致一个序列包含长度为 N 的所有二进制模式，除了N 1 的模式，并以 N-1 1 后跟 N-1 0 的模式结束。要获得完整的 De Bruijn 序列，请将最后的 N-1 个 0 替换为单个 1 条目（并且该序列应在该点环绕到长度为 2^N 的循环）。

对于 Prolog 实现，我怀疑如果将位添加到列表的开头而不是末尾，事情会最容易进行。不管怎样，我会试一试，让你知道它是否能像我希望的那样工作。

我昨晚写了我的代码，今天早上测试了它，首先尝试相反的奇偶校验位，然后将位添加到列表的开头。N = 1 的情况看起来有点反常，在努力编写与 N > 1 相同的代码后，我回到只返回 N = 1 的 [1,0]。

另一个很好的练习是使用差异列表技术编写将位添加到序列末尾的代码。

补充：（代码）

这是一个实现，它通过在列表的前面添加条目来构建表示 De Bruijn 序列的列表，确定性谓词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).

这也是我的后续练习的代码，pattern/2通过添加到尾部来构建列表。即使考虑到从上面重用谓词initialSeq/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).

注意：对于相同的 N，binaryDeBruijnSeq/2的结果将是pattern/2的反向列表。

于 2012-05-15T16:24:01.963 回答