De Bruijn sequences: Difference between revisions

{{trans|D}}

 

 

F deBruijn(k, n)

db[4443] = ‘.’

print("\nValidating the overlaid deBruijn sequence:")

 

{{out}}

 

=={{header|8080 Assembly}}==

putch: equ 2 ; Write character to console

puts: equ 9 ; Write string to console

arr: equ ($/256+1)*256 ; Place to store a[] (page-aligned)

val: equ arr+40 ; Place to store validation flags

 

{{out}}

=={{header|8086 Assembly}}==

 

puts: equ 9 ; Print string

cpu 8086

arr: resb 40 ; a[]

val: resb 10000 ; validation array

 

{{out}}

=={{header|Ada}}==

{{trans|D}}

with Ada.Strings.Fixed; use Ada.Strings;

with Ada.Strings.Unbounded;

Validate (Ovl);

New_Line;

 

{{out}}

 

=={{header|BASIC}}==

20 K = 10: N = 4

30 DIM A(K*N), S(K^N+N), T(5), P(5), V(K^N\8)

770 IF M THEN PRINT " none";

780 PRINT " missing."

{{out}}

<pre>Length: 10000

=={{header|C sharp|C#}}==

{{trans|Kotlin}}

using System.Collections.Generic;

using System.Text;

}

}

{{out}}

<pre>The length of the de Bruijn sequence is 10003

=={{header|C++}}==

{{trans|D}}

#include <functional>

#include <iostream>

 

return 0;

{{out}}

<pre>The length of the de Bruijn sequence is 10003

 

=={{header|CLU}}==

de_bruijn = cluster is generate

rep = null

db := string$substr(db, 1, 4443) || "." || string$rest(db, 4445)

validate(po, db, 4)

{{out}}

<pre>Length: 10000

=={{header|D}}==

{{trans|Kotlin}}

import std.conv;

import std.format;

writeln("\nValidating the overlaid deBruijn sequence:");

validate(db);

{{out}}

<pre>The length of the de Bruijn sequence is 10003

 

=={{header|Go}}==

 

