Re: possible combinations in sequence

in reply to possible combinations in sequence

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;
}
[download]

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

Comment on Re: possible combinations in sequence Download Code

Replies are listed 'Best First'.
Re^2: possible combinations in sequence by ikegami (Patriarch) on Jun 09, 2006 at 06:04 UTC
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.	[reply] [d/l] [select]
Re^3: possible combinations in sequence by roboticus (Chancellor) on Jun 09, 2006 at 12:10 UTC
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; } [download] </pedagogical_mode> --roboticus	[reply] [d/l]
Re^4: possible combinations in sequence by ruzam (Curate) on Jun 09, 2006 at 14:15 UTC
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% -- [download] 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?	[reply] [d/l]
Re^5: possible combinations in sequence by roboticus (Chancellor) on Jun 13, 2006 at 12:23 UTC
Re^2: possible combinations in sequence by ruzam (Curate) on Jun 09, 2006 at 05:39 UTC
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% -- [download]	[reply] [d/l]

In Section Cool Uses for Perl