Wygeneruj najkrótszy De Bruijn

22

Interesująca jest sekwencja De Bruijna: jest to najkrótsza, cykliczna sekwencja, która zawiera wszystkie możliwe sekwencje danego alfabetu o danej długości. Na przykład, jeśli rozważamy alfabet A, B, C i długość 3, możliwe wyniki to:

AAABBBCCCABCACCBBAACBCBABAC

Można zauważyć, że każda możliwa sekwencja 3-znakowy pomocą liter A, Bi Csą tam.

Twoim zadaniem jest wygenerowanie sekwencji De Bruijn w jak najmniejszej liczbie znaków. Twoja funkcja powinna przyjąć dwa parametry, liczbę całkowitą reprezentującą długość sekwencji oraz listę zawierającą alfabet. Twój wynik powinien być sekwencją w formie listy.

Możesz założyć, że każdy element w alfabecie jest inny.

Przykładowy generator można znaleźć tutaj

Standardowe luki zastosowanie

Nathan Merrill
źródło
Czy liczba całkowita reprezentująca długość sekwencji może być większa niż liczba unikalnych liter?
kukac67
Tak. Sekwencja binarna o długości 4 to 0000111101100101
Nathan Merrill,
„Twoim wyzwaniem jest wygenerowanie sekwencji De Bruijn w jak najmniejszej liczbie znaków” - Czy to oznacza „kod golfa” lub „uzyskać możliwie najkrótszą długość sekwencji De Bruijn”?
FryAmTheEggman
2
Obie. Aby się zakwalifikować, twój program musi wygenerować możliwie najkrótszą sekwencję, ale aby wygrać, twój program musi być najkrótszy.
Nathan Merrill,
2
@xem: zwykle sekwencje De Bruijn obejmują zawijanie, czyli tam, gdzie pojawiają się te brakujące sekwencje.
Keith Randall,

Odpowiedzi:

6

Pyth, 31 bajtów

Jest to bezpośrednia konwersja algorytmu zastosowanego w mojej odpowiedzi CJam . Wskazówki dotyczące gry w golfa mile widziane!

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

Ten kod definiuje funkcję, gktóra pobiera dwa argumenty, ciąg listy znaków i liczbę.

Przykładowe użycie:

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

Wydajność:

AAABAACABBABCACBACCBBBCBCCC

Rozszerzenie kodu:

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               #     "")

Wypróbuj tutaj

Optymalizator
źródło
4

CJam, 52 49 48 bajtów

To jest zaskakująco długie. Można w to dużo grać w golfa, biorąc pod uwagę wskazówki z tłumaczenia Pyth.

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

Wejście idzie jak

3 "ABC"

tj. - Ciąg listy znaków i długości.

a wyjściem jest ciąg De Bruijn

AAABAACABBABCACBACCBBBCBCCC

Wypróbuj online tutaj

Optymalizator
źródło
1
Gosh CJam powinien zostać zbanowany, nie jest przeznaczony tylko do jednego zadania golfowego, ale wydaje się, że do każdego możliwego zadania golfowego ...
flawr
2
@ flawr należy poczekać na odpowiedź w języku Pyth: P
Optimizer
3

CJam, 52 49 bajtów

Oto inne podejście w CJam:

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

Pobiera takie dane wejściowe:

"ABC" 3

i produkuje dzieło Lyndona

CCCBCCACBBCBACABCAABBBABAAA

Wypróbuj tutaj.

Wykorzystuje to relację ze słowami Lyndona . Generuje wszystkie słowa Lyndona o długości n w porządku leksykograficznym (jak opisano w tym artykule w Wikipedii), a następnie upuszcza te, których długości się nie dzielą n . To już daje sekwencję De Bruijn, ale ponieważ generuję słowa Lyndona jako ciągi cyfr, muszę również zastąpić je odpowiednimi literami na końcu.

Z powodów golfowych uważam, że późniejsze litery alfabetu mają niższy porządek leksykograficzny.

Martin Ender
źródło
1

JavaScript (ES6) 143

Używając słów Lyndona, takich jak odpowiedź Martina, zaledwie 3 razy ...

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
}

Testuj w konsoli FireFox / FireBug

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

Wydajność

CCCBCCACBBCBACABCAABBBABAAA 0000100110101111
edc65
źródło
1

Python 2, 114 bajtów

Nie jestem pewien, jak bardziej grać w golfa, ze względu na moje podejście.

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]

Wypróbuj online

Nie golfowany:

Ten kod jest trywialną modyfikacją mojego rozwiązania do nowszego wyzwania.

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]

Jedynym powodem [:1-n]jest to, że sekwencja obejmuje zawijanie.

mbomb007
źródło
1

PowerShell, 164 96 bajtów

-68 bajtów z -match O($n*2^n)zamiast generatora rekurencyjnegoO(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

Skrypt niepoznany i testowy:

$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"
}

Wydajność:

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

Zobacz także: Jeden pierścień, aby rządzić nimi wszystkimi. Jeden ciąg zawierający je wszystkie

mazzy
źródło