ในคณิตศาสตร์เชิงการจัด เรียง ลำดับเดอ บรูอิน (de Bruijn sequence ) อันดับn บน ตัวอักษรAขนาดkคือลำดับวัฏจักรที่สตริงความยาวn ทุก สตริง ที่เป็นไปได้ บนAปรากฏเพียงครั้งเดียวในฐานะสตริงย่อย (กล่าวคือ ในฐานะลำดับย่อยที่ต่อเนื่องกัน ) ลำดับดังกล่าวเขียนแทนด้วยB ( k , n )และมีความยาวk nซึ่งเป็นจำนวนสตริงที่แตกต่างกันที่มีความยาวnบนAสตริงที่แตกต่างกันแต่ละสตริง เมื่อนำมาเป็นสตริงย่อยของB ( k , n )จะต้องเริ่มต้นที่ตำแหน่งที่แตกต่างกัน เนื่องจากสตริงย่อยที่เริ่มต้นที่ตำแหน่งเดียวกันจะไม่แตกต่างกัน ดังนั้นB ( k , n )ต้องมี สัญลักษณ์ อย่างน้อยk n  ตัว และเนื่องจากB ( k , n )มี สัญลักษณ์ k nตัวพอดีลำดับเดอ บรูอินจึงสั้นที่สุดเมื่อพิจารณาจากคุณสมบัติที่ว่ามีสตริงความยาวn ทุกสตริง อย่างน้อยหนึ่งครั้ง

จำนวนลำดับ de Bruijn ที่แตกต่างกันB ( k , n )คือ

${\displaystyle {\dfrac {\left(k!\right)^{k^{n-1}}}{k^{n}}}.}$

สำหรับอักษรไบนารี จะได้ลำดับดังนี้สำหรับค่าบวก: 1, 1, 2, 16, 2048, 67108864... ((ลำดับA016031ในOEIS )) ${\displaystyle 2^{2^{(n-1)}-n}}$${\displaystyle n}$

ลำดับเหล่านี้ตั้งชื่อตามนักคณิตศาสตร์ชาวดัตช์Nicolaas Govert de Bruijnซึ่งเขียนเกี่ยวกับลำดับเหล่านี้ในปี 1946 ^{[ 1 ]}ดังที่เขาเขียนไว้ในภายหลัง^{[ 2 ]}การมีอยู่ของลำดับ de Bruijn สำหรับแต่ละลำดับพร้อมกับคุณสมบัติข้างต้นได้รับการพิสูจน์ ครั้งแรก สำหรับกรณีของตัวอักษรที่มีสององค์ประกอบโดย Camille Flye Sainte-Marie ( 1894 ) การขยายไปสู่ตัวอักษรที่ใหญ่กว่านั้นเป็นผลงานของTatyana van Aardenne-Ehrenfestและ de Bruijn ( 1951 ) ออโตมาตาสำหรับการจดจำลำดับเหล่านี้เรียกว่าออโตมาตา de Bruijn

ในการใช้งานหลายๆ กรณีA = {0,1}

ตัวอย่างที่เก่าแก่ที่สุดของลำดับเดอ บรูอิน (de Bruijn sequence) มาจากฉันทลักษณ์ภาษาสันสกฤตซึ่งนับตั้งแต่ผลงานของปิงคลา (Pingala ) รูปแบบสามพยางค์ที่เป็นไปได้ของพยางค์ยาวและสั้นแต่ละแบบจะได้รับชื่อเรียก เช่น 'y' สำหรับสั้น-ยาว-ยาว และ 'm' สำหรับยาว-ยาว-ยาว เพื่อช่วยในการจดจำชื่อเหล่านี้ จึงใช้คำช่วยจำว่าyamātārājabhānasalagāmซึ่งแต่ละรูปแบบสามพยางค์จะปรากฏขึ้นโดยเริ่มจากชื่อของมัน: 'yamātā' มีรูปแบบสั้น-ยาว-ยาว 'mātārā' มีรูปแบบยาว-ยาว-ยาว และอื่นๆ ไปจนถึง 'salagām' ซึ่งมีรูปแบบสั้น-สั้น-ยาว ตัวช่วยจำนี้เทียบเท่ากับลำดับ de Bruijn บนคู่ไบนารี 3 ตัว มีอายุเก่าแก่ไม่แน่ชัด แต่มีอายุอย่างน้อยเท่ากับหนังสือเกี่ยวกับฉันทลักษณ์ภาษาสันสกฤตของCharles Philip Brown ในปี 1869 ที่กล่าวถึงและถือว่าเป็น "บรรทัดโบราณที่เขียนโดย Pāṇini " ^{[ 3 ]}

