de Bruijn sequences

Blitz3D Forums/Blitz3D Programming/de Bruijn sequences

virtlands

(Posted 2013) [#1]

; Hi there, I'm kind of new to this forum. My name's Andy.

; I'm fascinated by all sorts of data structures and algorithms.

; Recently I spent hours studying de Bruijn sequences.
; For reference you can read more about them on these links:

; http://www.hakank.org/comb/debruijn.cgi?k=2&n=8&submit=Ok
; http://en.wikipedia.org/wiki/De_Bruijn_sequence#De_Bruijn_decoding
;

[bbcode]
;; Trying to generate a
;; de Bruijn sequence ...
;;
;; some website sources:
;; http://www.hakank.org/comb/debruijn.cgi?k=2&n=8&submit=Ok
;; http://en.wikipedia.org/wiki/De_Bruijn_sequence#De_Bruijn_decoding
;;
;; THIS PROGRAM HAS BEEN REPLACED BY FLOYD's excellent code,
;; shown below:
;;
[/bbcode]

Last edited 2013

Floyd

(Posted 2013) [#2]

I'll leave the debugging to you. Here is a more or less direct translation of the Python code in your second link.

Using global variables k,n to replace function arguments is a little annoying. But it was either that or pass them into the recursive function db().

Graphics 800, 600, 0, 2

Dim a(0)
Dim sequence(0)
Global seqLast, k, n		; Use of Globals is not ideal, but spares me the trouble of thinking!

k = 2 : n = 3 : de_bruijn( )	; same as old de_bruijn(k, n)
k = 3 : n = 3 : de_bruijn( )

WaitKey

Function de_bruijn( )		; arguments k,n are now global variables
	Print "De Bruijn Sequence for alphabet size " + k + " and subsequences of length " + n
	Print
	Dim sequence( k^n ), a( k*n )
	seqLast = -1
	db(1,1)
	seqPrint
End Function

Function db(t, p)
	If t > n
		If (n Mod p) = 0
			For j = 1 To p
				seqLast = seqLast + 1
				sequence( seqLast ) = a(j)
			Next
		End If
	Else
			a(t) = a(t - p)
			db(t + 1, p)
			For j = a(t - p) + 1 To k - 1
				a(t) = j
				db(t + 1, t)
			Next
	End If
End Function

Function seqPrint( )
	Write "["
	For m = 0 To seqLast - 1
		Write sequence(m) + ", "
	Next
	Write sequence( seqLast ) + "]"
	Print : Print
End Function

Last edited 2013

virtlands

(Posted 2013) [#3]

That DeBruijn code you placed there is brilliant.

I don't understand python code at all, but I'm glad you translated it.

I'm certainly going to use Floyd's code now.

I just now edited and deleted that large dinosaur (code) that I
originally placed above.

Thank you Mr Floyd.

My next topics of interest will be "Gray Code", "compression", or
something like that. I'm also very interested in "HUFFMAN" algorithms.

Will be back later.

Last edited 2013

Last edited 2013