De Bruijn sequences: Difference between revisions
Content added Content deleted
Alextretyak (talk | contribs) (Added 11l) |
|||
| Line 80: | Line 80: | ||
:* An OEIS entry: [https://oeis.org/A166315 A166315 lexicographically earliest binary de Bruijn sequences, B(2,n)] --- Not B(10,4), but possibly relevant. |
:* An OEIS entry: [https://oeis.org/A166315 A166315 lexicographically earliest binary de Bruijn sequences, B(2,n)] --- Not B(10,4), but possibly relevant. |
||
<br><br> |
<br><br> |
||
=={{header|11l}}== |
|||
{{trans|D}} |
|||
<lang 11l>V digits = ‘0123456789’ |
|||
F deBruijn(k, n) |
|||
V alphabet = :digits[0 .< k] |
|||
V a = [Byte(0)] * (k * n) |
|||
[Byte] seq |
|||
F db(Int t, Int p) -> N |
|||
I t > @n |
|||
I @n % p == 0 |
|||
@seq.extend(@a[1 .< p + 1]) |
|||
E |
|||
@a[t] = @a[t - p] |
|||
@db(t + 1, p) |
|||
V j = @a[t - p] + 1 |
|||
L j < @k |
|||
@a[t] = j [&] F'F |
|||
@db(t + 1, t) |
|||
j++ |
|||
db(1, 1) |
|||
V buf = ‘’ |
|||
L(i) seq |
|||
buf ‘’= alphabet[i] |
|||
R buf‘’buf[0 .< n - 1] |
|||
F validate(db) |
|||
V found = [0] * 10'000 |
|||
[String] errs |
|||
L(i) 0 .< db.len - 3 |
|||
V s = db[i .< i + 4] |
|||
I s.is_digit() |
|||
found[Int(s)]++ |
|||
L(i) 10'000 |
|||
I found[i] == 0 |
|||
errs [+]= ‘ PIN number #04 missing’.format(i) |
|||
E I found[i] > 1 |
|||
errs [+]= ‘ PIN number #04 occurs #. times’.format(i, found[i]) |
|||
I errs.empty |
|||
print(‘ No errors found’) |
|||
E |
|||
V pl = I errs.len == 1 {‘’} E ‘s’ |
|||
print(‘ ’String(errs.len)‘ error’pl‘ found:’) |
|||
L(err) errs |
|||
print(err) |
|||
V db = deBruijn(10, 4) |
|||
print(‘The length of the de Bruijn sequence is ’db.len) |
|||
print("\nThe first 130 digits of the de Bruijn sequence are: "db[0.<130]) |
|||
print("\nThe last 130 digits of the de Bruijn sequence are: "db[(len)-130..]) |
|||
print("\nValidating the deBruijn sequence:") |
|||
validate(db) |
|||
print("\nValidating the reversed deBruijn sequence:") |
|||
validate(reversed(db)) |
|||
db[4443] = ‘.’ |
|||
print("\nValidating the overlaid deBruijn sequence:") |
|||
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 deBruijn sequence: |
|||
No errors found |
|||
Validating the reversed deBruijn sequence: |
|||
No errors found |
|||
Validating the overlaid deBruijn sequence: |
|||
4 errors found: |
|||
PIN number 1459 missing |
|||
PIN number 4591 missing |
|||
PIN number 5814 missing |
|||
PIN number 8145 missing |
|||
</pre> |
|||
=={{header|8080 Assembly}}== |
=={{header|8080 Assembly}}== |
||