ในปี พ.ศ. 2437 A. de Rivière ได้ตั้งคำถามในวารสารปัญหาภาษาฝรั่งเศสL'Intermédiaire des Mathématiciensเกี่ยวกับการมีอยู่ของการจัดเรียงแบบวงกลมของศูนย์และหนึ่งที่มีขนาดซึ่งประกอบด้วยลำดับไบนารีทั้งหมดที่มีความยาวปัญหาได้รับการแก้ไข (ในเชิงบวก) พร้อมกับการนับจำนวนคำตอบที่แตกต่างกันโดย Camille Flye Sainte-Marie ในปีเดียวกัน^{[ 2 ]}เรื่องนี้ถูกลืมไปเป็นส่วนใหญ่ และMartin (1934)ได้พิสูจน์การมีอยู่ของวงจรดังกล่าวสำหรับขนาดตัวอักษรทั่วไปแทนที่จะเป็น 2 พร้อมกับอัลกอริทึมสำหรับการสร้างวงจรเหล่านั้น ในที่สุด เมื่อในปี พ.ศ. 2487 Kees Posthumus ตั้งข้อสันนิษฐานเกี่ยวกับการนับลำดับไบนารี de Bruijn ได้พิสูจน์ข้อสันนิษฐานในปี พ.ศ. 2489 ซึ่งทำให้ปัญหานี้เป็นที่รู้จักกันดี^{[ 2 ]}${\displaystyle 2^{n}}$${\displaystyle 2^{n}}$${\displaystyle n}$${\displaystyle 2^{2^{n-1}-n}}$${\displaystyle 2^{2^{n-1}-n}}$

Karl Popperได้อธิบายวัตถุเหล่านี้โดยอิสระในหนังสือ The Logic of Scientific Discovery (1934) ของเขา โดยเรียกวัตถุเหล่านี้ว่า "ลำดับที่สั้นที่สุดที่คล้ายกับการสุ่ม" ^{[ 4 ]}

• เมื่อกำหนดให้A = {0, 1} จะมีB (2, 3) ที่แตกต่างกันสองค่า ได้แก่ 00010111 และ 11101000 โดยค่าหนึ่งเป็นค่าผกผันหรือค่าปฏิเสธของอีกค่าหนึ่ง
• ในบรรดาตัวอักษร B (2, 4) ที่เป็นไปได้ 16 ตัว มีสองตัวคือ 0000100110101111 และ 0000111101100101
• ในบรรดาตัวอักษร B (2, 5) ที่เป็นไปได้ 2048 ตัวในอักษรเดียวกัน มีสองตัวคือ 00000100011001010011101011011111 และ 00000101001000111110111001101011

ลำดับเดอ บรูอินสามารถสร้างได้โดยการใช้เส้นทางแฮมิลโท เนียน ของกราฟเดอ บรูอินnมิติเหนือ สัญลักษณ์ k ตัว (หรือเทียบเท่ากับวงจรออยเลอร์ของกราฟเดอ บรูอิน ( n  − 1) มิติ) ^{[ 5 ]}

โครงสร้างทางเลือกอีกแบบหนึ่งเกี่ยวข้องกับการนำคำศัพท์ของ Lyndonทั้งหมดที่มีความยาวหาร n ลงตัวมาต่อ กันตาม ลำดับตัวอักษร^{[ 6 ]}

สามารถใช้การแปลง Burrows–Wheelerผกผัน เพื่อสร้างคำศัพท์ Lyndon ที่ต้องการตามลำดับพจนานุกรมได้ ^{[ 7 ]}

ลำดับ de Bruijn สามารถสร้างได้โดยใช้รีจิสเตอร์เลื่อน^{[ 8 ]}หรือผ่านฟิลด์จำกัด^{[ 9 ]}

