13
\$\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, by the Chen–Fox–Lyndon theorem, 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\$
8
  • \$\begingroup\$ Related \$\endgroup\$
    – xnor
    Jun 19, 2017 at 20:49
  • \$\begingroup\$ Note that this is equivalent to splitting by <=ness. (I have no idea how to express this better :| ) \$\endgroup\$ Jun 19, 2017 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, 2017 at 21:07
  • \$\begingroup\$ @xnor No. 'abac' is a Lyndon word. \$\endgroup\$ Jun 19, 2017 at 21:13
  • \$\begingroup\$ @user1502040 I see, ties are interesting. I'd suggest adding some test cases that catch this. \$\endgroup\$
    – xnor
    Jun 19, 2017 at 21:14

4 Answers 4

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\$
2
  • 1
    \$\begingroup\$ hf!ff>Y>YZUYT+./ accounts for the empty string case with 1 less byte. \$\endgroup\$
    – isaacg
    Jun 19, 2017 at 22:12
  • \$\begingroup\$ Nice, thanks! I felt like there must have been a shorter way. \$\endgroup\$
    – notjagan
    Jun 19, 2017 at 22:15
2
\$\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
  • 1
    \$\begingroup\$ This seems to fail on the empty string. \$\endgroup\$ Jun 19, 2017 at 21:34
0
\$\begingroup\$

05AB1E, 15 bytes

.œé.Δεā<._ć›P}P

Try it online or verify all test cases.

Explanation:

.œ            # Get all partitions of the (implicit) input-string
  é           # Sort them by length
   .Δ         # Find the first/shortest which is truthy for:
     ε        #  Map over each part of the current partition:
      ā       #   Push a list in the range [1,length] (without popping the part-string)
       <      #   Decrease it to a 0-based range [0,length)
        ._    #   For each value, rotate the string that many times
          ć   #   Extract head; pop and push remainder-list and first item separately
              #   (where the head is the unmodified part-string)
           ›  #   Check for each rotated part if it's lexicographically larger than the
              #   unmodified part-string
            P #   Check whether this is truthy for all rotations
     }P       #  After the inner map: check whether it's truthy for all parts in the
              #  partition
              # (after which the found result is output implicitly as result)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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