11
\$\begingroup\$

Background

A Lyndon word is a non-empty string which is strictly lexicographically smaller than all its other rotations. It is possible to factor any string uniquely as the concatenation of Lyndon words such that these subwords are lexicographically non-increasing; your challenge is to do this as succinctly as possible.

Details

You should implement a function or program which enumerates the Lyndon word factorization of any printable ASCII string, in order, outputting the resultant substrings as an array or stream of some kind. Characters should be compared by their code points, and all standard input and output methods are allowed. As usual for , the shortest program in bytes wins.

Test Cases

''           []
'C'          ['C']
'aaaaa'      ['a', 'a', 'a', 'a', 'a']
'K| '        ['K|', ' ']
'abaca'      ['abac', 'a']
'9_-$'       ['9_', '-', '$']
'P&O(;'      ['P', '&O(;']
'xhya{Wd$'   ['x', 'hy', 'a{', 'Wd', '$']
'j`M?LO!!Y'  ['j', '`', 'M', '?LO', '!!Y']
'!9!TZ'      ['!9!TZ']
'vMMe'       ['v', 'MMe']
'b5A9A9<5{0' ['b', '5A9A9<5{', '0']
\$\endgroup\$
  • \$\begingroup\$ Related \$\endgroup\$ – xnor Jun 19 '17 at 20:49
  • \$\begingroup\$ Note that this is equivalent to splitting by <=ness. (I have no idea how to express this better :| ) \$\endgroup\$ – CalculatorFeline Jun 19 '17 at 21:01
  • \$\begingroup\$ Is this equivalent to repeatedly taking the first character and the prefix of all characters bigger than it? \$\endgroup\$ – xnor Jun 19 '17 at 21:07
  • \$\begingroup\$ @xnor No. 'abac' is a Lyndon word. \$\endgroup\$ – user1502040 Jun 19 '17 at 21:13
  • \$\begingroup\$ @user1502040 I see, ties are interesting. I'd suggest adding some test cases that catch this. \$\endgroup\$ – xnor Jun 19 '17 at 21:14
5
\$\begingroup\$

Pyth, 17 16 bytes

-1 byte thanks to isaacg!

hf!ff>Y>YZUYT+./

Try it online!

Explanation

hf!ff>Y>YZUYT+./
              ./    Take all possible disjoint substring sets of [the input]
             +      plus [the input] itself (for the null string case).
 f                  Filter for only those sets which
  !f        T       for none of the substrings
    f  >YZUY        is there a suffix of the substring
     >Y             lexographically smaller than the substring itself.
h                   Return the first (i.e. the shortest) such set of substrings.
\$\endgroup\$
  • 1
    \$\begingroup\$ hf!ff>Y>YZUYT+./ accounts for the empty string case with 1 less byte. \$\endgroup\$ – isaacg Jun 19 '17 at 22:12
  • \$\begingroup\$ Nice, thanks! I felt like there must have been a shorter way. \$\endgroup\$ – notjagan Jun 19 '17 at 22:15
1
\$\begingroup\$

Jelly, 18 bytes

ṙJ¹ÐṂF⁼
ŒṖÇ€Ạ$ÐfṀȯ

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Pyth - 28 bytes

hf&SI_T.Am.A>Rdt.u.>N1tddT./

Test Suite.

\$\endgroup\$
  • 1
    \$\begingroup\$ This seems to fail on the empty string. \$\endgroup\$ – user1502040 Jun 19 '17 at 21:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.