72 lines
1.7 KiB
Ruby
72 lines
1.7 KiB
Ruby
def de_bruijn(k, n)
|
|
# de Bruijn sequence for alphabet k and subsequences of length n
|
|
alphabet = if k.is_a?(Integer)
|
|
(0...k).map(&:to_s)
|
|
else
|
|
k.chars
|
|
end
|
|
k = alphabet.size
|
|
a = Array.new(k * n, 0)
|
|
sequence = []
|
|
|
|
def db(t, p, a, k, n, sequence)
|
|
if t > n
|
|
sequence.concat(a[1..p]) if n % p == 0
|
|
else
|
|
a[t] = a[t - p]
|
|
db(t + 1, p, a, k, n, sequence)
|
|
(a[t - p] + 1...k).each do |j|
|
|
a[t] = j
|
|
db(t + 1, t, a, k, n, sequence)
|
|
end
|
|
end
|
|
end
|
|
|
|
db(1, 1, a, k, n, sequence)
|
|
sequence.map { |i| alphabet[i] }.join
|
|
end
|
|
|
|
def validate(db)
|
|
dbwithwrap = db + db[0, 3]
|
|
digits = '0123456789'
|
|
errorstrings = []
|
|
|
|
digits.chars.each do |d1|
|
|
digits.chars.each do |d2|
|
|
digits.chars.each do |d3|
|
|
digits.chars.each do |d4|
|
|
teststring = d1 + d2 + d3 + d4
|
|
errorstrings << teststring unless dbwithwrap.include?(teststring)
|
|
end
|
|
end
|
|
end
|
|
end
|
|
|
|
if errorstrings.any?
|
|
puts " #{errorstrings.size} errors found:"
|
|
errorstrings.each { |e| puts " PIN number #{e} missing" }
|
|
else
|
|
puts " No errors found"
|
|
end
|
|
end
|
|
|
|
db = de_bruijn(10, 4)
|
|
puts ""
|
|
puts "The length of the de Bruijn sequence is #{db.length}"
|
|
puts ""
|
|
puts "The first 130 digits of the de Bruijn sequence are: #{db[0, 130]}"
|
|
puts ""
|
|
puts "The last 130 digits of the de Bruijn sequence are: #{db[-130..-1]}"
|
|
puts ""
|
|
puts "Validating the deBruijn sequence:"
|
|
validate(db)
|
|
|
|
dbreversed = db.reverse
|
|
puts ""
|
|
puts "Validating the reversed deBruijn sequence:"
|
|
validate(dbreversed)
|
|
|
|
dboverlaid = db[0, 4443] + '.' + db[4444..-1]
|
|
puts ""
|
|
puts "Validating the overlaid deBruijn sequence:"
|
|
validate(dboverlaid)
|