Project Euler で紹介されている問題24を解いてみました。使うプログラミング言語が順列をサポートしていれば楽に解ける問題です。
Project Euler 問題24（辞書式順列）
順列とは、オブジェクトを順序よく並べたものである。例えば、3124 は 1、2、3、4 という数字の順列の1つとなる。数字またはアルファベット順にすべて並べた順列を辞書式順列と呼ぶ。0, 1, 2 の辞書式順列は次となる。
012 021 102 120 201 210
0, 1, 2, 3, 4, 5, 6, 7, 8, 9 の辞書式順列で、100万番目の数を求めよ。
解答例
プログラミング言語が順列をサポートしていれば、プログラミングは楽です。
C++ の解答例
C++ の標準ライブラリでは、この問題を解くのにぴったりな「next_permutation」という関数が用意されています。引数で与えた順列に対して、辞書式順列として、次の順列を返します。
配列 n に 0 から 9 までの数字を格納します。これが辞書式順列で最初の順列となります。999999 回 next_permutation を呼び出せば、100万番目の順列が求まります。また、10桁の数となるため、32bit整数を超える場合があります。そのため、解答として出力する変数 answer は long long int 型にしました。
この関数を使った C++ の解答例です。
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int n[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
for (int i = 1; i < 1000000; ++i) {
next_permutation(n, n + 10);
}
long long int answer = 0;
for (int i = 0; i < 10; ++i) {
answer = answer * 10 + n[i];
}
cout << "Problem024: " << answer << endl;
return 0;
}Python の解答例
Python では、標準モジュール itertools で順列を生成する関数が用意されています。
次のプログラム例は、すべての順列を生成して100万番目の順列を取り出しています。すべての順列を生成しているため、消費メモリは多いですが、簡単なプログラムで問題を解くことができています。
"""Project Euler Problem024"""
import itertools
answer = 0
for i in list(itertools.permutations(range(10)))[1000000 - 1]:
answer = answer * 10 + i
print("Problem024: " + str(answer))C でライブラリを実装する
C には、順列を生成する標準ライブラリがありません。そのため、自分で作る必要があります。C++ の「next_permutation」に近い関数「next_perm」を実装しました。
この関数は、「改訂新版 C言語によるアルゴリズム事典」（奥村晴彦著 技術評論社 1991年）の「順列」の項を参考にしました。ただし、C++ の「next_permutation」に似せるために、インターフェイスを変更しています。
#include <stdio.h>
int next_perm(int p[], int n)
{
int i, j, t;
i = n - 2;
while ((i >= 0)&&(p[i] >= p[i + 1])) {
--i;
}
if (i == -1) {
return 0;
}
j = n - 1;
while (p[i] >= p[j]) {
--j;
}
t = p[i];
p[i] = p[j];
p[j] = t;
++i;
j = n - 1;
while (i < j) {
t = p[i];
p[i] = p[j];
p[j] = t;
++i;
--j;
}
return 1;
}
int main()
{
int n[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
int i;
long long int answer = 0;
for (i = 1; i < 1000000; ++i) {
next_perm(n, 10);
}
for (i = 0; i < 10; ++i) {
answer = answer * 10 + n[i];
}
printf("Problem024: %lld\n", answer);
return 0;
}最後に
順列は、高校数学の科目である数学A「場合の数と確率」で履修します。高校数学として習う手計算の方法と、コンピュータを使った解法は、性質が違う場合が多いですが、それぞれの楽しさがあります。
引き続き、Project Euler の問題を紹介していきます。
