0 から N - 1 までの N 個の数字の順列は N! 通りあります。この順列に 0 から N! - 1 までの番号を付けるプログラムを作ってください。
たとえば、0 から 8 までの 9 個の整数の順列で、番号の振り方を考えてみましょう。最初が 0 で始まるパターンは 8! = 40320 通りありますね。このパターンには 0 - 40319 までの番号を割り当てます。そして、1 で始まるパターンには 40320 - 80639 までの番号を割り当てます。残りのパターンも同じです。
次に 2 番目の数字を考えましょう。01 で始まるパターンは 7! = 5040 通りあります。 したがって、このパターンには 0 - 5039 までの番号を割り当てます。10 で始まるパターンには 40320 - 45359 までの番号を、12 で始まるパターンには 45360 - 50399 までの番号を割り当てます。あとはこれを 9 番目までの数字まで続ければ、すべてパターンに番号を割り当てることができます。
では実際に 867254301 というパターンで試してみましょう。次の図を見てください。
８ 8 * 8! ６ [0 1 2 3 4 5 6 7] : 8*8! + 6*7! ７ [0 1 2 3 4 5 7] : 8*8! + 6*7! + 6*6! ２ [0 1 2 3 4 5] : 8*8! + 6*7! + 6*6! + 2*5! ５ [0 1 3 4 5] : 8*8! + 6*7! + 6*6! + 2*5! + 4*4! ４ [0 1 3 4] : 8*8! + 6*7! + 6*6! + 2*5! + 4*4! + 3*3! ３ [0 1 3] : 8*8! + 6*7! + 6*6! + 2*5! + 4*4! + 3*3! + 2*2! ０ [0 1] : 8*8! + 6*7! + 6*6! + 2*5! + 4*4! + 3*3! + 2*2! + 0*1! １ [1] : 番号 : 357478
注意すべき点は、数字をそのまま掛け算してはいけないところです。たとえば、7 に注目してください。このとき、残されている数字は 0, 1, 2, 3, 4, 5, 7 がありますね。番号は順番に振っていくので、867 は 86 で始まるパターンの 6*6! 番目から始まるのです。つまり、残っている数字の中で何番目に位置しているのかを求める必要があります。今回は参考文献『Ｃ言語による最新アルゴリズム事典』に紹介されている方法を使います。次の図を見てください。
8|6 7 2 5 4 3 0 1
6 7 2 5 4 3 0 1 : 8 より大きな数字を -1 する
8 6|7 2 5 4 3 0 1
6 2 5 4 3 0 1 : 6 より大きな数字を -1 する
8 6 6|2 5 4 3 0 1
2 5 4 3 0 1 : 6 より大きな数字を -1 する
8 6 6 2|5 4 3 0 1
4 3 2 0 1 : 2 より大きな数字を -1 する
8 6 6 2 4|3 2 0 1
3 2 0 1 : 4 より大きな数字を -1 する
・・・省略・・・
8 6 6 2 4 3 2 0 0
2 番目の 6 に注目してください。次の数字 7 は 6 より大きいですね。6 が使われたのですから、7 は 7 番目ではなく 6 番目になるわけです。つまり、数字ではなく位置を表していると考えるのです。自分よりも前にある数字を使ったならば、位置を -1 して前に詰めればいいわけです。あとはこれを繰り返すだけです。
問題 41 の逆で、番号から順列を求めるプログラムを作ってください。
m 個の整数 1, 2, ..., m の順列を考えます。このとき、i 番目 (先頭要素が 1 番目) の要素が整数 i ではない順列を「完全順列」といいます。簡単な例を示しましょう。
1 - 3 の完全順列 2 3 1 3 1 2
1 - 4 の完全順列 2 1 4 3 2 3 4 1 2 4 1 3 3 1 4 2 3 4 1 2 3 4 2 1 4 1 2 3 4 3 1 2 4 3 2 1
1 から m までの整数値で完全順列を生成するプログラムを作ってください。
完全順列の総数を「モンモール数 (Montmort number)」といいます。モンモール数は次の漸化式で求めることができます。
モンモール数を long long int で求める関数 montmort_number を定義してください。
montmort_number(1) => 0 montmort_number(2) => 1 montmort_number(3) => 2 montmort_number(4) => 9 montmort_number(5) => 44 montmort_number(6) => 265 montmort_number(7) => 1854 montmort_number(10) => 1334961 montmort_number(20) => 895014631192902121
バランスの取れた n 対のカッコ列を画面に表示する関数 kakko を定義してください。カッコ列は ( と ) からなる列のことで、バランスが取れているカッコ列は、右カッコで閉じることができる、つまり右カッコに対応する左カッコがある状態のことをいいます。たとえば n = 1 の場合、( ) はバランスの取れたカッコ列ですが、) ( はバランスが取れていません。
kakko(3) => (画面に表示) ((())) (()()) (())() ()(()) ()()() kakko(4) => (画面に表示) (((()))) ((()())) ((())()) ((()))() (()(())) (()()()) (()())() (())(()) (())()() ()((())) ()(()()) ()(())() ()()(()) ()()()()
バランスの取れた n 対のカッコ列の総数を long long int で求める関数 kakko_number を定義してください。
kakkoNum(1) => 1 kakkoNum(2) => 2 kakkoNum(3) => 5 kakkoNum(4) => 14 kakkoNum(5) => 42 kakkoNum(6) => 132 kakkoNum(7) => 429 kakkoNum(8) => 1430 kakkoNum(9) => 4862 kakkoNum(10) => 16796 kakkoNum(30) => 3814986502092304
整数 n を 1 以上の自然数の和で表すことを考えます。これを「整数の分割」といいます。整数を分割するとき、同じ自然数を何回使ってもかまいませんが、並べる順序が違うだけのものは同じ分割とします。簡単な例を示します。
n = 6
6 分割 : 1 + 1 + 1 + 1 + 1 + 1
5 分割 : 1 + 1 + 1 + 1 + 2
4 分割 : 1 + 1 + 1 + 3
1 + 1 + 2 + 2
3 分割 : 1 + 1 + 4
1 + 2 + 3
2 + 2 + 2
2 分割 : 1 + 5
2 + 4
3 + 3
1 分割 : 6
6 の場合、分割の仕方は 11 通りあります。この数を「分割数」といいます。自然数 n の分割数を long long int で求める関数 partition_number を定義してください。
partitionNumber(1) => 1 partitionNumber(2) => 2 partitionNumber(3) => 3 partitionNumber(4) => 5 partitionNumber(5) => 7 partitionNumber(6) => 11 partitionNumber(7) => 15 partitionNumber(8) => 22 partitionNumber(10) => 42 partitionNumber(50) => 204226
整数 n の分割の仕方をすべて求める関数 partition_of_int を定義してください。
partition_of_int(6) => (画面に出力) 6 5 1 4 2 4 1 1 3 3 3 2 1 3 1 1 1 2 2 2 2 2 1 1 2 1 1 1 1 1 1 1 1 1 1
「ラテン方陣」は数独の枠の条件を無くした方陣です。ラテン方陣の定義を参考文献『数理パズルのはなし』より引用します。
『ラテン方陣を一般的にいうなら、n 行 n 列の正方形の枡に n 種類の記号を n 個ずつ配列して、各行各列に記号の重複のないものを n 次のラテン方陣というのです。』
このラテン方陣をパズルに応用したものが数独というわけです。簡単な例を示しましょう。3 次のラテン方陣は次に示す 12 通りになります。
0 1 2 0 1 2 0 2 1 0 2 1 1 0 2 1 0 2
1 2 0 2 0 1 1 0 2 2 1 0 0 2 1 2 1 0
2 0 1 1 2 0 2 1 0 1 0 2 2 1 0 0 2 1
標準形
1 2 0 1 2 0 2 0 1 2 0 1 2 1 0 2 1 0
0 1 2 2 0 1 0 1 2 1 2 0 0 2 1 1 0 2
2 0 1 0 1 2 1 2 0 0 1 2 1 0 2 0 2 1
図 : 3 次のラテン方陣
この中で、最初の行と列の要素を昇順に並べたものを「標準形」といいます。3 次のラテン方陣の場合、標準形は 1 種類しかありません。ラテン方陣は任意の行を交換する、または任意の列を交換してもラテン方陣になります。3 次のラテン方陣の場合、標準形から行または列を交換することで、残りの 11 種類のラテン方陣を生成することができます。
4, 5, 6, 7 次の標準形ラテン方陣の総数を求めてください。
┏━┯━┯━┳━┯━┯━┓ ┃１│２│３┃４│５│６┃ ┠─┼─┼─╂─┼─┼─┨ ┃４│５│６┃１│２│３┃ ┣━┿━┿━╋━┿━┿━┫ ┃２│１│４┃３│６│５┃ ┠─┼─┼─╂─┼─┼─┨ ┃３│６│５┃２│１│４┃ ┣━┿━┿━╋━┿━┿━┫ ┃５│３│１┃６│４│２┃ ┠─┼─┼─╂─┼─┼─┨ ┃６│４│２┃５│３│１┃ ┗━┷━┷━┻━┷━┷━┛ 図 : 数独 (6 行 6 列盤) の解 (一例)
上図に示す 6 行 6 列盤の数独において、数独の解となる盤面の総数を求めてください。
リスト : 順列を番号に変換
#define N 20
// 階乗 (long long では 20! まで)
long long fact(int n)
{
long long x = 1;
while (n > 1) x *= n--;
return x;
}
long long perm_to_num(int *buff, int size)
{
int value = 0, work[N];
for (int i = 0; i < size; i++) work[i] = buff[i];
for (int i = 0; i < size - 1; i++) {
value += fact(size - 1 - i) * work[i];
for (int j = i + 1; j < size; j++) {
if (work[i] < work[j]) work[j]--;
}
}
return value;
}
順列を表す配列 buff を work にコピーして番号に変換します。buff の内容を破壊してもよければ、コピーする必要はありません。あとは説明したことをそのままプログラムしただけなので、とくに難しいところはないと思います。
番号を順列に変換することも簡単です。たとえば、0 から 8 までの 9 個の整数の順列で、番号 357478 を順列に変換してみましょう。次の図を見てください。配列 buffer に 0 から 8 までの数字を昇順にセットします。そして、配列の先頭から数字を決定していきます。変数 i が決定する配列の位置を表します。357478 / 8! は 8 になるので、buffer[0] の数字は buffer[0 + 8] の要素 8 になります。要素 8 を取り出して bufer[0] に挿入します。要素を交換するのではなく、他の要素はひとつ右へ移動することに注意してください。
次は buffer[1] の数字を決定します。値を 357478 % 8! = 34918 に更新し、i をインクリメントします。34918 / 7! は 6 になるので、buffer[1 + 6] の要素 6 を buffer[1] に挿入します。つまり、変数 i から末尾までの要素の中から数字を選んでいくわけです。あとはこれを繰り返すことで順列に変換することができます。
変数 i ↓ buffer [０ １ ２ ３ ４ ５ ６ ７ ８] 357478 / 8! = 8, buffer[i + 8] を buffer[i] に挿入 357478 % 8! = 34918 変数 i ↓ buffer [８ ０ １ ２ ３ ４ ５ ６ ７] 34918 / 7! = 6, buffer[i + 6] を buffer[i] に挿入 34918 % 7! = 4678 変数 i ↓ buffer [８ ６ ０ １ ２ ３ ４ ５ ７] 4678 / 6! = 6, buffer[i + 6] を buffer[i] に挿入 4678 % 6! = 358 変数 i ↓ buffer [８ ６ ７ ０ １ ２ ３ ４ ５] 358 / 5! = 2, buffer[i + 2] を buffer[i] に挿入 358 % 5! = 118
変数 i ↓
buffer [８ ６ ７ ２ ０ １ ３ ４ ５]
118 / 4! = 4, buffer[i + 4] を buffer[i] に挿入
118 % 4! = 22
変数 i ↓
buffer [８ ６ ７ ２ ５ ０ １ ３ ４]
22 / 3! = 3, buffer[i + 3] を buffer[i] に挿入
22 % 3! = 4
変数 i ↓
buffer [８ ６ ７ ２ ５ ４ ０ １ ３]
4 / 2! = 2, buffer[i + 2] を buffer[i] に挿入
4 % 2! = 0
↓
buffer [８ ６ ７ ２ ５ ４ ３ ０ １]
0 / 1! = 0, buffer[i + 0] を buffer[i] に挿入
↓
buffer [８ ６ ７ ２ ５ ４ ３ ０ １] 終了
プログラムは次のようになります。
リスト : 番号を順列に変換する (番号は 0 から開始)
void num_to_perm(long long n, int *buff, int size)
{
for (int i = 0; i < size; i++) buff[i] = i;
for (int i = 0; i < size - 1; i++) {
long long m = fact(size - 1 - i);
long long p = n / m;
int x = buff[i + p];
for (int k = i + p; k > i; k--) {
buff[k] = buff[k - 1];
}
buff[i] = x;
n %= m;
}
}
説明したことをそのままプログラムしただけなので、特に難しいところはないと思います。
リスト : 順列を番号に変換する (yacp41.c)
#include <stdio.h>
#include <stdbool.h>
// long long で 20! まで
#define N 20
// 階乗
long long fact(int n)
{
long long x = 1;
while (n > 1) x *= n--;
return x;
}
// 順列を番号に変換
long long perm_to_num(int *buff, int size)
{
int value = 0, work[N];
for (int i = 0; i < size; i++) work[i] = buff[i];
for (int i = 0; i < size - 1; i++) {
value += fact(size - 1 - i) * work[i];
for (int j = i + 1; j < size; j++) {
if (work[i] < work[j]) work[j]--;
}
}
return value;
}
// 番号を順列に変換
void num_to_perm(long long n, int *buff, int size)
{
for (int i = 0; i < size; i++) buff[i] = i;
for (int i = 0; i < size - 1; i++) {
long long m = fact(size - 1 - i);
long long p = n / m;
int x = buff[i + p];
for (int k = i + p; k > i; k--) {
buff[k] = buff[k - 1];
}
buff[i] = x;
n %= m;
}
}
// テスト
int buffer[N];
bool used[N];
void make_perm(int n, int size)
{
if (n == size) {
for (int i = 0; i < size; i++)
printf("%d ", buffer[i]);
printf("=> %lld\n", perm_to_num(buffer, size));
} else {
for (int i = 0; i < size; i++) {
if (used[i]) continue;
buffer[n] = i;
used[i] = true;
make_perm(n + 1, size);
used[i] = false;
}
}
}
int main(void)
{
int buff1[] = {0, 1, 2, 3, 4, 5, 6, 7, 8};
int buff2[] = {8, 7, 6, 5, 4, 3, 2, 1, 0};
printf("%lld\n", perm_to_num(buff1, 9));
printf("%lld\n", perm_to_num(buff2, 9));
make_perm(0, 4);
for (int i = 0; i < 24; i++) {
int buff3[4];
num_to_perm(i, buff3, 4);
for (int j = 0; j < 4; j++)
printf("%d ", buff3[j]);
printf("\n");
}
return 0;
}
$ clang yacp41.c $ ./a.out 0 362879 0 1 2 3 => 0 0 1 3 2 => 1 0 2 1 3 => 2 0 2 3 1 => 3 0 3 1 2 => 4 0 3 2 1 => 5 1 0 2 3 => 6 1 0 3 2 => 7 1 2 0 3 => 8 1 2 3 0 => 9 1 3 0 2 => 10 1 3 2 0 => 11 2 0 1 3 => 12 2 0 3 1 => 13 2 1 0 3 => 14 2 1 3 0 => 15 2 3 0 1 => 16 2 3 1 0 => 17 3 0 1 2 => 18 3 0 2 1 => 19 3 1 0 2 => 20 3 1 2 0 => 21 3 2 0 1 => 22 3 2 1 0 => 23 0 1 2 3 0 1 3 2 0 2 1 3 0 2 3 1 0 3 1 2 0 3 2 1 1 0 2 3 1 0 3 2 1 2 0 3 1 2 3 0 1 3 0 2 1 3 2 0 2 0 1 3 2 0 3 1 2 1 0 3 2 1 3 0 2 3 0 1 2 3 1 0 3 0 1 2 3 0 2 1 3 1 0 2 3 1 2 0 3 2 0 1 3 2 1 0
リスト : 完全順列
#define N 16
int buffer[N];
bool used[N];
void print_perm(int n)
{
for (int i = 0; i < n; i++)
printf("%d ", buffer[i]);
printf("\n");
}
void derangement(int n, int m)
{
if (n == m)
print_perm(m);
else {
for (int i = 0; i <= m; i++) {
if (used[i] || i == n + 1) continue;
buffer[n] = i;
used[i] = true;
derangement(n + 1, m);
used[i] = false;
}
}
}
関数 derangement は、基本的には 1 から m までの数字を m 個選ぶ順列を生成する処理と同じです。n 番目の数字を選ぶとき、数字 i が n + 1 と等しい場合は i を選択しません。n が m と等しい場合は m 個の数字を選んだので print_perm で表示します。これで完全順列を生成することができます。
リスト : 完全順列の総数
long long montmort_number(int n)
{
if (n == 1)
return 0;
else if (n == 2)
return 1;
else
return (n - 1) * (montmort_number(n - 1) + montmort_number(n - 2));
}
// 別解
long long montmort_number1(int n)
{
long long a = 0, b = 1;
for (int i = 1; i < n; i++) {
long long c = (i + 1) * (a + b);
a = b;
b = c;
}
return a;
}
関数 montmort_number は公式をそのままプログラムしただけです。二重再帰になっているので、実行速度はとても遅くなります。これを繰り返しに変換すると別解のようになります。考え方はフィボナッチ数列と同じです。変数 a に i 番目の値を、b に i + 1 番目の値を保存しておきます。すると、i + 2 番目の値は (i + 1) * (a + b) で計算することができます。あとは、b の値を a に、新しい値を b にセットして処理を繰り返すだけです。
リスト : 完全順列とモンモール数 (yacp43.c)
#include <stdio.h>
#include <stdbool.h>
#define N 16
int buffer[N];
bool used[N + 1];
void print_perm(int n)
{
for (int i = 0; i < n; i++)
printf("%d ", buffer[i]);
printf("\n");
}
// 完全順列
void derangement(int n, int m)
{
if (n == m)
print_perm(m);
else {
for (int i = 1; i <= m; i++) {
if (used[i] || i == n + 1) continue;
buffer[n] = i;
used[i] = true;
derangement(n + 1, m);
used[i] = false;
}
}
}
// モンモール数
long long montmort_number(int n)
{
if (n == 1)
return 0;
else if (n == 2)
return 1;
else
return (n - 1) * (montmort_number(n - 1) + montmort_number(n - 2));
}
// 別解
long long montmort_number1(int n)
{
long long a = 0, b = 1;
for (int i = 1; i < n; i++) {
long long c = (i + 1) * (a + b);
a = b;
b = c;
}
return a;
}
int main(void)
{
derangement(0, 3);
derangement(0, 4);
derangement(0, 5);
// long long では 20 まで
for (int i = 1; i <= 20; i++) {
printf("%d, %lld\n", i, montmort_number(i));
printf("%d, %lld\n", i, montmort_number1(i));
}
return 0;
}
$ clang yacp43.c $ ./a.out 2 3 1 3 1 2 2 1 4 3 2 3 4 1 2 4 1 3 3 1 4 2 3 4 1 2 3 4 2 1 4 1 2 3 4 3 1 2 4 3 2 1 2 1 4 5 3 2 1 5 3 4 2 3 1 5 4 2 3 4 5 1 2 3 5 1 4 2 4 1 5 3 2 4 5 1 3 2 4 5 3 1 2 5 1 3 4 2 5 4 1 3 2 5 4 3 1 3 1 2 5 4 3 1 4 5 2 3 1 5 2 4 3 4 1 5 2 3 4 2 5 1 3 4 5 1 2 3 4 5 2 1 3 5 1 2 4 3 5 2 1 4 3 5 4 1 2 3 5 4 2 1 4 1 2 5 3 4 1 5 2 3 4 1 5 3 2 4 3 1 5 2 4 3 2 5 1 4 3 5 1 2 4 3 5 2 1 4 5 1 2 3 4 5 1 3 2 4 5 2 1 3 4 5 2 3 1 5 1 2 3 4 5 1 4 2 3 5 1 4 3 2 5 3 1 2 4 5 3 2 1 4 5 3 4 1 2 5 3 4 2 1 5 4 1 2 3 5 4 1 3 2 5 4 2 1 3 5 4 2 3 1 1, 0 1, 0 2, 1 2, 1 3, 2 3, 2 4, 9 4, 9 5, 44 5, 44 6, 265 6, 265 7, 1854 7, 1854 8, 14833 8, 14833 9, 133496 9, 133496 10, 1334961 10, 1334961 11, 14684570 11, 14684570 12, 176214841 12, 176214841 13, 2290792932 13, 2290792932 14, 32071101049 14, 32071101049 15, 481066515734 15, 481066515734 16, 7697064251745 16, 7697064251745 17, 130850092279664 17, 130850092279664 18, 2355301661033953 18, 2355301661033953 19, 44750731559645106 19, 44750731559645106 20, 895014631192902121 20, 895014631192902121
リスト : カッコ列の生成
#define N 64
char buffer[N];
void kakko_sub(int x, int y, int m, int n)
{
if (x == y && x == m) {
buffer[n] = '\0';
printf("%s\n", buffer);
} else {
if (x < m) {
buffer[n] = '(';
kakko_sub(x + 1, y, m, n + 1);
}
if (y < x) {
buffer[n] = ')';
kakko_sub(x, y + 1, m, n + 1);
}
}
}
void kakko(int m)
{
kakko_sub(0, 0, m, 0);
}
カッコ列の生成は簡単です。関数 kakko_sub の引数 x が左カッコの個数、引数 y が右カッコの個数を表します。引数 n はカッコを配列 buffer に書き込む位置を表します。
バランスの取れたカッコ列の場合、x, y, m には y <= x <= m の関係が成り立ちます。x == y && y == m の場合、カッコ列がひとつ完成しました。buffer の終端にヌル文字を書き込んでから printf で表示します。そうでなければ、kakko_sub を再帰呼び出しします。x < m であれば左カッコを追加し、y < x であれば右カッコを追加します。これでカッコ列を生成することができます。
カタラン数 - Wikipedia によると、カッコ列の総数は「カタラン数 (Catalan number)」になるとのことです。カタラン数は次に示す公式で求めることができます。
これをそのままプログラムしてもいいのですが、それではちょっと面白くないので別な方法でプログラムを作ってみましょう。カタラン数は次に示す経路図において、A から B までの最短距離の道順を求めるとき、対角線を超えないものの総数に一致します。
Ｂ Ｂ
┌─┬─┬─┬─┐ ┌─┬─┬─０─14
│ │ │ │ │ │ │ │ │ │
├─┼─┼─┼─┤ ├─┼─０─５─14
│ │ │ │ │ │ │ │ │ │
├─┼─┼─┼─┤ ├─０─２─５─９
│ │ │ │ │ │ │ │ │ │
├─┼─┼─┼─┤ ０─１─２─３─４
│ │ │ │ │ │ │ │ │ │
└─┴─┴─┴─┘ １─１─１─１─１
Ａ Ａ
図 : 道順の総数の求め方
A からある地点にいたる最短距離の道順の総数は、左隣と真下の地点の値を足したものになります。一番下の地点は 1 で、対角線を越えた地点は 0 になります。あとは下から順番に足し算していけば、A から B までの道順の総数を求めることができます。上図の場合はカラタン数 Ｃ4 に相当し、その値は 14 となります。
プログラムは配列を使うと簡単です。次の図を見てください。
0 : [1, 1, 1, 1, 1] 1 : [1, 1, 1, 1, 1,] 2 : [1, 1, 1+1=2, 2+1=3, 3+1=4] => [1, 1, 2, 3, 4] 3 : [1, 1, 2, 3+2=5, 5+4=9] => [1, 1, 2, 5, 9] 4 : [1, 1, 2, 5, 5+9=14] => [1, 1, 2, 5, 14]
上図は Ｃn (n = 4) を求める場合です。大きさが n + 1, 要素の値が 1 の一次元配列を用意します。n = 0, 1 の場合は n 番目の要素をそのまま返します。n が 2 よりも大きい場合、変数 i を 2 に初期化して、i - 1 番目以降の要素の累積和を求めます。
たとえば i = 2 の場合、2 番目の要素は 1 番目の要素と自分自身を加算した値 2 になります。3 番目の要素は 2 番目の要素と自分自身を足した値 3 になり、4 番目の要素は 3 + 1 = 4 になります。次に i を +1 して同じことを繰り返します。3 番目の要素は 2 + 3 = 5 になり、4 番目の要素は 5 + 4 = 9 になります。i = 4 のとき、4 番目の要素は 5 + 9 = 14 となり、Ｃ4 の値を求めることができました。
プログラムは次のようになります。
リスト : カッコ列の総数
long long kakko_num(int n)
{
long long table[N];
for (int i = 0; i <= n; i++)
table[i] = 1;
for (int i = 2; i <= n; i++) {
for (int j = i; j <= n; j++) {
table[j] += table[j - 1];
}
}
return table[n];
}
説明したことをそのままプログラムしただけなので、とくに難しいところはないと思います。
リスト : カッコ列とカタラン数 (yacp45.c)
#include <stdio.h>
#define N 64
char buffer[N];
void kakko_sub(int x, int y, int m, int n)
{
if (x == y && x == m) {
buffer[n] = '\0';
printf("%s\n", buffer);
} else {
if (x < m) {
buffer[n] = '(';
kakko_sub(x + 1, y, m, n + 1);
}
if (y < x) {
buffer[n] = ')';
kakko_sub(x, y + 1, m, n + 1);
}
}
}
void kakko(int m)
{
kakko_sub(0, 0, m, 0);
}
long long kakko_num(int n)
{
long long table[N];
for (int i = 0; i <= n; i++)
table[i] = 1;
for (int i = 2; i <= n; i++) {
for (int j = i; j <= n; j++) {
table[j] += table[j - 1];
}
}
return table[n];
}
int main(void)
{
kakko(2);
kakko(3);
kakko(4);
// long long では 35 まで
for (int i = 1; i <= 35; i++)
printf("%d, %lld\n", i, kakko_num(i));
return 0;
}
$ clang yacp45.c $ ./a.out (()) ()() ((())) (()()) (())() ()(()) ()()() (((()))) ((()())) ((())()) ((()))() (()(())) (()()()) (()())() (())(()) (())()() ()((())) ()(()()) ()(())() ()()(()) ()()()() 1, 1 2, 2 3, 5 4, 14 5, 42 6, 132 7, 429 8, 1430 9, 4862 10, 16796 11, 58786 12, 208012 13, 742900 14, 2674440 15, 9694845 16, 35357670 17, 129644790 18, 477638700 19, 1767263190 20, 6564120420 21, 24466267020 22, 91482563640 23, 343059613650 24, 1289904147324 25, 4861946401452 26, 18367353072152 27, 69533550916004 28, 263747951750360 29, 1002242216651368 30, 3814986502092304 31, 14544636039226909 32, 55534064877048198 33, 212336130412243110 34, 812944042149730764 35, 3116285494907301262
─┬─ 6 : 6
│
├─ 5 ─ 1 : 5 + 1
│
├─ 4 ┬ 2 : 4 + 2
│ │
│ └ 1 ─ 1 : 4 + 1 + 1
│
├─ 3 ┬ 3 : 3 + 3
│ │
│ ├ 2 ─ 1 : 3 + 2 + 1
│ │
│ └ 1 ─ 1 ─ 1 : 3 + 1 + 1 + 1
│
├─ 2 ┬ 2 ┬ 2 : 2 + 2 + 2
│ │ │
│ │ └ 1 ─ 1 : 2 + 2 + 1 + 1
│ │
│ └ 1 ─ 1 ─ 1 ─ 1 : 2 + 1 + 1 + 1 + 1
│
└─ 1 ─ 1 ─ 1 ─ 1 ─ 1 ─ 1 : 1 + 1 + 1 + 1 + 1 + 1
図 : 整数 6 の分割
6 の場合、分割の仕方は上図のように 11 通りあります。分割の仕方を列挙する場合、整数 n から k 以下の整数を選んでいくと考えてください。まず、6 から 6 を選びます。すると、残りは 0 になるので、これ以上整数を分割することはできません。次に、6 から 5 を選びます。残りは 1 になるので、1 を選ぶしか方法はありません。
次に、4 を選びます。残りは 2 になるので、2 から 2 以下の整数を分割する方法になります。2 から 2 を選ぶと残りは 0 になるので 2 が得られます。1 を選ぶと残りは 1 になるので、1 + 1 が得られます。したがって、4 + 2, 4 + 1 + 1 となります。同様に、6 から 3 を選ぶと、残りは 3 から 3 以下の整数を選ぶ方法になります。
6 から 2 以下の整数を選ぶ方法は、残り 4 から 2 以下の整数を選ぶ方法になり、そこで 2 を選ぶと 2 から 2 以下の整数を選ぶ方法になります。1 を選ぶと 4 から 1 以下の整数を選ぶ方法になりますが、これは 1 通りしかありません。最後に 6 から 1 を選びますが、これも 1 通りしかありません。これらをすべて足し合わせると 11 通りになります。
整数 n を k 以下の整数で分割する総数を求める関数を p(n, k) とすると、p(n, k) は次のように定義することができます。
たとえば、p(6, 6) は次のように計算することができます。
p(6, 6) => p(0, 6) + p(6, 5)
=> 1 + p(1, 5) + p(6, 4)
=> 1 + 1 + p(2, 4) + p(6, 3)
=> 1 + 1 + 2 + 7
=> 11
p(2, 4) => p(-2, 4) + p(2, 3)
=> 0 + p(-1, 3) + p(2, 2)
=> 0 + 0 + p(0, 2) + p(2, 1)
=> 0 + 0 + 1 + 1
=> 2
p(6, 3) => p(3, 3) + p(6, 2)
=> p(0, 3) + p(3, 2) + p(4, 2) + p(6, 1)
=> 1 + p(1, 2) + p(3, 1) + p(2, 2) + p(4, 1) + 1
=> 1 + 1 + 1 + p(0, 2) + p(2, 1) + 1 + 1
=> 1 + 1 + 1 + 1 + 1 + 1 + 1
=> 7
分割数を求める関数 partition_number は、関数 p(n, k) を使うと次のようにプログラムすることができます。
リスト : 分割数
long long part_num(int n, int k)
{
if (n < 0 || k < 1)
return 0;
else if (n <= 1 || k == 1)
return 1;
else
return part_num(n - k, k) + part_num(n, k - 1);
}
long long partition_number(int n)
{
return part_num(n, n);
}
関数 part_num は p(n, k) の定義をそのままプログラムしただけです。ただし、このプログラムは二重再帰で何度も同じ値を求めているため実行速度はとても遅くなります。
「動的計画法」というアルゴリズムを使うと、大きな値でも高速に計算することができます。動的計画法については、拙作のページ Algorithms wit Python: 動的計画法 をお読みくださいませ。
次の図を見てください。
k 1 : [1, 1, 1, 1, 1, 1, 1] 2 : [1, 1, 1+1=2, 1+1=2, 2+1=3, 2+1=3, 3+1=4] => [1, 1, 2, 2, 3, 3, 4] 3: [1, 1, 2, 1+2=3, 1+3=4, 2+3=5, 3+4=7] => [1, 1, 2, 3, 4, 5, 7] 4: [1, 1, 2, 3, 1+4=4, 1+5=6, 2+7=9] => [1, 1, 2, 3, 5, 6, 9 5: [1, 1, 2, 3, 5, 1+6=7, 1+9=10] => [1, 1, 2, 3, 5, 7, 10] 6: [1, 1, 2, 3, 5, 7, 10+1=11] => [1, 1, 2, 3, 5, 7, 11]
大きさ n + 1 の配列を用意します。配列の添字が n を表していて、p(n, 1) から順番に値を求めていきます。p(n, 1) の値は 1 ですから、配列の要素は 1 に初期化します。次に、p(n, 2) の値を求めます。定義により p(n, 2) = p(n - 2, 2) + p(n, 1) なので、2 番目以降の要素に n - 2 番目の要素を加算すれば求めることができます。あとは、k の値をひとつずつ増やして同様の計算を行えば p(n, n) の値を求めることができます。
プログラムは次のようになります。
リスト : 分割数 (動的計画法)
#define N 512
// long long では 405 まで
long long partition_number1(int n)
{
long long a[N];
for (int i = 0; i <= n; i++)
a[i] = 1;
for (int k = 2; k <= n; k++) {
for (int m = k; m <= n; m++) {
a[m] += a[m - k];
}
}
return a[n];
}
説明をそのままプログラムしただけなので、とくに難しいところはないと思います。
リスト : 整数の分割
#define M 128
int buffer[M];
void print_part_int(int n)
{
for (int i = 0; i < n; i++)
printf("%d ", buffer[i]);
printf("\n");
}
void part_int(int n, int k, int x)
{
if (n == 0)
print_part_int(x);
else if (n == 1) {
buffer[x] = 1;
print_part_int(x + 1);
} else if (k == 1) {
for (int i = 0; i < n; i++) buffer[x + i] = 1;
print_part_int(x + n);
} else {
if (n - k >= 0) {
buffer[x] = k;
part_int(n - k, k, x + 1);
}
part_int(n, k - 1, x);
}
}
void partition_of_int(int n)
{
part_int(n, n, 0);
}
基本的な考え方は partition_number と同じです。関数 part_int は選んだ数値を外部変数 buffer に格納していくだけです。n が 0 の場合は print_part_int で表示します。n が 1 の場合は buffer に 1 を追加してから表示します。k が 1 の場合は buffer に 1 を n 個追加してから表示します。
それ以外の場合、n - k が 0 以上であれば、k を選んで buffer に追加して、part_int を再帰呼び出しします。それから、k を -1 して part_int を再帰呼び出しします。
リスト : 整数の分割と分割数 (yacp47.c)
#include <stdio.h>
long long part_num(int n, int k)
{
if (n < 0 || k < 1)
return 0;
else if (n <= 1 || k == 1)
return 1;
else
return part_num(n - k, k) + part_num(n, k - 1);
}
long long partition_number(int n)
{
return part_num(n, n);
}
#define N 512
// long long では 405 まで
long long partition_number1(int n)
{
long long a[N];
for (int i = 0; i <= n; i++)
a[i] = 1;
for (int k = 2; k <= n; k++) {
for (int m = k; m <= n; m++) {
a[m] += a[m - k];
}
}
return a[n];
}
#define M 128
int buffer[M];
void print_part_int(int n)
{
for (int i = 0; i < n; i++)
printf("%d ", buffer[i]);
printf("\n");
}
void part_int(int n, int k, int x)
{
if (n == 0)
print_part_int(x);
else if (n == 1) {
buffer[x] = 1;
print_part_int(x + 1);
} else if (k == 1) {
for (int i = 0; i < n; i++) buffer[x + i] = 1;
print_part_int(x + n);
} else {
if (n - k >= 0) {
buffer[x] = k;
part_int(n - k, k, x + 1);
}
part_int(n, k - 1, x);
}
}
void partition_of_int(int n)
{
part_int(n, n, 0);
}
int main(void)
{
for (int i = 50; i <= 400; i += 50) {
printf("%d, %lld\n", i, partition_number1(i));
}
partition_of_int(3);
partition_of_int(4);
partition_of_int(5);
partition_of_int(6);
return 0;
}
$ clang yacp47.c $ ./a.out 50, 204226 100, 190569292 150, 40853235313 200, 3972999029388 250, 230793554364681 300, 9253082936723602 350, 279363328483702152 400, 6727090051741041926 3 2 1 1 1 1 4 3 1 2 2 2 1 1 1 1 1 1 5 4 1 3 2 3 1 1 2 2 1 2 1 1 1 1 1 1 1 1 6 5 1 4 2 4 1 1 3 3 3 2 1 3 1 1 1 2 2 2 2 2 1 1 2 1 1 1 1 1 1 1 1 1 1
ラテン方陣は数独の枠のチェックを外すだけで求めることができます。詳しくは拙作のページ「数独の解法」をお読みください。単純なバックトラックで解くと、実行時間は次のようになります。
表 : 実行結果 (単位 : 秒) N : 個数 : 時間 --+----------+--------- 4 : 4 : 0.000 5 : 56 : 0.000 6 : 9408 : 0.031 7 : 16942080 : 85.194 実行環境 : clang version 14.0.0, Ubunts 22.04 LTS (WSL2, Windows 10), Intel Core i5-6200U 2.30GHz 最適化オプション : -O2
数字をビットで表すと、もう少し速くなるかもしれません。高次の標準形ラテン方陣の総数は、簡単に求めることができない非常にハードな問題だといわれています。興味のある方は挑戦してみてください。
リスト : ラテン方陣
#include <stdio.h>
#include <stdbool.h>
#include <time.h>
#define N 7
int board[N][N];
int count;
// 縦のチェック
bool check_column(int n, int y, int size)
{
for (int i = 0; i < size; i++) {
if (board[i][y] == n) return false;
}
return true;
}
// 横のチェック
bool check_line(int n, int x, int size)
{
for (int i = 0; i < size; i++) {
if (board[x][i] == n) return false;
}
return true;
}
// チェック
bool check(int n, int x, int y, int size)
{
return check_column(n, y, size) && check_line(n, x, size);
}
// 初期化
void init_board(int size)
{
for (int i = 0; i < size; i++) {
board[0][i] = board[i][0] = i + 1;
}
for (int i = 1; i < size; i++) {
for (int j = 1; j < size; j++) {
board[i][j] = 0;
}
}
count = 0;
}
// 盤面の表示
void print_board(int size)
{
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
printf("%d ", board[i][j]);
}
printf("\n");
}
printf("\n");
}
// 深さ優先探索
void solver(int n, int size)
{
if (n == size * size) {
// print_board(size);
count++;
} else {
int x = n / size;
int y = n % size;
if (board[x][y] != 0) {
solver(n + 1, size);
} else {
for (int n = 1; n <= size; n++) {
if (check(n, x, y, size)) {
board[x][y] = n;
solver(n + 1, size);
board[x][y] = 0;
}
}
}
}
}
int main(void)
{
for (int i = 4; i <= N; i++) {
clock_t s = clock();
init_board(i);
solver(0, i);
printf("%d, %d, %.3f\n", i, count, (double)(clock() - s)/CLOCKS_PER_SEC);
}
return 0;
}
解の総数を求める場合、単純な方法では 6 * 6 の数独でも大変です。そこでラテン方陣のような標準形を考えることにします。数独の場合、数字 N と数字 M を交換しても数独の条件を満たすので、数字の配置を下図のように限定することにします。
1 2 3 4 5 6 4 5 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 図 : 数字の配置
一番上の行で数字を交換することで 6! = 720 通り、右上のグループの残り 3 つの数字を交換することで 6 通りの解が生成されます。したがって、上図の解の総数を I とすると、解の総数は I * 720 * 6 になります。
プログラムは拙作のページ「数独の解法」とほとんど同じなので説明は割愛します。詳細はプログラムリスト６をお読みください。
実行結果は次のようになりました。
$ clang -O2 yacp50.c $ ./a.out 6528, 0.006sec
解の総数は 6528 * 720 * 6 = 28200960 になります。
リスト : 数独 (6 * 6 盤) の解の総数 (yacp50.c)
#include <stdio.h>
#include <stdbool.h>
#include <time.h>
#define N 6
// 盤面
int board[N][N] = {
{1, 2, 3, 4, 5, 6},
{4, 5, 6, 0, 0, 0},
{0},
{0},
{0},
{0},
};
// 解の総数
int count;
// 縦
bool check_column(int n, int y)
{
for (int x = 0; x < N; x++) {
if (board[x][y] == n) return false;
}
return true;
}
// 横
bool check_line(int n, int x)
{
for (int y = 0; y < N; y++) {
if (board[x][y] == n) return false;
}
return true;
}
// 枠 (x, y) は左上の位置
bool check_group(int n, int x, int y)
{
int x1 = (x / 2) * 2;
int y1 = (y / 3) * 3;
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 3; j++) {
if (board[x1 + i][y1 + j] == n) return false;
}
}
return true;
}
bool check(int n, int x, int y)
{
return check_column(n, y) && check_line(n, x) && check_group(n, x, y);
}
// 深さ優先探索
void solver(int n)
{
if (n == N * N) {
count++;
} else {
int x = n / N;
int y = n % N;
if (board[x][y] != 0)
solver(n + 1);
else {
for (int i = 1; i <= N; i++) {
if (check(i, x, y)) {
board[x][y] = i;
solver(n + 1);
board[x][y] = 0;
}
}
}
}
}
int main(void)
{
clock_t s = clock();
solver(0);
printf("%d, %.3fsec\n", count, (double)(clock() - s)/CLOCKS_PER_SEC);
return 0;
}