De Bruijn sequences: Difference between revisions
Content deleted Content added
Line 2,205:
return</lang>
{{out|output|text= is identical to the 1<sup>st</sup> REXX version.}} <br>
=={{header|Ruby}}==
{{trans|D}}
<lang ruby>def deBruijn(k, n)
alphabet = "0123456789"
@a = Array.new(k * n, 0)
@seq = []
def db(k, n, t, p)
if t > n then
if n % p == 0 then
temp = @a[1 .. p]
@seq.concat temp
end
else
@a[t] = @a[t - p]
db(k, n, t + 1, p)
j = @a[t - p] + 1
while j < k do
@a[t] = j # & 0xFF
db(k, n, t + 1, t)
j = j + 1
end
end
end
db(k, n, 1, 1)
buf = ""
for i in @seq
buf <<= alphabet[i]
end
return buf + buf[0 .. n-2]
end
def validate(db)
le = db.length
found = Array.new(10000, 0)
errs = []
# Check all strings of 4 consecutive digits within 'db'
# to see if all 10,000 combinations occur without duplication.
for i in 0 .. le-4
s = db[i .. i+3]
if s.scan(/\D/).empty? then
found[s.to_i] += 1
end
end
for i in 0 .. found.length - 1
if found[i] == 0 then
errs <<= (" PIN number %04d missing" % [i])
elsif found[i] > 1 then
errs <<= (" PIN number %04d occurs %d times" % [i, found[i]])
end
end
if errs.length == 0 then
print " No errors found\n"
else
pl = (errs.length == 1) ? "" : "s"
print " ", errs.length, " error", pl, " found:\n"
for err in errs
print err, "\n"
end
end
end
db = deBruijn(10, 4)
print "The length of the de Bruijn sequence is ", db.length, "\n\n"
print "The first 130 digits of the de Bruijn sequence are: ", db[0 .. 129], "\n\n"
print "The last 130 digits of the de Bruijn sequence are: ", db[-130 .. db.length], "\n\n"
print "Validating the de Bruijn sequence:\n"
validate(db)
print "\n"
db[4443] = '.'
print "Validating the overlaid de Bruijn sequence:\n"
validate(db)</lang>
{{out}}
<pre>The length of the de Bruijn sequence is 10003
The first 130 digits of the de Bruijn sequence are: 0000100020003000400050006000700080009001100120013001400150016001700180019002100220023002400250026002700280029003100320033003400350
The last 130 digits of the de Bruijn sequence are: 6898689969697769786979698769886989699769986999777787779778877897798779978787978887889789878997979887989799879998888988998989999000
Validating the de Bruijn sequence:
No errors found
Validating the overlaid de Bruijn sequence:
4 errors found:
PIN number 1459 missing
PIN number 4591 missing
PIN number 5814 missing
PIN number 8145 missing</pre>
=={{header|Visual Basic .NET}}==
|