Urutan De Bruijn menarik: Urutan siklik terpendek yang berisi semua kemungkinan urutan alfabet tertentu dengan panjang tertentu. Misalnya, jika kami mempertimbangkan alfabet A, B, C dan panjang 3, output yang mungkin adalah:

AAABBBCCCABCACCBBAACBCBABAC

Anda akan melihat bahwa setiap kemungkinan urutan 3-karakter dengan menggunakan huruf A, Bdan Cberada di sana.

Tantangan Anda adalah untuk menghasilkan urutan De Bruijn dalam karakter sesedikit mungkin. Fungsi Anda harus mengambil dua parameter, bilangan bulat yang mewakili panjang urutan, dan daftar yang berisi alfabet. Output Anda harus menjadi urutan dalam formulir daftar.

Anda dapat mengasumsikan bahwa setiap item dalam alfabet berbeda.

Contoh generator dapat ditemukan di sini

Celah standar berlaku

Pyth, 31 byte

Ini adalah konversi langsung dari algoritma yang digunakan dalam jawaban CJam saya . Selamat datang di golf!

Mu?G}H+GG+G>Hefq<HT>G-lGTUH^GHk

Kode ini mendefinisikan fungsi gyang mengambil dua argumen, string daftar karakter dan nomor.

Contoh penggunaan:

Mu?G}H+GG+G>Hefq<HT>G-lGTUH^GHkg"ABC"3

Keluaran:

AAABAACABBABCACBACCBBBCBCCC

Perluasan kode:

M                 # def g(G,H):
 u                #   return reduce(lambda G, H:
  ?G              #     (G if
    }H            #       (H in
      +GG         #          add(G,G)) else
    +G            #       add(G,
      >H          #         slice_end(H,
        e         #           last_element(
         f        #             Pfilter(lambda T:
          q       #               equal(
           <HT    #                 slice_start(H,T),
           >G     #                 slice_end(G,
             -lGT #                   minus(Plen(G),T))),
          UH      #               urange(H)))))),
  ^GH             #     cartesian_product(G,H),
  k               #     "")

Coba di sini

CJam, 52 49 48 byte

Ini sangat lama. Ini bisa bermain golf banyak, mengambil tips dari terjemahan Pyth.

