Re: make a 24(another practical problem)

[Steffen Müller]

Hi,

----- Original Message -----
From: "Greg Bacon" <[EMAIL PROTECTED]>
To: "user who" <[EMAIL PROTECTED]>; <[EMAIL PROTECTED]>;
<[EMAIL PROTECTED]>
Sent: Friday, January 18, 2002 6:58 PM
Subject: Re: make a 24(another practical problem)


> Here's a program that uses good ol' brute force.  An obvious bottleneck
> is the use of dc(1) to evaluate the RPN.

you could replace the permute function with the one below. It's a few times
faster, I think. MJD wrote it, I just modified it.

> #! /usr/local/bin/perl -w
>
> use strict;
>
> sub usage { "Usage: $0 target number_1 number_2 [ ... number_n ]\n" }
>
> sub permute {
>     my @items = @{ $_[0] };
>     my @perms = @{ $_[1] || [] };
>
>     unless (@items) {
>         return [ @perms ];
>     }
>     else {
>         my(@newitems,@newperms,$i);
>         my @result;
>
>         foreach $i (0 .. $#items) {
>             @newitems = @items;
>             @newperms = @perms;
>
>             unshift @newperms, splice @newitems, $i, 1;
>             push @result, permute([@newitems], [@newperms]);
>         }
>
>         @result;
>     }
> }

sub permute2 {
         my @items = @_;
         my @perms;
         my $n = 0;
         my $count = @items;
         my $iterate = 1;
         $iterate *= $count-- while $count > 1;
         while ( $n < $iterate ) {
           $n++, push @perms, [@items] if $n==0;
           my $i;
           my $p = $n;
           for ($i=1; $i<=@items && $p%$i==0; $i++) {
             $p /= $i;
           }
           my $d = $p % $i;
           my $j = @items - $i;
           if ($j < 0) {
             @items = reverse @items;
           } else {
             @items[$j+1..$#items] = reverse @items[$j+1..$#items];
             @items[$j,$j+$d] = @items[$j+$d,$j];
           }
           $n++;
           push @perms, [@items];
         };
         return @perms;
       }

Regards,
Steffen
--
$_=qq#tsee      gmx.net#;s#e#s#g;s#[^\s\w]#c#;s#s#ust#g;s#t#J#e;s#nus#ker#
;chop;$c=' ^^^^ ';$c='12319';@c=split/(..)/,'8234130006710523';@d=split"3"
,$c;chop;'  at  ';s#(t)ustust#$1\0ano$1;.#;y#.; #ehr#;@_=$_;shift@c,substr
$_[0],$_,1,chr(ord(substr$_[0],$_)-shift@c)for$d[0]..$d[1];print"$_[0]\n";