перестановки

[ocehb]

sub shuffle (@) {
    return ( [ $_[0],$_[1] ],[ $_[1],$_[0] ] ) if (scalar @_ == 2);

    my $b = shift @_;
    my @ret;
    foreach my $r (shuffle (@_)) {
        foreach (0..scalar @$r) {
            my (@rr) = @$r;
            splice @rr,$_,0,$b;
            push @ret,\@rr;
        }
    }
    return @ret;
}

# time perl a.pl 1 2 3 4 5 6 | wc -l
     720
Real: 0.07s User: 0.05s System: 0.01s Percent: 90%% Cmd: perl a.pl 1 2 3 4 5 6
Real: 0.07s User: 0.00s System: 0.00s Percent: 5%% Cmd: wc -l
# time perl a.pl 1 2 3 4 5 6 7 8 9 | wc -l
  362880
Real: 7.43s User: 6.65s System: 0.63s Percent: 98%% Cmd: perl a.pl 1 2 3 4 5 6 7 8 9
Real: 7.42s User: 0.07s System: 0.01s Percent: 1%% Cmd: wc -l
# time perl a.pl 1 2 3 4 5 6 7 8 9 0 | wc -l
Out of memory during request for 1012 bytes, total sbrk() is 536786944 bytes!
       0
Real: 56.49s User: 16.54s System: 4.47s Percent: 37%% Cmd: perl a.pl 1 2 3 4 5 6 7 8 9 0
Real: 56.49s User: 0.00s System: 0.00s Percent: 0%% Cmd: wc -l
#

Comments

Re: хех. умеет :)

[rmrfchik.livejournal.com]

А чего тут спорить-то?
Так и говори — "каюсь, слил".
Последняя операция в return i+ff(i-1) это +. Хорошо заметно, если переписать в лисповом стиле (не зря примеры в статье приведены на лиспе): (+ i (ff (- i 1)))
А вот как будет выглядет остаточная рекурсия:

int ff (int i, int acc)
{
if (i == 1) return acc;
return ff (i-1, acc + i);
}
int main (int argc,char** argv)
{
int num = atoi (argv[1]);
printf ("%d => %d\n",num,ff (num,0));
exit (0);
}

Re: хех. умеет :)

[ocehb]

да до этого я дошел уже, просто бегать сегодня надо.