Math Battle [ 0170: Perl の順列機能 ] ]

[ 0170: Perl の順列機能 ]

[ 湯会老人の補足 ]

1 から 9 までの数字を一つずつ使って、
次の条件を満たす 9 桁の整数を作りなさい。

上位 n 桁を取り出した数は n で割り切れる。
(n は 1 から 9 まで)

こういう数は 1 個しかありません。見つかるかな？

単純に 123456789〜987654321 の範囲をチェックしますと、
864197533 回ものループを回すことになり極端に非効率です。

これに対して 5 桁目の 5 を自明で固定とすれば、
(1, 2, 3, 4, 6, 7, 8, 9) の順列をチェック対象とすればよいことになり
8! = 40320とおり。実に 2 万分の1 (!!!) 以下の処理時間ですむことになります。

これを使わない手はない。
さっそく、Math::Permute を自分の Perl 環境に追加インストールしました。

改造した Perl ソースコードは以下のとおりです。

#!/usr/local/bin/perl

use Math::Permute::Array;

# a5は5で固定とする。
@digits = (1,2,3,4,6,7,8,9);
$p = new Math::Permute::Array(\@digits);
foreach $i (0..$p->cardinal()-1) {
　($a1,$a2,$a3,$a4,$a6,$a7,$a8,$a9)
　　= @{$p->permutation($i)};
　$count++;
　next unless (($a2 % 2) == 0);
　next unless ((($a1+$a2+$a3) % 3) == 0);
　next unless ((($a3*10+$a4) % 4) == 0);
　next unless (($a6 % 2) == 0);
　next unless ((($a4+5+$a6) % 3) == 0);
　next unless (((($a1+500+$a6*10+$a7)
　　- ($a2*100+$a3*10+$a4)) % 7) == 0);
　next unless ((($a6*100+$a7*10+$a8) % 8) == 0);

　# 生き残った数を書き出す。
　printf ("Bingo: %1d%1d%1d%1d5%1d%1d%1d%1d\n",
　　$a1,$a2,$a3,$a4,$a6,$a7,$a8,$a9);
}
printf("Checked %d numbers\n", $count);

これで「上位 n 桁を取り出した数は n で割り切れる」という条件を
クリアーしています。
なお 1 から 9 までの数をどう並べてもできた数が 9 で割り切れることは
自明ですから、あえてプログラムでのチェックには入れていません。

実行は 1 秒もかかりませんでした。

Bingo: 381654729
Checked 40320 numbers

私は Permute 機能のインストールにあたって次のサイトを参考にしました。

https://metacpan.org/pod/Math::Permute::Array

以上、必要に応じてご参考になさってください。

[ 0181: 次の記事 ]

[ 0180: 放物線に内接する四角形 ]

[ 0179: 萬福ラーメンができる前に ]

[ 0178: 1,2,3,4,12345 ]

[ 0177: 0069再考 ]

[ 0176: 関取記事リスト ]