De Bruijn sequences: Difference between revisions
julia example
(+Racket) |
(julia example) |
||
Line 214:
PIN number 8145 missing
</pre>
=={{header|Julia}}==
<lang julia>function debruijn(k::Integer, n::Integer)
alphabet = b"0123456789abcdefghijklmnopqrstuvwxyz"[1:k]
a = zeros(UInt8, k * n)
seq = UInt8[]
function db(t, p)
if t > n
if n % p == 0
append!(seq, a[2:p+1])
end
else
a[t + 1] = a[t - p + 1]
db(t + 1, p)
for j in a[t-p+1]+1:k-1
a[t + 1] = j
db(t + 1, t)
end
end
end
db(1, 1)
return String([alphabet[i + 1] for i in vcat(seq, seq[1:n-1])])
end
function verifyallPIN(str, k, n, deltaposition=0)
if deltaposition != 0
str = str[1:deltaposition-1] * "." * str[deltaposition+1:end]
end
result = true
for i in 1:k^n-1
pin = string(i, pad=n)
if !occursin(pin, str)
println("PIN $pin does not occur in the sequence.")
result = false
end
end
println("The sequence does ", result ? "" : "not ", "contain all PINs.")
end
const s = debruijn(10, 4)
println("The length of the sequence is $(length(s)). The first 130 digits are:\n",
s[1:130], "\nand the last 130 digits are:\n", s[end-130:end])
print("Testing sequence: "), verifyallPIN(s, 10, 4)
print("Testing the reversed sequence: "), verifyallPIN(reverse(s), 10, 4)
println("\nAfter replacing 4444th digit with \'.\':"), verifyallPIN(s, 10, 4, 4444)
</lang>{{out}}
<pre>
The length of the sequence is 10003. The first 130 digits are:
0000100020003000400050006000700080009001100120013001400150016001700180019002100220023002400250026002700280029003100320033003400350
and the last 130 digits are:
76898689969697769786979698769886989699769986999777787779778877897798779978787978887889789878997979887989799879998888988998989999000
Testing sequence: The sequence does contain all PINs.
Testing the reversed sequence: The sequence does contain all PINs.
After replacing 4444th digit with '.':
PIN 1459 does not occur in the sequence.
PIN 4591 does not occur in the sequence.
PIN 5814 does not occur in the sequence.
PIN 8145 does not occur in the sequence.
The sequence does not contain all PINs.
</pre>
=={{header|Perl}}==
| |||