Dear Fellow Monks,

Let S be a set of given strings containing no newline character. I would like to "categorize" the strings in S by constructing a set R of n regular expressions r1, ..., rn of the form qr/^...$/ such that S1, ..., Sn - where Si denotes the subset of S consisting of the strings matched by ri (i=1, ..., n) - is a partition of S.

Needless to say I'm not interested in trivial partitions like induced by R = { qr/^.*$/ } or R = { qr/^s$/ for s in S }. The set R should rather be minimal in a sense I'm still unsure of how to define it but the following example should make it clear: For S = { a, b, c, aa, bb, ccc, aaaaa, bbb, cccccc, aaaaaaa, bbbb, ccccccc } I would like to construct R = { qr/^a+$/, qr/^b+$/, qr/^c+$/ }.

Do you know of a CPAN module that solves this problem? Or of any research papers that deal with it? I might have been searching for the wrong terms but Google hasn't been able to point me to something useful, yet.

In reply to Partitioning a set of strings by regular expressions by Locutus

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.