Sprawdź słowo Lyndona

22

Lyndon słowo to ciąg znaków, który jest ściśle leksykograficznie mniejszy niż którykolwiek z jego cyklicznych obrotów. Biorąc pod uwagę ciąg binarny, określ, czy jest to słowo Lyndona w jak najmniejszej liczbie bajtów.

Na przykład 001011jest słowem Lyndon. Jego obroty, wymienione poniżej, są uzyskiwane przez wielokrotne przesuwanie pierwszego symbolu do końca.

001011
010110
101100
011001
110010
100101

Spośród nich oryginalny ciąg znaków jest najpierw leksykograficznie, lub równoważnie, reprezentuje najmniejszą liczbę binarną.

Jednak 001001nie jest słowem Lyndona, ponieważ jedna z jego rotacji jest taka sama jak sama, co wiąże je z najwcześniejszym leksykograficznie.

Powiązany problem.

Dane wejściowe: niepusty ciąg binarny lub lista cyfr 0i 1. Być może nie używać liczb, jak 5do reprezentowania 101.

Dane wyjściowe: spójna wartość Prawda lub Falsey, która mówi, czy ciąg jest słowem Lyndona.

Wbudowane specjalnie dla słów Lyndon nie są dozwolone.

Przypadki testowe:

Słowa Lyndon o długości do 6 to:

0
1
01
001
011
0001
0011
0111
00001
00011
00101
00111
01011
01111
000001
000011
000101
000111
001011
001101
001111
010111
011111

Nie-Lyndonskie słowa o długości do 4 to:

00
10
11
000
010
100
101
110
111
0000
0010
0100
0101
0110
1000
1001
1010
1011
1100
1101
1110
1111

Tabela liderów:

Pokaż fragment kodu

code-golf string xnor
źródło

Odpowiedzi:

5

Python 2, 42

Wydaje się, że jest wystarczająco dobry do porównania z przyrostkami zamiast zawracania głowy rotacją.

f=lambda s,i=1:i/len(s)or s<s[i:]*f(s,i+1)

Konfiguracja rekurencji nie wydaje się zbyt ładna; może można to zrobić lepiej.

Ta 44-bajtowa wersja pokazuje, co się dzieje:

lambda s:all(s<=s[i:]for i in range(len(s)))
feersum
źródło
4

Haskell, 43 38 bajtów

f x=all(x<=)$init$scanl(const.tail)x x

scanl(const.tail)x xbuduje listę wszystkich przyrostków x, w tym pusty ciąg ""na końcu, który jest usuwany init.

Edycja: @feersum zauważył błąd w mojej pierwszej wersji i wpadł na pomysł, że wystarczy porównanie z przyrostkami.

nimi
źródło
Jak to sprawdzić, czy nie ma żadnych obroty x, które są równe x?
feersum
@feersum: tak nie jest. To jest błąd. Naprawione. Dzięki za informację!
nimi
4

Pyth, 9 bajtów

!f>z>zTUz

Demonstracja

Wykorzystuje Vihan i in. podejście do sufiksów al.

isaacg
źródło
Cholera, myślałem, że mam coś do
roboty
2

CJam, 15 14 bajtów

