Re: possible combinations in sequence

[roboticus]

in reply to possible combinations in sequence

ruzam:

Here's my stab at it. I took out the hash because my method doesn't generate duplicates. Instead I just return the list of results:

#!/usr/bin/perl -w
use strict;
use warnings;

# initial source in sequence order
my $source = 'horse:cow:dog:cat';

function($source);

# and now the results
foreach (function($source)) {
    print "$_\n";
}

# generate array of combinations
sub function {
    my @t = split /:/, shift;
    my @res=(shift @t);
    for my $i (@t) {
        @res=($i, @res, map{$_.':'.$i} @res);
    }
    return @res;
}

UPDATE: I didn't benchmark it because I've never used that module before. (I'll have to go install it and read up on it.) But I submitted it because I suspect that generating the strings from components might be faster than removing chunks. Any benchmarking ninjas out there wanna help me out?

--roboticus

[ruzam]

Whollopin Websnappers!
Taking a decisive lead, and proving yet again that simplicity is beauty: roboticus++

source: horse:cow:dog:cat
             Rate     ruzam  ikegami3     rhesa    rhesa2 roboticus
ruzam      4655/s        --      -62%      -66%      -66%      -80%
ikegami3  12238/s      163%        --      -10%      -11%      -47%
rhesa     13612/s      192%       11%        --       -1%      -41%
rhesa2    13742/s      195%       12%        1%        --      -40%
roboticus 22986/s      394%       88%       69%       67%        --

source: horse
              Rate  ikegami3     ruzam     rhesa    rhesa2 roboticus
ikegami3   41518/s        --      -36%      -64%      -72%      -84%
ruzam      64752/s       56%        --      -43%      -56%      -75%
rhesa     113875/s      174%       76%        --      -22%      -56%
rhesa2    146152/s      252%      126%       28%        --      -43%
roboticus 257311/s      520%      297%      126%       76%        --

source: horse:cat
             Rate     ruzam  ikegami3     rhesa    rhesa2 roboticus
ruzam     27050/s        --       -3%      -53%      -59%      -72%
ikegami3  27836/s        3%        --      -52%      -57%      -71%
rhesa     57415/s      112%      106%        --      -12%      -40%
rhesa2    65371/s      142%      135%       14%        --      -32%
roboticus 96089/s      255%      245%       67%       47%        --

source: horse:cow:cat
             Rate     ruzam  ikegami3     rhesa    rhesa2 roboticus
ruzam     10920/s        --      -43%      -61%      -64%      -76%
ikegami3  19183/s       76%        --      -32%      -37%      -59%
rhesa     28259/s      159%       47%        --       -7%      -39%
rhesa2    30244/s      177%       58%        7%        --      -35%
roboticus 46412/s      325%      142%       64%       53%        --

source: horse:cow:dog:cat:mouse
             Rate     ruzam    rhesa2     rhesa  ikegami3 roboticus
ruzam      1855/s        --      -67%      -68%      -72%      -82%
rhesa2     5676/s      206%        --       -2%      -14%      -45%
rhesa      5781/s      212%        2%        --      -13%      -44%
ikegami3   6614/s      257%       17%       14%        --      -36%
roboticus 10353/s      458%       82%       79%       57%        --

source: horse:cow:dog:cat:rat:mouse
            Rate     ruzam    rhesa2     rhesa  ikegami3 roboticus
ruzam      799/s        --      -70%      -70%      -77%      -85%
rhesa2    2659/s      233%        --       -0%      -24%      -50%
rhesa     2667/s      234%        0%        --      -24%      -50%
ikegami3  3521/s      340%       32%       32%        --      -34%
roboticus 5371/s      572%      102%      101%       53%        --

[ikegami]

If you want a huge speed boost, replace
@rv=($i, @rv, map{$_.':'.$i} @rv);
with
push @rv, $i, map{$_.':'.$i} @rv;

By the way, I found confusing the use of $i for something which is not an index and not even numerical. $part would have worked fine, since it's an element of @parts. Well, it was named @parts before you renamed to worthless @t. Nice algorithm, but shoddy code.

[roboticus]

ikegami:

Thanks for the tip on the speed boost. Once I get the benchmarking stuff installed I'll play with it. While I do like your suggestion, I prefer the order that my method generates--all one-word combinations first, then the two-word combinations, etc.)

Re: shoddy code. Yeah, I guess so, consider me properly admonished. ++ for calling me on it and keeping me honest. When I thunk up the technique to use, I just erased the original function body and started whacking away at it. I didn't think to clarify things by using better variable names. (Of course, I just came off of a little golfing trip so my head was in "trim keystrokes" mode.</lame_excuse_mode>) Now, I guess the proper thing to do is to clean it up a little and insert your suggestion, so here goes:

<pedagogical_mode>

sub function {
    my @parts = split /:/, shift;

    # Null is the complete list of combinations for
    # an empty word list
    my @combinations=();

    # Sequentially (recursively with tail recursion
    # removed) rebuild the combination list adding one
    # new word each iteration
    for my $new_word (@parts) {

        # Given a complete set of combinations for a
        # given list of words, we can add a new word to
        # the list and generate all new valid combinations
        # by concatenating to the original list:
        push @combinations,

              # the new word (a single word is a valid
              # combination)
              $new_word,

              # and the original list with the new word
              # glommed onto the end of each member
              map {$_.':'.$new_word} @combinations
              ;
    }
    return @combinations;
}

</pedagogical_mode>

--roboticus

[ruzam]

Just when you thought it couldn't get any faster...
Here's a comparison of the revised roboticus version (with ikegami's speed suggestion):

source: horse:cow:dog:cat
              Rate      ruzam  roboticus roboticus2
ruzam       4695/s         --       -80%       -86%
roboticus  23049/s       391%         --       -33%
roboticus2 34607/s       637%        50%         --

source: horse
               Rate      ruzam roboticus2  roboticus
ruzam       64954/s         --       -71%       -76%
roboticus2 223392/s       244%         --       -16%
roboticus  266354/s       310%        19%         --

source: horse:cat
               Rate      ruzam  roboticus roboticus2
ruzam       26625/s         --       -72%       -76%
roboticus   96711/s       263%         --       -13%
roboticus2 111706/s       320%        16%         --

source: horse:cow:cat
              Rate      ruzam  roboticus roboticus2
ruzam      11023/s         --       -77%       -82%
roboticus  46987/s       326%         --       -24%
roboticus2 62225/s       465%        32%         --

source: horse:cow:dog:cat:mouse
              Rate      ruzam  roboticus roboticus2
ruzam       1913/s         --       -82%       -89%
roboticus  10826/s       466%         --       -39%
roboticus2 17652/s       823%        63%         --

source: horse:cow:dog:cat:rat:mouse
             Rate      ruzam  roboticus roboticus2
ruzam       798/s         --       -85%       -91%
roboticus  5253/s       559%         --       -43%
roboticus2 9221/s      1056%        76%         --


The new function is now an magnitude faster than my original attempt. That's no small change. Is this the limit of optimizing or can yet more juice be squeezed out of this function?