Überprüfen Sie Lyndon-Wort

22

Ein Lyndon-Wort ist eine Zeichenfolge, die streng lexikografisch kleiner ist als jede ihrer zyklischen Rotationen. Bestimmen Sie bei einer gegebenen Binärzeichenfolge, ob es sich um ein Lyndon-Wort handelt, und zwar in möglichst wenigen Bytes.

Zum Beispiel 001011ist ein Lyndon-Wort. Die unten aufgelisteten Umdrehungen werden erhalten, indem das erste Symbol wiederholt ans Ende bewegt wird.

001011
010110
101100
011001
110010
100101

Von diesen steht die ursprüngliche Zeichenfolge lexikografisch an erster Stelle oder repräsentiert äquivalent die kleinste Binärzahl.

Es 001001ist jedoch kein Lyndon-Wort, da eine seiner Umdrehungen dieselbe ist wie seine selbst, was es für lexikografisch am frühesten bindet.

Ein verwandtes Problem.

Eingabe: Eine nicht leere Binärzeichenfolge oder eine Liste von Ziffern 0und 1. Sie dürfen keine Zahlen verwenden, die Sie gerne 5darstellen 101.

Ausgabe: Ein konsistenter Truthy- oder Falsey-Wert, der angibt, ob die Zeichenfolge ein Lyndon-Wort ist.

Built-Ins speziell für Lyndon-Wörter sind nicht zulässig.

Testfälle:

Die Lyndon-Wörter mit einer Länge von bis zu 6 sind:

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

Die Nicht-Lyndon-Wörter mit einer Länge von bis zu 4 sind:

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

Bestenliste:

Code-Snippet anzeigen

code-golf string xnor
quelle

Antworten:

5

Python 2, 42

Es scheint gut genug zu sein, mit Suffixen zu vergleichen, anstatt sich um eine Rotation zu kümmern.

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

Der Aufbau der Rekursion erscheint nicht sehr schön; Vielleicht könnte es besser gemacht werden.

Diese 44-Byte-Version macht klarer, was los ist:

lambda s:all(s<=s[i:]for i in range(len(s)))
Feersum
quelle
4

Haskell, 43 38 Bytes

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

scanl(const.tail)x xErstellt eine Liste aller Suffixe von x, einschließlich der leeren Zeichenfolge ""am Ende, die mit entfernt wird init.

Bearbeiten: @feersum entdeckte einen Fehler in meiner ersten Version und kam auf die Idee, dass der Vergleich mit Suffixen ausreicht.

nimi
quelle
Wie wird überprüft, ob es keine Rotationen gibt x, die gleich sind x?
Feersum
@feersum: tut es nicht. Es ist ein Fehler. Behoben. Danke, dass Sie es herausgefunden haben!
nimi
4

Pyth, 9 Bytes

!f>z>zTUz

Demonstration

Verwendet Vihan et. Ansatz mit Suffixen.

isaacg
quelle
Verdammt noch mal
2

CJam, 15 bis 14 Bytes

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

Probieren Sie diese Geige im CJam-Interpreter aus oder überprüfen Sie alle Testfälle auf einmal.

Wie es funktioniert

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
quelle
2

J, 11 char

Ausgaben 1für Lyndon-Wörter und 0sonstiges.

0=0({/:)<\.

<\.Nimmt Suffixe und /:sagt uns dann , wie wir sie lexikographisch sortieren sollen. {Nimmt den Eintrag am 0-ten Index und 0=prüft, ob er Null ist: Wenn dies der Fall ist, haben wir ein Lyndon-Wort, weil das größte Suffix die Position in einer Sortierung nicht ändern würde. Wenn es nicht Null ist, ist es kein Lyndon-Wort, da ein Suffix lexikografisch früher ist.

   0=0({/:)<\. '001011'
1
   0=0({/:)<\. '001001'
0
algorithmshark
quelle
2

TeaScript , 10 Bytes

xe»x«xS(i©

Sehr Golf, sehr kurz. Probieren Sie es online aus

Erklärung && Ungolfed

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
quelle
Heilige Kuh, du schlägst <s> Pyth </ s> Dennis ! Wie ist das überhaupt möglich ?!
ETHproductions
2
@ETHproductions In einer Welt, in der Dennis outgolfing kann, ist alles möglich: p
Downgoat
Ich werde diesen Moment genießen, solange er andauert, dann werden die Antworten von CJam und Pyth wahrscheinlich mehr gespielt
Downgoat
Warten Sie, warten Sie ... Ich sehe, dass dies wie Fälle richtig behandelt 00, aber wie macht es das, ohne zu merken, dass es sich selbst gleicht (dh wann i==0)?
ETHproductions
@ETHproductions Dies ist eigentlich kein Zyklus wie die Antwort von feersum , lediglich das Vergleichen der Suffixe ist funktional äquivalent
Downgoat
1

Haskell, 29

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

Prüft, ob shöchstens jedes seiner nicht leeren Suffixe wie Nimis Antwort ist .

Der Ausdruck scanr(:)[]generiert die Liste der Suffixe durch Auflisten.

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

Die initleere Zeichenkette wird dann am Ende entfernt. Abschließend wird all(s<=)geprüft, ob jedes Suffix xerfüllt ist s<=x. Da das erste Suffix sselbst ist, <=wird a benötigt.

xnor
quelle
1

Ruby, 37 Bytes

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

Testen:

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
quelle
1

Burlesque, 15 Bytes

JiRJU_j<]x/==&&

Hauptsächlich 8 dieser 7 Bytes dienen dazu, zu überprüfen, ob sie nicht zusammenpassen. Ansonsten kann man einfach mitgehenJiR<]== .

Erläuterung:

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
quelle
0

Javascript (ES6), 129 Bytes

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
quelle
0

Javascript, 91 87 Bytes

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

Im Grunde verkette ich das Wort mit sich selbst und überprüfe, ob es noch da ist. Um zu überprüfen, ob es sich um die kleinstmögliche Zahl handelt, stelle ich einfach sicher, dass sie mit einer 0 beginnt und mit einer 1 endet.

Tests

[
['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
quelle
0

Mathematica, 86 Bytes

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

Eingang

[1111]

J42161217
quelle