r_,,\fm<(f>1-!

Wypróbuj to skrzypce w interpretatorze CJam lub zweryfikuj wszystkie przypadki testowe jednocześnie.

Jak to działa

r              e# Read a token from STDIN.
 _,            e# Push the length of a copy.
   ,           e# Turn length L into [0 ... L-1].
    \fm<       e# Rotate the token 0, ..., and L-1 units to the left.
        (      e# Shift out the first rotation, i.e., the original token.
         f>    e# Compare all other rotations with this one.
           1-  e# Remove 1 from the resulting array of Booleans.
             ! e# Apply logical NOT to turn an empty array into 1, and a
               e# non-empty one into 0.
Dennis
źródło
2

J, 11 znaków

Dane wyjściowe 1dotyczące słów Lyndona i 0nie tylko.

0=0({/:)<\.

<\. przybiera przyrostki, a następnie /: mówi nam, jak sortować je leksykograficznie. {pobiera wpis przy 0-tym indeksie i 0=sprawdza, czy wynosi zero: jeśli tak, to mamy słowo Lyndona, ponieważ największy przyrostek nie zmieniłby miejsca w jakimś rodzaju; jeśli jest niezerowe, nie jest słowem Lyndona, ponieważ niektóre sufiksy są wcześniej leksykograficzne.

   0=0({/:)<\. '001011'
1
   0=0({/:)<\. '001001'
0
algorytmshark
źródło
2

TeaScript , 10 bajtów

xe»x«xS(i©

Bardzo golfowy, bardzo krótki. Wypróbuj online

Wyjaśnienie i nieugolfowany

xe(#x<=xS(i))

xe(#      // Loop through x
          // Check if all iterations return true
    x <=  // Input is less than or equal to...
    xS(i) // Input chopped at current index
)
Downgoat
źródło
Święta krowa, bijesz <s> Pyth </s> Dennis ! Jak to w ogóle jest możliwe?!
ETHprodukcje
2
@ETHproductions W świecie, w którym Dennis może zostać pokonany, wszystko jest możliwe: p
Downgoat
Będę delektować się tą chwilą, dopóki będzie trwała, wtedy odpowiedzi na pytania CJam i Pyth prawdopodobnie będą bardziej
grały w
Czekaj, czekaj ... Widzę, że to poprawnie obsługuje przypadki takie jak 00, ale jak to robi, nie łapiąc się, że jest równy sobie (tj. Kiedy i==0)?
ETHprodukcje
@ETHproductions To nie jest tak naprawdę cykl jak odpowiedź feersum , zwykłe porównanie sufiksów jest funkcjonalnie równoważne
Downgoat
1

Haskell, 29

f s=all(s<=)$init$scanr(:)[]s

Sprawdza, czy s co najwyżej każdy z niepustych sufiksów, jak odpowiedź nich .

Ekspresja scanr(:)[] generuje listę sufiksów poprzez listowanie.

>> scanr(:)[] "abcd"
["abcd","bcd","cd","d",""]

initNastępnie pozbywa pusty ciąg na końcu. Na koniec all(s<=)sprawdza, czy każdy przyrostek xjest odpowiedni s<=x. Ponieważ pierwszy sufiks jest ssam, <=potrzebny jest a .

xnor
źródło
1

Rubinowy, 37 bajtów

->s{(1...s.size).all?{|i|s[i..-1]>s}}

Testowanie:

lyndon_words = %w(0 1 01 001 011 0001 0011 0111 00001 00011 00101 00111
                  01011 01111 000001 000011 000101 000111 001011 001101
                  001111 010111 011111)

not_lyndon_words = %w(00 10 11 000 010 100 101 110 111 0000 0010 0100 0101
                      0110 1000 1001 1010 1011 1100 1101 1110 1111)

f=->s{(1...s.size).all?{|i|s[i..-1]>s}}

p lyndon_words.all? &f      # => true
p not_lyndon_words.any? &f  # => false
daniero
źródło
1

Burleska, 15 bajtów

JiRJU_j<]x/==&&

Głównie 8 z tych 7 bajtów ma sprawdzić, czy się nie wiąże. W przeciwnym razie możesz przejść po prostuJiR<]== .

Wyjaśnienie:

J       -- duplicate word
iR      -- all rotations
J       -- duplicate list of all rotations
U_      -- check if list contains no duplicates
j       -- swap
<]      -- find minimum of the list
x/      -- rotate top
==      -- compare minimum with the original word
&&      -- and results of min == orig and list unique
mroman
źródło
0

JavaScript (ES6), 129 bajtów

a=Array;s=prompt();console.log(a.from(a(s.length),(x,i)=>i).map(n=>(s.substring(n)+s.substring(0,n--))).sort().pop().contains(s))
anOKsquirrel
źródło
0

JavaScript, 91 87 bajtów

f=x=>(y=(x+x).slice(1,-1),x[0]==x||!(y.indexOf(x)+1)&&!x.indexOf('0')&&x.slice(-1)==1);

Zasadniczo łączę to słowo z samym sobą i sprawdzam, czy nadal tam jest. Aby sprawdzić, czy jest to najmniejsza możliwa liczba, po prostu sprawdzam, czy zaczyna się od 0, a kończy na 1.

Testy

[
['0',1],
['1',1],
['01',1],
['001',1],
['011',1],
['0001',1],
['0011',1],
['0111',1],
['00001',1],
['00011',1],
['00101',1],
['00111',1],
['01011',1],
['01111',1],
['000001',1],
['000011',1],
['000101',1],
['000111',1],
['001011',1],
['001101',1],
['001111',1],
['010111',1],
['011111',1],
['00',0],
['10',0],
['11',0],
['000',0],
['010',0],
['100',0],
['101',0],
['110',0],
['111',0],
['0000',0],
['0010',0],
['0100',0],
['0101',0],
['0110',0],
['1000',0],
['1001',0],
['1010',0],
['1011',0],
['1100',0],
['1101',0],
['1110',0],
['1111',0]
].forEach(t =>{ 
  r=f(t[0])
  x=t[1]
  console.log('Test '+(r==x?'OK':'Fail (Expected: ' + x +')')
  +'\nInput: '+t[0]+'\nResult: ' +r+'\n')                       
})
Naouak
źródło
0

Mathematica, 86 bajtów

(s=Table[#~StringRotateLeft~i,{i,StringLength@#}];Last@s==First@Sort@s&&s~Count~#==1)&

wkład

[„1111”]

J42161217
źródło