import (

fmt.Println("\nValidating the overlaid de Bruijn sequence:")

validate(db)

 

{{out}}

=={{header|Groovy}}==

{{trans|Java}}

 

class DeBruijn {

validate(sb.toString())

}

{{out}}

<pre>The length of the de Bruijn sequence is 10003

Straight-forward implementation of inverse Burrows—Wheeler transform [[wp:De_Bruijn_sequence#Construction|De_Bruijn_sequence#Construction] is reasonably efficient for the task (about a milliseconds for B(10,4) in GHCi).

 

import Data.Map ((!))

import qualified Data.Map as M

deBruijn :: Ord a => [a] -> Int -> [a]

deBruijn s n = let lw = concat $ lyndonWords n s

 

<pre>λ> cycleForm [1,4,3,2,0]

The task.

 

 

main = do

 

let db' = a ++ ('.': tail b) where (a,b) = splitAt 4444 db

 

<pre>λ> main

{{trans|Python}}

 

import Data.Array (Array, listArray, (!), (//))

import qualified Data.Array as A

seqn = db 1 1 `evalState` listArray (0, k*n-1) (repeat 0)

 

=={{header|J}}==

definitions. The C. verb computes the cycles. J's sort is a stable sort.

 

repeat_alphabet=: [: , [: i.&> (^ <:) # [

groups=: [ ]\ ] , ({.~ <:)~ NB. length x infixes of sequence y cyclically extended by x-1

verify_PINs=: (/:~@:groups -: pins@:[) NB. LENGTH verify_PINs SEQUENCE

A=: 10 de_bruijn 4

 

4 verify_PINs (a.i.'.') (<: 4444)} A

0

 

=={{header|Java}}==

{{trans|C++}}

import java.util.Arrays;

import java.util.List;

validate(sb.toString());

}

{{out}}

<pre>The length of the de Bruijn sequence is 10003

 

=={{header|Julia}}==

alphabet = b"0123456789abcdefghijklmnopqrstuvwxyz"[1:k]

a = zeros(UInt8, k * n)

print("Testing the reversed sequence: "), verifyallPIN(reverse(s), 10, 4)

println("\nAfter replacing 4444th digit with \'.\':"), verifyallPIN(s, 10, 4, 4444)

<pre>

The length of the sequence is 10003. The first 130 digits are:

=={{header|Kotlin}}==

{{trans|Go}}

 

fun deBruijn(k: Int, n: Int): String {

println("\nValidating the overlaid deBruijn sequence:")

validate(db)

{{out}}

<pre>The length of the de Bruijn sequence is 10003

=={{header|Lua}}==

{{trans|C++}}

for i,v in pairs(tbl) do

print(v)

end

 

{{out}}

<pre>The length of the de Bruijn sequence is 10003

 

=={{header|Mathematica}}/{{header|Wolfram Language}}==

seq = seq~Join~Take[seq, 3];

Length[seq]

StringDrop[ToString[NumberForm[#, 4, NumberPadding -> {"0", "0"}]],

1] & /@ Range[0, 9999],

 

{{out}}

=={{header|Nim}}==

{{trans|D}}

 

const Digits = "0123456789"

db[4443] = '.'

echo "Validating the overlaid deBruijn sequence:"

 

{{out}}

 

For a given word length n, constructs a de Bruijn sequence by concatenating, in lexicographic order, all the Lyndon words whose length divides n. (See Wikipedia article "de Bruijn sequence", section "Construction".)

program deBruijnSequence;

uses SysUtils;

end;

end.

{{out}}

<pre>

=={{header|Perl}}==

{{trans|Raku}}

use warnings;

use feature 'say';

substr $seq, 4443, 1, 5;

say "Incorrect 4 digit PINs in the revised sequence:";

{{out}}

<pre>de Bruijn sequence length: 10003

{{trans|zkl}}

{{trans|Go}}

<span style="color: #004080;">string</span> <span style="color: #000000;">deBruijn</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""</span>

<span style="color: #008080;">for</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">99</span> <span style="color: #008080;">do</span>

<span style="color: #000000;">deBruijn</span><span style="color: #0000FF;">[</span><span style="color: #000000;">4444</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">'.'</span>

<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Re-running checks: %s\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">check</span><span style="color: #0000FF;">(</span><span style="color: #000000;">deBruijn</span><span style="color: #0000FF;">))</span>

{{out}}

<pre>

 

=={{header|Python}}==

# from https://en.wikipedia.org/wiki/De_Bruijn_sequence

 

print("Validating the overlaid deBruijn sequence:")

validate(dboverlaid)

{{out}}

<pre>

{{trans|Go}}

 

(define (de-bruijn k n)

(validate "" seq)

(validate "reversed " (reverse seq))

 

{{out}}

Deviates very slightly from the task spec. Generates a randomized de Bruijn sequence and replaces the 4444th digit with a the digit plus 1 mod 10 rather than a '.', mostly so it can demonstrate detection of extra PINs as well as missing ones.

 

my $seq;

 

put "Incorrect 4 digit PINs in the revised sequence:";

$seq.substr-rw(4443,1) = $digit;

{{out|Sample output}}

<pre>de Bruijn sequence length: 10003

The &nbsp; de Bruijn &nbsp; sequence generated by these REXX programs are identical to the sequence shown on the &nbsp; ''discussion'' &nbsp; page &nbsp; (1^st topic).

=== hard-coded node to be removed ===

$= /*initialize the de Bruijn sequence. */

#=10; lastNode= (#-2)(#-2)(#-1)(#-2) /*this number is formed when this # ···*/

if e==0 then e= 'No' /*Gooder English (sic) the error count.*/

say _ e 'errors found.' /*display the number of errors found. */

{{out|output}}

<pre>

 

This method slightly bloats the program and slows execution.

$= /*initialize the de Bruijn sequence. */

do j=0 for 10; $= $ j; jj= j || j /*compose the left half of the numbers.*/

if e==0 then e= 'No' /*Gooder English (sic) the error count.*/

say _ e 'errors found.' /*display the number of errors found. */

{{out|output|text=&nbsp; is identical to the 1^st REXX version.}} <br>

 

=={{header|Ruby}}==

{{trans|D}}

alphabet = "0123456789"

@a = Array.new(k * n, 0)

db[4443] = '.'

print "Validating the overlaid de Bruijn sequence:\n"

{{out}}

<pre>The length of the de Bruijn sequence is 10003

=={{header|Visual Basic .NET}}==

{{trans|C#}}

 

Module Module1

End Sub

 

{{out}}

<pre>The first 130 digits of the de Bruijn sequence are: 0000100020003000400050006000700080009001100120013001400150016001700180019002100220023002400250026002700280029003100320033003400350

{{libheader|Wren-fmt}}

{{libheader|Wren-str}}

import "/str" for Str

System.print("\n4,444th digit in the sequence: '%(deBruijn[4443])' (setting it to '.')")

deBruijn = deBruijn[0..4442] + "." + deBruijn[4444..-1]

 

{{out}}

=={{header|zkl}}==

{{trans|Raku}}

foreach n in (100){

a,a01,a11 := "%02d".fmt(n), a[0,1], a[1,1];

}

}

println("de Bruijn sequence length: ",dbSeq.len());

 

println("\n4444th digit in the sequence: ", seqText[4443]);

dbSeq[4443]=".";

{{out}}

<pre>