De Bruijn sequences: Difference between revisions
Content added Content deleted
JsfasdF256 (talk | contribs) No edit summary |
Not a robot (talk | contribs) (Add CLU) |
||
Line 930: | Line 930: | ||
PIN number 5814 missing |
PIN number 5814 missing |
||
PIN number 8145 missing</pre> |
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}}== |
=={{header|D}}== |