q~a*{m*:s}*{:H\:G_+\#)GGHH,,{_H<G,@-G>=},W=>+?}*

Inputnya seperti

3 "ABC"

yaitu - String daftar karakter dan panjangnya.

dan output adalah string De Bruijn

AAABAACABBABCACBACCBBBCBCCC

Cobalah online di sini

CJam, 52 49 byte

Berikut adalah pendekatan berbeda dalam CJam:

l~:N;:L,(:Ma{_N*N<0{;)_!}g(+_0a=!}g]{,N\%!},:~Lf=

Mengambil input seperti ini:

"ABC" 3

dan menghasilkan karya Lyndon seperti

CCCBCCACBBCBACABCAABBBABAAA

Coba di sini.

Ini memanfaatkan hubungan dengan kata-kata Lyndon . Ini menghasilkan semua kata-kata Lyndon dengan panjang n dalam urutan leksikografis (seperti yang diuraikan dalam artikel Wikipedia), lalu menjatuhkan kata-kata yang panjangnya tidak dibagi n . Ini sudah menghasilkan urutan De Bruijn, tapi karena saya menghasilkan kata-kata Lyndon sebagai string angka, saya juga perlu mengganti yang dengan huruf yang sesuai di akhir.

Untuk alasan bermain golf, saya menganggap huruf-huruf selanjutnya dalam alfabet memiliki urutan leksikografis yang lebih rendah.

JavaScript (ES6) 143

Menggunakan kata-kata Lyndon, seperti aswer Martin, hanya 3 kali panjang ...

F=(a,n)=>{
  for(w=[-a[l='length']],r='';w[0];)
  {
    n%w[l]||w.map(x=>r+=a[~x]);
    for(;w.push(...w)<=n;);
    for(w[l]=n;!~(z=w.pop()););
    w.push(z+1)
  }
  return r
}

Uji di konsol FireFox / FireBug

console.log(F("ABC",3),F("10",4))

Keluaran

CCCBCCACBBCBACABCAABBBABAAA 0000100110101111

Python 2, 114 byte

Saya tidak terlalu yakin bagaimana cara bermain golf, karena pendekatan saya.

def f(a,n):
 s=a[-1]*n
 while 1:
    for c in a:
     if((s+c)[len(s+c)-n:]in s)<1:s+=c;break
    else:break
 print s[:1-n]

Cobalah online

Tidak Disatukan:

Kode ini adalah modifikasi sepele dari solusi saya ke tantangan yang lebih baru.

def f(a,n):
    s=a[-1]*n
    while 1:
        for c in a:
            p=s+c
            if p[len(p)-n:]in s:
                continue
            else:
                s=p
                break
        else:
            break
    print s[:1-n]

Satu-satunya alasan [:1-n]yang diperlukan adalah karena urutannya termasuk pembungkus.

Powershell, 164 96 byte

-68 byte dengan -match O($n*2^n)generator bukan rekursifO(n*log(n))

param($s,$n)for(;$z=$s|% t*y|?{"$($s[-1])"*($n-1)+$x-notmatch-join"$x$_"[-$n..-1]}){$x+=$z[0]}$x

Skrip tidak diuji & tes:

$f = {

param($s,$n)                    # $s is a alphabet, $n is a subsequence length
for(;                           # repeat until...
    $z=$s|% t*y|?{              # at least a character from the alphabet returns $true for expression:
        "$($s[-1])"*($n-1)+$x-notmatch  # the old sequence that follows two characters (the last letter from the alphabet) not contains
        -join"$x$_"[-$n..-1]    # n last characters from the new sequence
}){
    $x+=$z[0]                   # replace old sequence with new sequence
}
$x                              # return the sequence

}

@(
    ,("ABC",  2, "AABACBBCC")
    ,("ABC",  3, "AAABAACABBABCACBACCBBBCBCCC")
    ,("ABC",  4, "AAAABAAACAABBAABCAACBAACCABABACABBBABBCABCBABCCACACBBACBCACCBACCCBBBBCBBCCBCBCCCC")
    ,("ABC",  5, "AAAAABAAAACAAABBAAABCAAACBAAACCAABABAABACAABBBAABBCAABCBAABCCAACABAACACAACBBAACBCAACCBAACCCABABBABABCABACBABACCABBACABBBBABBBCABBCBABBCCABCACABCBBABCBCABCCBABCCCACACBACACCACBBBACBBCACBCBACBCCACCBBACCBCACCCBACCCCBBBBBCBBBCCBBCBCBBCCCBCBCCBCCCCC")
    ,("ABC",  6, "AAAAAABAAAAACAAAABBAAAABCAAAACBAAAACCAAABABAAABACAAABBBAAABBCAAABCBAAABCCAAACABAAACACAAACBBAAACBCAAACCBAAACCCAABAABAACAABABBAABABCAABACBAABACCAABBABAABBACAABBBBAABBBCAABBCBAABBCCAABCABAABCACAABCBBAABCBCAABCCBAABCCCAACAACABBAACABCAACACBAACACCAACBABAACBACAACBBBAACBBCAACBCBAACBCCAACCABAACCACAACCBBAACCBCAACCCBAACCCCABABABACABABBBABABBCABABCBABABCCABACACABACBBABACBCABACCBABACCCABBABBABCABBACBABBACCABBBACABBBBBABBBBCABBBCBABBBCCABBCACABBCBBABBCBCABBCCBABBCCCABCABCACBABCACCABCBACABCBBBABCBBCABCBCBABCBCCABCCACABCCBBABCCBCABCCCBABCCCCACACACBBACACBCACACCBACACCCACBACBACCACBBBBACBBBCACBBCBACBBCCACBCBBACBCBCACBCCBACBCCCACCACCBBBACCBBCACCBCBACCBCCACCCBBACCCBCACCCCBACCCCCBBBBBBCBBBBCCBBBCBCBBBCCCBBCBBCBCCBBCCBCBBCCCCBCBCBCCCBCCBCCCCCC")
    ,("01",   3, "00010111")
    ,("01",   4, "0000100110101111")
    ,("abcd", 2, "aabacadbbcbdccdd")
    ,("0123456789", 3, "0001002003004005006007008009011012013014015016017018019021022023024025026027028029031032033034035036037038039041042043044045046047048049051052053054055056057058059061062063064065066067068069071072073074075076077078079081082083084085086087088089091092093094095096097098099111211311411511611711811912212312412512612712812913213313413513613713813914214314414514614714814915215315415515615715815916216316416516616716816917217317417517617717817918218318418518618718818919219319419519619719819922232242252262272282292332342352362372382392432442452462472482492532542552562572582592632642652662672682692732742752762772782792832842852862872882892932942952962972982993334335336337338339344345346347348349354355356357358359364365366367368369374375376377378379384385386387388389394395396397398399444544644744844945545645745845946546646746846947547647747847948548648748848949549649749849955565575585595665675685695765775785795865875885895965975985996667668669677678679687688689697698699777877978878979879988898999")
    ,("9876543210", 3, "9998997996995994993992991990988987986985984983982981980978977976975974973972971970968967966965964963962961960958957956955954953952951950948947946945944943942941940938937936935934933932931930928927926925924923922921920918917916915914913912911910908907906905904903902901900888788688588488388288188087787687587487387287187086786686586486386286186085785685585485385285185084784684584484384284184083783683583483383283183082782682582482382282182081781681581481381281181080780680580480380280180077767757747737727717707667657647637627617607567557547537527517507467457447437427417407367357347337327317307267257247237227217207167157147137127117107067057047037027017006665664663662661660655654653652651650645644643642641640635634633632631630625624623622621620615614613612611610605604603602601600555455355255155054454354254154053453353253153052452352252152051451351251151050450350250150044434424414404334324314304234224214204134124114104034024014003332331330322321320312311310302301300222122021121020120011101000")
) |% {
    $s,$n,$e = $_
    $r = &$f $s $n
    "$($r-eq$e): $r"
}

Keluaran:

True: AABACBBCC
True: AAABAACABBABCACBACCBBBCBCCC
True: AAAABAAACAABBAABCAACBAACCABABACABBBABBCABCBABCCACACBBACBCACCBACCCBBBBCBBCCBCBCCCC
True: AAAAABAAAACAAABBAAABCAAACBAAACCAABABAABACAABBBAABBCAABCBAABCCAACABAACACAACBBAACBCAACCBAACCCABABBABABCABACBABACCABBACABBBBABBBCABBCBABBCCABCACABCBBABCBCABCCBABCCCACACBACACCACBBBACBBCACBCBACBCCACCBBACCBCACCCBACCCCBBBBBCBBBCCBBCBCBBCCCBCBCCBCCCCC
True: AAAAAABAAAAACAAAABBAAAABCAAAACBAAAACCAAABABAAABACAAABBBAAABBCAAABCBAAABCCAAACABAAACACAAACBBAAACBCAAACCBAAACCCAABAABAACAABABBAABABCAABACBAABACCAABBABAABBACAABBBBAABBBCAABBCBAABBCCAABCABAABCACAABCBBAABCBCAABCCBAABCCCAACAACABBAACABCAACACBAACACCAACBABAACBACAACBBBAACBBCAACBCBAACBCCAACCABAACCACAACCBBAACCBCAACCCBAACCCCABABABACABABBBABABBCABABCBABABCCABACACABACBBABACBCABACCBABACCCABBABBABCABBACBABBACCABBBACABBBBBABBBBCABBBCBABBBCCABBCACABBCBBABBCBCABBCCBABBCCCABCABCACBABCACCABCBACABCBBBABCBBCABCBCBABCBCCABCCACABCCBBABCCBCABCCCBABCCCCACACACBBACACBCACACCBACACCCACBACBACCACBBBBACBBBCACBBCBACBBCCACBCBBACBCBCACBCCBACBCCCACCACCBBBACCBBCACCBCBACCBCCACCCBBACCCBCACCCCBACCCCCBBBBBBCBBBBCCBBBCBCBBBCCCBBCBBCBCCBBCCBCBBCCCCBCBCBCCCBCCBCCCCCC
True: 00010111
True: 0000100110101111
True: aabacadbbcbdccdd
True: 0001002003004005006007008009011012013014015016017018019021022023024025026027028029031032033034035036037038039041042043044045046047048049051052053054055056057058059061062063064065066067068069071072073074075076077078079081082083084085086087088089091092093094095096097098099111211311411511611711811912212312412512612712812913213313413513613713813914214314414514614714814915215315415515615715815916216316416516616716816917217317417517617717817918218318418518618718818919219319419519619719819922232242252262272282292332342352362372382392432442452462472482492532542552562572582592632642652662672682692732742752762772782792832842852862872882892932942952962972982993334335336337338339344345346347348349354355356357358359364365366367368369374375376377378379384385386387388389394395396397398399444544644744844945545645745845946546646746846947547647747847948548648748848949549649749849955565575585595665675685695765775785795865875885895965975985996667668669677678679687688689697698699777877978878979879988898999
True: 9998997996995994993992991990988987986985984983982981980978977976975974973972971970968967966965964963962961960958957956955954953952951950948947946945944943942941940938937936935934933932931930928927926925924923922921920918917916915914913912911910908907906905904903902901900888788688588488388288188087787687587487387287187086786686586486386286186085785685585485385285185084784684584484384284184083783683583483383283183082782682582482382282182081781681581481381281181080780680580480380280180077767757747737727717707667657647637627617607567557547537527517507467457447437427417407367357347337327317307267257247237227217207167157147137127117107067057047037027017006665664663662661660655654653652651650645644643642641640635634633632631630625624623622621620615614613612611610605604603602601600555455355255155054454354254154053453353253153052452352252152051451351251151050450350250150044434424414404334324314304234224214204134124114104034024014003332331330322321320312311310302301300222122021121020120011101000

Lihat juga: Satu Dering untuk mengatur semuanya. Satu String berisi semuanya