And now for something a little different...

This method certainly won't win any speed prizes. And I'm not even sure why I did it -- except just to see it work. It relies on the fact that any composite number can be factored but one way into its constituent primes. We begin by assigning each letter of the alphabet a unique prime number. Each unordered string of letters -- a set, really -- can be represented as the product of the primes those letters represent. The difference between two strings, then, will be the quotient of the first product divided by the second, factored into its constituent primes and converted back to letters. This is assuming that the numbers evenly divide, i.e. that the remainder of the division is zero. If not, the string difference is undefined, because it means the second string has letters in it not contained in the first.

The following program illustrates the technique: 

use Math::BigInt;
@Primes = (2,3,5,7,11,13,17,19,23,29,31,37,41,
    43,47,53,59,61,67,71,73,79,83,89,97,101);
@AsciiPrimes = ((0) x 65, @Primes, (0) x 6, @Primes, (0) x 133);

print StringDif('abcdgoldfish', 'flash'),"\n";
print StringDif('lmnogoldfish', 'dish'),"\n";
print StringDif('osar', 'oar'),"\n";

sub StringDif {
    my ($StrA, $StrB) = @_;
    my $A = Math::BigInt->new(1);
    my $B = Math::BigInt->new(1);
    my $Quot, $Rem, $NewQuot, $ReturnStr;
    foreach (unpack 'C*', $StrA) {$A *= $AsciiPrimes[$_]}
    foreach (unpack 'C*', $StrB) {$B *= $AsciiPrimes[$_]}
    if ($A eq '+0' or $B eq '+0') {
        warn "Non-letter in string"; return undef
    }
    ($Quot, $Rem) = Math::BigInt->new($A)->bdiv($B);
    return undef unless $Rem eq '+0';
    $ReturnStr = '';
    foreach('a'..'z') {
        do {
            ($NewQuot, $Rem) = Math::BigInt->new($Quot)
                ->bdiv($AsciiPrimes[ord $_]);
            if ($Rem eq '+0') {
                $ReturnStr .= $_;
                $Quot = $NewQuot
            }
        } while $Rem eq '+0' 
    }
    return $ReturnStr
}

[download]
Note that, due to the use of Math::BigInt, strings can be as long as you like. Also, even though the input strings don't have to be sorted, the output string will be.

In reply to Re: Difference Of Two Strings by Dr. Mu
in thread Difference Of Two Strings by YuckFoo

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.