เป้าหมาย: สร้าง ลำดับ B (2, 4) de Bruijn ที่มีความยาว 2 ⁴ = 16 โดยใช้วงจรกราฟ Eulerian ( n  − 1 = 4 − 1 = 3) วงจรกราฟ 3-D de Bruijn

แต่ละขอบในกราฟเดอ บรูอินสามมิตินี้ สอดคล้องกับลำดับของตัวเลขสี่หลัก: ตัวเลขสามหลักที่ระบุจุดยอดที่ขอบนั้นออกจาก ตามด้วยตัวเลขหนึ่งหลักที่ระบุขอบนั้น หากเราเดินทางผ่านขอบที่มีหมายเลข 1 จาก 000 เราจะไปถึง 001 ซึ่งบ่งชี้ว่ามีลำดับย่อย 0001 อยู่ในลำดับเดอ บรูอิน การเดินทางผ่านแต่ละขอบเพียงครั้งเดียว หมายถึงการใช้ลำดับตัวเลขสี่หลักทั้ง 16 ลำดับเพียงครั้งเดียว

ตัวอย่างเช่น สมมติว่าเราเคลื่อนที่ตามเส้นทางออยเลอร์ต่อไปนี้ผ่านจุดยอดเหล่านี้:

000, 000, 001, 011, 111, 111, 110, 101, 011,

110, 100, 001, 010, 101, 010, 100, 000.

นี่คือลำดับเอาต์พุตที่มีความยาวk :

0 0 0 0

_ 0 0 0 1

_ _ 0 0 1 1

ซึ่งสอดคล้องกับลำดับเดอ บรูอิน ดังต่อไปนี้:

0 0 0 0 1 1 1 1 0 1 1 0 0 1 0 1

