De Bruijn sequences: Difference between revisions
Add CLU
JsfasdF256 (talk | contribs) No edit summary |
Not a robot (talk | contribs) (Add CLU) |
||
Line 930:
PIN number 5814 missing
PIN number 8145 missing</pre>
=={{header|CLU}}==
<lang clu>% Generate the De Bruijn sequence consisiting of N-digit numbers
de_bruijn = cluster is generate
rep = null
own k: int := 0
own n: int := 0
own a: array[int] := array[int]$[]
own seq: array[int] := array[int]$[]
generate = proc (k_, n_: int) returns (string)
k := k_
n := n_
a := array[int]$fill(0, k*n, 0)
seq := array[int]$[]
db(1, 1)
s: stream := stream$create_output()
for i: int in array[int]$elements(seq) do
stream$puts(s, int$unparse(i))
end
return(stream$get_contents(s))
end generate
db = proc (t, p: int)
if t>n then
if n//p = 0 then
for i: int in int$from_to(1, p) do
array[int]$addh(seq, a[i])
end
end
else
a[t] := a[t - p]
db(t+1, p)
for j: int in int$from_to(a[t - p] + 1, k-1) do
a[t] := j
db(t + 1, t)
end
end
end db
end de_bruijn
% Reverse a string
reverse = proc (s: string) returns (string)
r: array[char] := array[char]$predict(1, string$size(s))
for c: char in string$chars(s) do
array[char]$addl(r, c)
end
return(string$ac2s(r))
end reverse
% Find all missing N-digit values
find_missing = proc (db: string, n: int) returns (sequence[string])
db := db || string$substr(db, 1, n) % wrap
missing: array[string] := array[string]$[]
s: stream := stream$create_output()
for i: int in int$from_to(0, 10**n-1) do
%s: stream := stream$create_output()
stream$reset(s)
stream$putzero(s, int$unparse(i), n)
val: string := stream$get_contents(s)
if string$indexs(val, db) = 0 then
array[string]$addh(missing, val)
end
end
return(sequence[string]$a2s(missing))
end find_missing
% Report all missing values, or 'none'.
validate = proc (s: stream, db: string, n: int)
stream$puts(s, "Validating...")
missing: sequence[string] := find_missing(db, n)
for v: string in sequence[string]$elements(missing) do
stream$puts(s, " " || v)
end
if sequence[string]$size(missing) = 0 then
stream$puts(s, " none")
end
stream$putl(s, " missing.")
end validate
start_up = proc ()
po: stream := stream$primary_output()
% Generate the De Bruijn sequence for 4-digit numbers
db: string := de_bruijn$generate(10, 4)
% Report length and first and last digits
stream$putl(po, "Length: " || int$unparse(string$size(db)))
stream$putl(po, "First 130 characters:")
stream$putl(po, string$substr(db, 1, 130))
stream$putl(po, "Last 130 characters:")
stream$putl(po, string$substr(db, string$size(db)-130, 130))
% See if there are any missing values in the sequence
validate(po, db, 4)
% Reverse and validate again
stream$putl(po, "Reversing...")
validate(po, reverse(db), 4)
% Replace the 4444'th element with '.' and validate again
stream$putl(po, "Setting the 4444'th character to '.'...")
db := string$substr(db, 1, 4443) || "." || string$rest(db, 4445)
validate(po, db, 4)
end start_up</lang>
{{out}}
<pre>Length: 10000
First 130 characters:
0000100020003000400050006000700080009001100120013001400150016001700180019002100220023002400250026002700280029003100320033003400350
Last 130 characters:
6897689868996969776978697969876988698969976998699977778777977887789779877997878797888788978987899797988798979987999888898899898999
Validating... none missing.
Reversing...
Validating... none missing.
Setting the 4444'th character to '.'...
Validating... 1459 4591 5814 8145 missing.</pre>
=={{header|D}}==
| |||