Changes

Jump to: navigation, search

De Bruijn Sequence

424 bytes removed, 21:00, 26 January 2021
no edit summary
'''[[Main Page|Home]] * [[Programming]] * [[Data]] * De Bruijn Sequence'''
[[FILE:LW441-MC-Escher-Moebius-Strip-II-1963.jpg|border|right|thumb|link=http://www.mcescher.com/gallery/recognition-success/mobius-strip-ii/|[[Arts#Escher|M.C. Escher]] - Möbius Strip II <ref>[http://www.mcescher.com/gallery/recognition-success/ M.C. Escher - The Official Website – Recognition & Success] </ref> <ref>[https://en.wikipedia.org/wiki/M%C3%B6bius_strip Moebius Strip from Wikipedia]</ref> ]] In [https://en.wikipedia.org/wiki/Combinatorics combinatorial mathematics], a '''k'''-ary '''De Bruijn Sequence''' B(k, n) of order '''n''', named after the Dutch mathematician [[Nicolaas de Bruijn]], is a cyclic sequence of a given alphabet '''A''' with size '''k''' for which every possible subsequence of length '''n''' in '''A''' appears as a sequence of consecutive characters exactly once <ref>[https://en.wikipedia.org/wiki/De_Bruijn_sequence De Bruijn sequence from Wikipedia]</ref>. In chess programming there are applications of de Bruijn sequences with the Binary alphabet, in [[Hash Table|hashing]] sets like [[Piece-Sets]] or Square-sets, also called [[Bitboards]], most notably in [[BitScan#DeBruijnMultiplation|Bit scanning]] <ref>[[Charles Leiserson|Charles E. Leiserson]], [[Harald Prokop]], [[Keith H. Randall]] ('''1998'''). ''Using de Bruijn Sequences to Index a 1 in a Computer Word''. [http://supertech.csail.mit.edu/papers/debruijn.pdf pdf]</ref> .
=Binary alphabet=
* [https://oeis.org/A166315 A166315 - OEIS]
* [https://en.wikipedia.org/wiki/Lyndon_word Lyndon word from Wikipedia]
* [[Videos#:Category:If|If]] - [https://en.wikipedia.org/wiki/If_3 Forgotten Roads], [https://en.wikipedia.org/wiki/Beat-Club Beat-Club] [https://www.youtube.com/watch?v=V1BcLk19hVw #71], September 25, 1971, [https://en.wikipedia.org/wiki/YouTube YouTube] Video: {{#evu:https://www.youtube.com/watch?v=JFTX4cwxJLI2Hejk6KyYpk|alignment=left|valignment=top}}
=References=
<references />  '''[[Data|Up one Level]]'''[[Category:M. C. EscherIf]]

Navigation menu