Problem 24

0から9の数字で順列を作って 1000000番めに大きい数を求めろという問題。
先頭が 0でも問題ないっていうのでだいぶ楽になったのかな〜と思います。
単純な方法だと単に 0123456789 から 9876543210まで数えていく方法だろうけど、
面倒なので楽な方法を考える。

10個の数字を並べるわけだから、順列は 10!個ある。なので一番初めの数は
(10-1)! * (n + 1)が1000000を越えるような nのはず。ここでは 2になる。
対象から 2をはずして、1000000から (10 - 1)! * n を引いた数に対して
同じことをすればいい。この操作を 10回繰り返せば答えが得られる。
答えは対象からはずした数を連結したものになる。

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

my %list = (0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9);
print "Answer is ", p24(1000000), "\n"; # Answer is 2783915460

sub p24 {
    my ($nth) = @_;
    my $answer = "";

    for (1..10){
        my @key    = sort keys %list;
        my $length = scalar @key;
        my $fact   = factorial($length - 1);

        for my $i (1..$length) {
            if (($fact * $i) >= $nth) {
                $nth   -= ($fact * ($i - 1));
                delete $list{$key[$i - 1]};
                $answer .= $key[$i - 1];
                last;
            }
        }
    }

    return $answer;
}

sub factorial {
    my ($n) = @_;
    my $sum = 1;

    map { $sum *= $_;} (1..$n);

    return $sum;
}