จุดยอดทั้งแปดจุดปรากฏในลำดับดังต่อไปนี้:

 {0 0 0 0} 1 1 1 1 0 1 1 0 0 1 0 1 0 {0 0 0 1} 1 1 1 0 1 1 0 0 1 0 1 0 0 {0 0 1 1} 1 1 0 1 1 0 0 1 0 1 0 0 0 {0 1 1 1} 1 0 1 1 0 0 1 0 1 0 0 0 0 {1 1 1 1} 0 1 1 0 0 1 0 1 0 0 0 0 1 {1 1 1 0} 1 1 0 0 1 0 1 0 0 0 0 1 1 {1 1 0 1} 1 0 0 1 0 1 0 0 0 0 1 1 1 {1 0 1 1} 0 0 1 0 1 0 0 0 0 1 1 1 1 {0 1 1 0} 0 1 0 1 0 0 0 0 1 1 1 1 0 {1 1 0 0} 1 0 1 0 0 0 0 1 1 1 1 0 1 {1 0 0 1} 0 1 0 0 0 0 1 1 1 1 0 1 1 {0 0 1 0} 1 0 0 0 0 1 1 1 1 0 1 1 0 {0 1 0 1} 0} 0 0 0 1 1 1 1 0 1 1 0 0 {1 0 1 ... ... 0 0} 0 0 1 1 1 1 0 1 1 0 0 1 {0 1 ... ... 0 0 0} 0 1 1 1 1 0 1 1 0 0 1 0 {1 ... 

...แล้วเราก็กลับไปยังจุดเริ่มต้น ลำดับตัวเลข 3 หลักทั้งแปดลำดับ (ซึ่งสอดคล้องกับจุดยอดทั้งแปดจุด) จะปรากฏขึ้นสองครั้ง และลำดับตัวเลข 4 หลักทั้งสิบหกลำดับ (ซึ่งสอดคล้องกับขอบทั้ง 16 เส้น) จะปรากฏขึ้นเพียงครั้งเดียว

ในทางคณิตศาสตร์การแปลง Burrows—Wheeler ผกผันบนคำwจะสร้างมัลติเซตของคลาสสมมูลที่ประกอบด้วยสตริงและการหมุนของสตริงเหล่านั้น^{[ 7 ]}คลาสสมมูลของสตริงเหล่านี้แต่ละคลาสจะมีคำ Lyndonเป็นองค์ประกอบขั้นต่ำที่ไม่ซ้ำกัน ดังนั้นการแปลง Burrows—Wheeler ผกผันจึงถือได้ว่าเป็นการสร้างเซตของคำ Lyndon สามารถแสดงได้ว่าหากเราทำการแปลง Burrows—Wheeler ผกผันบนคำwที่ประกอบด้วยตัวอักษรขนาดkที่ทำซ้ำk ^{n −1}ครั้ง (เพื่อให้ได้คำที่มีความยาวเท่ากับลำดับ de Bruijn ที่ต้องการ) ผลลัพธ์ที่ได้จะเป็นเซตของคำ Lyndon ทั้งหมดที่มีความยาวหารn ลงตัว ดังนั้นการจัดเรียงคำ Lyndon เหล่านี้ตามลำดับพจนานุกรมจะให้ลำดับ de Bruijn B ( k , n ) และนี่จะเป็นลำดับ de Bruijn แรกในลำดับพจนานุกรม สามารถใช้วิธีต่อไปนี้ในการดำเนินการแปลงผกผันของ Burrows-Wheeler โดยใช้การเรียงสับเปลี่ยนมาตรฐาน :

1. เรียงลำดับตัวอักษรในสตริงwเพื่อให้ได้สตริงใหม่w ′
2. วางสตริงw ′ไว้เหนือสตริงwแล้วจับคู่ตำแหน่งของแต่ละตัวอักษรในw ′กับตำแหน่งในwโดยคงลำดับไว้ กระบวนการนี้กำหนดการเรียงสับเปลี่ยนมาตรฐาน (Standard Permutation )
3. เขียนการเรียงสับเปลี่ยนนี้ในรูปแบบสัญกรณ์วงจรโดยให้ตำแหน่งที่เล็กที่สุดในแต่ละวงจรอยู่ลำดับแรก และเรียงลำดับวงจรจากน้อยไปมาก
4. ในแต่ละรอบ ให้แทนที่ตัวเลขแต่ละตัวด้วยตัวอักษรที่ตรงกันจากสตริงw ′ในตำแหน่งนั้น
5. แต่ละวัฏจักรได้กลายเป็นคำศัพท์ของลินดอนแล้ว และถูกจัดเรียงตามลำดับตัวอักษร ดังนั้นการตัดวงเล็บออกจะทำให้ได้ลำดับเดอ บรูอินชุดแรก

ตัวอย่างเช่น ในการสร้าง ลำดับ B (2,4) de Bruijn ที่เล็กที่สุดที่มีความยาว 2 ⁴ = 16 ให้ทำซ้ำตัวอักษร (ab) 8 ครั้ง จะได้w =ababababababababเรียงลำดับตัวอักษรในwจะได้w ′ =aaaaaaaabbbbbbbbวางw ′ไว้เหนือwดังแสดงในรูป และจับคู่แต่ละองค์ประกอบในw ′กับองค์ประกอบที่สอดคล้องกันในwโดยการลากเส้น กำหนดหมายเลขคอลัมน์ดังแสดงในรูป เพื่อให้เราสามารถอ่านวัฏจักรของการเรียงสับเปลี่ยนได้:

เริ่มจากด้านซ้าย วงจรสัญกรณ์การเรียงสับเปลี่ยนมาตรฐานคือ: (1) (2 3 5 9) (4 7 13 10) (6 11) (8 15 14 12) (16) ( การเรียงสับเปลี่ยนมาตรฐาน )

จากนั้น แทนที่ตัวเลขแต่ละตัวด้วยตัวอักษรที่ตรงกันในw ′จากคอลัมน์นั้นจะได้ผลลัพธ์ดังนี้: (a)(aaab)(aabb)(ab)(abbb)(b )

นี่คือคำศัพท์ Lyndon ทั้งหมดที่มีความยาวหาร 4 ลงตัว เรียงตามลำดับตัวอักษร ดังนั้นการตัดวงเล็บออกจะได้B (2,4) = aaaabaabbababbbb

โค้ด Pythonต่อไปนี้คำนวณลำดับ de Bruijn โดยกำหนดkและnตามอัลกอริทึมจากการสร้างเชิงผสมของFrank Ruskey ^{[ 10 ]}

จากtyping นำเข้าIterable , Any def de_bruijn ( k : Iterable [ str ] | int , n : int ) -> str : """ลำดับเดอ บรูอินสำหรับตัวอักษร k  และลำดับย่อยที่มีความยาว n  """ # อินพุตตัวอักษรสองแบบ: จำนวนเต็มจะขยาย# เป็นรายการของจำนวนเต็มเป็นตัวอักษร.. ถ้าisinstance ( k , int ): alphabet = list ( map ( str , range ( k ))) else : # ในขณะที่รายการประเภทใด ๆ จะถูกนำไปใช้ตามที่เป็นอยู่alphabet = k k = len ( k )a = [ 0 ] * k * n ลำดับ= []def db ( t , p ): if t > n : if n % p == 0 : sequence . extend ( a [ 1 : p + 1 ]) else : a [ t ] = a [ t - p ] db ( t + 1 , p ) for j in range ( a [ t - p ] + 1 , k ): a [ t ] = j db ( t + 1 , t )db ( 1 , 1 ) ส่งคืน"" . join ( alphabet [ i ] for i in sequence )พิมพ์( de_bruijn ( 2 , 3 )) พิมพ์( de_bruijn ( "abcd" , 2 ))

ซึ่งพิมพ์

00010111 aabacadbbcbdccdd 

โปรดสังเกตว่าลำดับเหล่านี้เข้าใจได้ว่า "วนรอบ" เป็นวัฏจักร ตัวอย่างเช่น ลำดับแรกประกอบด้วย 110 และ 100 ในลักษณะนี้

วงจรเดอ บรูอินมีประโยชน์โดยทั่วไปในการทดลองทางประสาทวิทยาและจิตวิทยาที่ตรวจสอบผลของลำดับการกระตุ้นต่อระบบประสาท^{[ 11 ]}และสามารถสร้างขึ้นมาเป็นพิเศษเพื่อใช้กับ^การถ่ายภาพด้วยคลื่นแม่เหล็กไฟฟ้าเชิงฟังก์ชัน [ ^{12 ]}

สัญลักษณ์ของลำดับ de Bruijn ที่เขียนรอบวัตถุทรงกลม (เช่น ล้อของหุ่นยนต์ ) สามารถใช้เพื่อระบุมุม ได้ โดยการตรวจสอบ สัญลักษณ์ nตัวที่ต่อเนื่องกันซึ่งหันหน้าเข้าหาจุดคงที่ ปัญหาการเข้ารหัสมุมนี้เรียกว่า "ปัญหาดรัมหมุน" ^{[ 13 ]}รหัส Grayสามารถใช้เป็นกลไกการเข้ารหัสตำแหน่งแบบหมุนที่คล้ายกัน ซึ่งเป็นวิธีการที่พบได้ทั่วไปในตัวเข้ารหัสแบบหมุน

ลำดับ de Bruijn สามารถใช้เพื่อค้นหาดัชนีของบิตที่ตั้งค่าที่มีนัยสำคัญน้อยที่สุด ("1 ขวาสุด") หรือบิตที่ตั้งค่าที่มีนัยสำคัญมากที่สุด ("1 ซ้ายสุด") ในคำโดยใช้การดำเนินการบิตและการคูณ^{[ 14 ]}ตัวอย่างต่อไปนี้ใช้ลำดับ de Bruijn เพื่อกำหนดดัชนีของบิตที่ตั้งค่าที่มีนัยสำคัญน้อยที่สุด (เทียบเท่ากับการนับจำนวนบิต '0' ที่ต่อท้าย) ในจำนวนเต็ม 32 บิตที่ไม่มีเครื่องหมาย :

uint8_t lowestBitIndex ( uint32_t v ) { static const uint8_t BitPositionLookup [ 32 ] = // ตารางแฮช{ 0 , 1 , 28 , 2 , 29 , 14 , 24 , 3 , 30 , 22 , 20 , 15 , 25 , 17 , 4 , 8 , 31 , 27 , 13 , 23 , 21 , 19 , 16 , 7 , 26 , 12 , 18 , 6 , 11 , 5 , 10 , 9 } ; return BitPositionLookup [(( uint32_t )(( v & - v ) * 0x077CB531U )) >> 27 ]; }

ฟังก์ชัน นี้lowestBitIndex()จะส่งคืนดัชนีของบิตที่มีค่าต่ำที่สุดในvหรือศูนย์หากvไม่มีบิตใดถูกตั้งค่า ค่าคงที่ 0x077CB531U ในนิพจน์คือ ลำดับ B (2, 5) 0000 0111 0111 1100 1011 0101 0011 0001 (เพิ่มช่องว่างเพื่อความชัดเจน) การดำเนินการนี้(v & -v)จะตั้งค่าบิตทั้งหมดเป็นศูนย์ ยกเว้นบิตที่มีค่าต่ำที่สุด ทำให้ได้ค่าใหม่ที่เป็นกำลังของ 2 กำลังของ 2 นี้จะถูกคูณ (เลขคณิตโมดูลัส 2 ³² ) ด้วยลำดับ de Bruijn ทำให้ได้ผลคูณ 32 บิต โดยที่ลำดับบิตของ 5 MSB จะมีเอกลักษณ์เฉพาะสำหรับแต่ละกำลังของ 2 5 MSB จะถูกเลื่อนไปยังตำแหน่ง LSB เพื่อสร้างรหัสแฮชในช่วง [0, 31] ซึ่งจะถูกใช้เป็นดัชนีในตารางแฮช BitPositionLookup ค่าตารางแฮชที่เลือกคือดัชนีบิตของบิตที่ตั้งค่าไว้ที่มีค่าน้อยที่สุดใน v

ตัวอย่างต่อไปนี้แสดงวิธีการหาดัชนีของบิตที่มีค่ามากที่สุดในจำนวนเต็ม 32 บิตที่ไม่มีเครื่องหมาย:

uint32_t keepHighestBit ( uint32_t n ) { n |= ( n >> 1 ); n |= ( n >> 2 ); n |= ( n >> 4 ); n |= ( n >> 8 ); n |= ( n >> 16 ); return n - ( n >> 1 ); }uint8_t highestBitIndex ( uint32_t v ) { static const uint8_t BitPositionLookup [ 32 ] = { // ตารางแฮช0 , 1 , 16 , 2 , 29 , 17 , 3 , 22 , 30 , 20 , 18 , 11 , 13 , 4 , 7 , 23 , 31 , 15 , 28 , 21 , 19 , 10 , 12 , 6 , 14 , 27 , 9 , 5 , 26 , 8 , 25 , 24 , }; return BitPositionLookup [( keepHighestBit ( v ) * 0x06EB14F9U ) >> 27 ]; }

ในตัวอย่างข้างต้น มีการใช้ลำดับเดอ บรูอินทางเลือก (0x06EB14F9U) พร้อมกับการเรียงลำดับค่าในอาร์เรย์ใหม่ที่สอดคล้องกัน การเลือกใช้ลำดับเดอ บรูอินนี้เป็นไปโดยพลการ แต่ค่าในตารางแฮชจะต้องเรียงลำดับให้ตรงกับลำดับเดอ บรูอินที่เลือกkeepHighestBit()ฟังก์ชันจะตั้งค่าบิตทั้งหมดเป็นศูนย์ ยกเว้นบิตที่มีค่ามากที่สุด ทำให้ได้ค่าที่เป็นกำลังของ 2 ซึ่งจะถูกประมวลผลต่อไปเช่นเดียวกับในตัวอย่างก่อนหน้า

ลำดับเดอ บรูอิน (de Bruijn sequence) สามารถใช้เพื่อลดระยะการโจมตีแบบบรูทฟอร์ซ (brute-force attack)บน ระบบล็อกรหัสแบบ PINที่ไม่มีปุ่ม "enter" และยอมรับ ตัวเลข n หลักสุดท้าย ที่ป้อน ตัวอย่างเช่นระบบล็อกประตูแบบดิจิทัลที่มีรหัส 4 หลัก (แต่ละหลักมี 10 ตัวเลือก ตั้งแต่ 0 ถึง 9) จะมี คำตอบ B (10, 4) คำตอบ โดยมีความยาวเท่ากับ10,000ดังนั้น อย่างมากที่สุดก็แค่เท่านั้น10,000 + 3 =ต้องกด 10,003 ครั้ง(เนื่องจากวิธีแก้ปัญหาเป็นแบบวนซ้ำ) เพื่อเปิดล็อค ในขณะที่การลองรหัสทั้งหมดแยกกันจะต้องใช้ 4 ครั้ง10,000 =​40,000 เครื่องกด

ลำดับเดอ บรูอินแบบ n-ary f เท่าเป็นส่วนขยายของแนวคิด ลำดับเดอ บรูอินแบบ n -ary โดยที่ลำดับที่มีความยาว n จะมี ลำดับย่อยที่เป็นไปได้ทั้งหมดที่มีความยาวnอยู่fครั้ง ตัวอย่างเช่น สำหรับลำดับวัฏจักร 11100010 และ 11101000 เป็นลำดับเดอ บรูอินแบบไบนารีสองเท่า จำนวนลำดับเดอ บรูอินสองเท่าสำหรับคือส่วนจำนวนอื่นๆ ที่ทราบ^{[ 16 ]}คือ, , และ ${\displaystyle fk^{n}}$${\displaystyle n=2}$${\displaystyle N_{n}}$${\displaystyle n=1}$${\displaystyle N_{1}=2}$${\displaystyle N_{2}=5}$${\displaystyle N_{3}=72}$${\displaystyle N_{4}=43768}$

ทอรัสเดอ บรูอินคืออาร์เรย์รูปทรงทอรัสที่มีคุณสมบัติว่า เมทริกซ์ k - ary m -by -n ทุกตัว จะปรากฏเพียงครั้งเดียวเท่านั้น

สามารถใช้รูปแบบดังกล่าวสำหรับการเข้ารหัสตำแหน่งสองมิติในลักษณะที่คล้ายคลึงกับที่อธิบายไว้ข้างต้นสำหรับการเข้ารหัสแบบหมุน ตำแหน่งสามารถกำหนดได้โดยการตรวจสอบ เมทริกซ์ขนาด m x nที่อยู่ติดกับเซ็นเซอร์โดยตรง และคำนวณตำแหน่งของเมทริกซ์นั้นบนทอรัสเดอ บรูอิน

การคำนวณตำแหน่งของทูเปิลหรือเมทริกซ์ที่ไม่ซ้ำกันเฉพาะในลำดับหรือทอรัสของเดอ บรูอิน เรียกว่าปัญหาการถอดรหัสเดอ บรูอิน อั ลกอริทึมการ ถอดรหัสที่${\displaystyle \color {Blue}O(n\log n)}$มีประสิทธิภาพมีอยู่สำหรับลำดับพิเศษที่สร้างขึ้นแบบเรียกซ้ำ^{[ 17 ]}และขยายไปยังกรณีสองมิติ^{[ 18 ]}การถอดรหัสเดอ บรูอินมีความน่าสนใจ เช่น ในกรณีที่ใช้ลำดับหรือทอรัสขนาดใหญ่สำหรับการเข้ารหัสตำแหน่ง

• จำนวนปกติ
• รีจิสเตอร์เลื่อนป้อนกลับเชิงเส้น
• n-ลำดับ
• ทฤษฎีบทที่ดีที่สุด
• ซูเปอร์เพอร์มิวเทชัน

• ไวส์สไตน์, เอริก ดับเบิลยู. "de Bruijn Sequence" . แมทเวิลด์ .
• ลำดับ OEIS A166315 (ลำดับไบนารีเดอบรูจินที่เล็กที่สุดในพจนานุกรม)
• ลำดับ De Bruijn เก็บถาวร 11-04-2011 ที่Wayback Machine
• เครื่องกำเนิดภาพ CGI
• ตัวสร้างแอปเพล็ต
• ตัวสร้างและถอดรหัส JavaScriptการนำอัลกอริทึมของ J. Tuliani มาใช้
• ระบบล็อคประตูด้วยรหัส
• อาร์เรย์ขั้นต่ำที่ประกอบด้วยชุดค่าผสมย่อยทั้งหมดของสัญลักษณ์: ลำดับเดอ บรูอิน และทอรัส
• http://debruijnsequence.orgมีลำดับ de Bruijn หลายประเภท