Re: Unique Character Combinations

Here it is without the need for a global array and BEGIN block:

use strict;
use warnings;

print join "\n", comb( 'A' .. 'C' );

sub comb {
    my @c_out = ();
    push @c_out, permute( '', $_, @_ ) for ( 0 .. $#_ );
    return @c_out;
}

sub permute {
    my @results;
    my ( $str, $depth, @chars ) = @_;
    if ( !$depth-- ) {
        foreach (@chars) {
            push @results, $str . $_;
        }
    }
    else {
        push @results,
          permute( $str . $chars[$_],
            $depth, @chars[ ( $_ + 1 ) .. ($#chars) ] )
          for ( 0 .. $#chars );
    }
    return @results;
}
[download]

Other clean-up is left as an exercise to the reader. ;)

thor

Feel the white light, the light within Be your own disciple, fan the sparks of will For all of us waiting, your kingdom will come

Comment on Re: Unique Character Combinations Download Code

Replies are listed 'Best First'.
Re^2: Unique Character Combinations by Roy Johnson (Monsignor) on May 02, 2005 at 15:24 UTC
With the other cleanup: `sub comb { map permute( '', $_, @_ ), ( 0 .. $#_ ); } sub permute { my ( $str, $depth, @chars ) = @_; map $str.$_, $depth ? (map permute( $chars[$_], $depth-1, @chars[ ( $_ + 1 ) .. ($#chars) ] ) , (0..$#chars)) : @chars; }` [download] That benchmarks about 10% faster than the original for me, but the powerset code below is 15x faster than either of them. `sub powerset { my ($car, @cdr) = @_; my @cdr_powerset = @cdr ? powerset(@cdr) : (); return # sort {length $a <=> length $b or $a cmp $b} ($car, map("$car$_", @cdr_powerset), @cdr_powerset); }` [download] If you include the sort that is currently commented out, the order will be correct, but the performance will degrade, though it is still about 7x faster for A..G. When I increase the range, the advantage for powerset increases. Even with the sort in place, it is 18x faster for A..L (30x without the sort). Caution: Contents may have been coded under pressure.	[reply] [d/l] [select]

Replies are listed 'Best First'.

Re^2: Unique Character Combinations
by Roy Johnson (Monsignor) on May 02, 2005 at 15:24 UTC

sub comb {
    map  permute( '', $_, @_ ), ( 0 .. $#_ );
}

sub permute {
    my ( $str, $depth, @chars ) = @_;
    map $str.$_,
      $depth
    ? (map permute( $chars[$_],
            $depth-1, @chars[ ( $_ + 1 ) .. ($#chars) ] )
       , (0..$#chars))
        : @chars;
}
[download]

sub powerset {
    my ($car, @cdr) = @_;
    my @cdr_powerset = @cdr ? powerset(@cdr) : ();
    return
#     sort {length $a <=> length $b or $a cmp $b}
      ($car, map("$car$_", @cdr_powerset), @cdr_powerset);
}
[download]

Caution: Contents may have been coded under pressure.

[reply]
[d/l]
[select]