組合せ論と決定木理論：小規模ソートの最適解
組合せ論の歴史
順列と組合せの数学的起源
順列（Permutation）と組合せ（Combination）の研究は、古代インドとギリシャにまで遡る。紀元前2世紀頃、インドの数学者Pingalaは、韻律学の研究において二項係数に相当する概念を発見した。
17世紀、フランスの数学者Blaise Pascal（1623-1662）は、著作「Traité du triangle arithmétique」(1654)でパスカルの三角形を体系化し、二項係数の計算法を確立した。同時期、Pierre de Fermatとの書簡のやり取りは、確率論の基礎を築いた。
パスカルの三角形と二項係数:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
C(n,k) = n! / (k! × (n-k)!)
順列公式:
P(n) = n!
P(n,k) = n! / (n-k)!
階乗の爆発的成長
n個の異なる要素の順列数はn!（nの階乗）である。この関数は超指数的に成長する：
順列数の成長:
n = 2: 2! = 2
n = 3: 3! = 6
n = 4: 4! = 24
n = 5: 5! = 120
n = 6: 6! = 720
n = 10: 10! = 3,628,800
n = 20: 20! ≈ 2.43 × 10^18
Stirlingの近似 (James Stirling, 1730):
n! ≈ √(2πn) × (n/e)^n
これは、順列の列挙による解法が
小規模でしか実用的でないことを示す
---
決定木理論
決定木とソートの下界
決定木（Decision Tree）は、比較ベースのアルゴリズムを表現する数学的モデルである。1959年、L.R. Ford Jr.とS.M. Johnsonは、論文「A Tournament Problem」で、ソートに必要な最小比較回数を決定木を用いて分析した。
決定木モデル:
- 各内部ノード: 比較操作
- 各葉: 最終的な順列（結果）
- 根から葉への経路: アルゴリズムの実行
n個の要素のソート:
- 葉の数 ≥ n! (全順列)
- 木の高さ h ≥ log₂(n!)
- よって、最悪ケースで ⌈log₂(n!)⌉ 回の比較が必要
例: n = 3
log₂(3!) = log₂(6) ≈ 2.58
→ 最低3回の比較が必要
Push_swapへの決定木適用
Push_swapでは、「比較」だけでなく「操作」がコストとなる。決定木の概念を拡張して分析する：
Push_swap決定木（n=3の場合）:
[a,b,c]
/ \
a<b? a>b?
/ \
[1,2,3] [2,1,3]
[1,3,2] [3,1,2]
[2,3,1] [3,2,1]
↓ ↓
0-2 ops each 1-2 ops each
理論的最小操作数:
- すでにソート: 0
- 隣接スワップ1回: 1
- 最悪ケース: 2
---
2要素ソート：自明な基底ケース
数学的分析
2要素の場合、可能な順列は2つのみ：
2要素の順列空間:
Σ₂ = {[a,b], [b,a]} where a < b
状態1: [a,b] → ソート済み → 0操作
状態2: [b,a] → sa → [a,b] → 1操作
決定木の高さ: 1
最悪ケース: 1操作
平均: 0.5操作
実装
/*
** 2要素ソート: 自明な基底ケース
** 時間計算量: O(1)
** 操作回数: 0または1
*/
void sort_two(t_state *state)
{
if (!state->a.top || !state->a.top->next)
return ;
if (state->a.top->index > state->a.top->next->index)
sa(state, 1);
}
---
3要素ソート：完全列挙による最適解
対称群S₃の構造
3要素の順列群S₃は、6つの要素を持つ最小の非可換群である：
対称群S₃の構造:
元: e, (12), (13), (23), (123), (132)
サイクル表記:
e = () 恒等置換
(12) = σ₁ 1と2を交換
(13) = σ₂ 1と3を交換
(23) = σ₃ 2と3を交換
(123) = τ₁ 巡回置換 1→2→3→1
(132) = τ₂ 巡回置換 1→3→2→1
乗法表:
| e σ₁ σ₂ σ₃ τ₁ τ₂
────┼────────────────────────
e | e σ₁ σ₂ σ₃ τ₁ τ₂
σ₁ | σ₁ e τ₁ τ₂ σ₂ σ₃
σ₂ | σ₂ τ₂ e τ₁ σ₃ σ₁
σ₃ | σ₃ τ₁ τ₂ e σ₁ σ₂
τ₁ | τ₁ σ₃ σ₁ σ₂ τ₂ e
τ₂ | τ₂ σ₂ σ₃ σ₁ e τ₁
全6パターンの最適解
各順列から恒等順列[0,1,2]への最短経路を完全列挙：
3要素の全パターン最適解:
パターン | 順列 | 操作 | 操作数
─────────┼─────────┼───────────┼────────
1 | [0,1,2] | (なし) | 0
2 | [0,2,1] | sa ra | 2
3 | [1,0,2] | sa | 1
4 | [1,2,0] | rra | 1
5 | [2,0,1] | ra | 1
6 | [2,1,0] | sa rra | 2
統計:
- 0操作: 1パターン (16.7%)
- 1操作: 3パターン (50.0%)
- 2操作: 2パターン (33.3%)
- 平均: 1.17操作
- 最大: 2操作
決定木による実装
/*
** 3要素ソート: 完全決定木による最適解
** Ford & Johnson (1959) の理論に基づく
** 時間計算量: O(1)
** 操作回数: 0, 1, または 2
*/
void sort_three(t_state *state)
{
int a;
int b;
int c;
if (state->a.size < 3)
return ;
a = state->a.top->index;
b = state->a.top->next->index;
c = state->a.top->next->next->index;
/* 決定木による分岐 */
if (a < b && b < c)
return ; /* [0,1,2] → ソート済み */
if (a < c && c < b)
{
sa(state, 1); /* [0,2,1] → sa */
ra(state, 1); /* → ra */
}
else if (b < a && a < c)
sa(state, 1); /* [1,0,2] → sa */
else if (c < a && a < b)
rra(state, 1); /* [1,2,0] → rra */
else if (b < c && c < a)
ra(state, 1); /* [2,0,1] → ra */
else
{
sa(state, 1); /* [2,1,0] → sa */
rra(state, 1); /* → rra */
}
}
インデックスベースの簡潔な実装
/*
** 3要素ソート: インデックス位置による判定
** より簡潔な実装
*/
void sort_three_indexed(t_state *state)
{
int max_pos;
if (state->a.size < 3)
return ;
max_pos = find_max_index_position(&state->a);
/* 最大値がトップにある場合 */
if (max_pos == 0)
ra(state, 1);
/* 最大値が2番目にある場合 */
else if (max_pos == 1)
rra(state, 1);
/* 最大値は既に底にある */
/* 残り2要素をソート */
if (state->a.top->index > state->a.top->next->index)
sa(state, 1);
}
---
4要素ソート：分割統治法の適用
問題の分解
4要素のソートは、分割統治法（Divide and Conquer）の考え方を適用できる。1要素を分離し、3要素ソートに帰着させる：
4要素ソートの戦略:
Step 1: 最小要素を特定
Step 2: 最小要素をスタックBに移動
Step 3: 残り3要素をソート（帰納法の仮定）
Step 4: 最小要素をスタックAに戻す
分析:
- Step 2: 0〜3回のローテーション + 1回のpb
- Step 3: 0〜2回の操作
- Step 4: 1回のpa
合計: 2〜7操作
最適経路の計算
/*
** 4要素ソート: 分割統治法
** John von Neumann (1945) の原理に基づく
*/
void sort_four(t_state *state)
{
int min_pos;
if (state->a.size < 4)
return ;
/* 最小要素の位置を特定 */
min_pos = find_min_index_position(&state->a);
/* 最小要素をトップに移動（最短経路） */
rotate_to_top(state, min_pos, state->a.size);
/* 最小要素をスタックBへ */
pb(state, 1);
/* 残り3要素をソート（帰納法の適用） */
sort_three(state);
/* 最小要素を戻す */
pa(state, 1);
}
/*
** 最短経路でトップに移動
** 正: ra方向、負: rra方向
*/
void rotate_to_top(t_state *state, int pos, int size)
{
int forward;
int backward;
forward = pos;
backward = size - pos;
if (forward <= backward)
{
while (pos-- > 0)
ra(state, 1);
}
else
{
while (pos++ < size)
rra(state, 1);
}
}
操作回数の分析
4要素ソートの操作回数分布:
最小位置 | 移動コスト | 3要素ソート | pa | 合計範囲
─────────┼────────────┼─────────────┼────┼──────────
0 | 0 | 0-2 | 1 | 1-3
1 | 1 | 0-2 | 1 | 2-4
2 | 2 | 0-2 | 1 | 3-5
3 | 1 | 0-2 | 1 | 2-4
最悪ケース: 5操作
平均操作数: 約3.5操作
---
5要素ソート：2段階分離戦略
評価基準と目標
42スクールの評価基準では、5要素ソートは最大12操作で完了する必要がある。これは、理論的最適解よりもゆるい制約である。
5要素ソートの理論的分析:
順列数: 5! = 120
理論的下界: ⌈log₂(120)⌉ = 7 (比較回数)
Push_swap操作での推定:
- 2要素をBへ移動: 2-6操作
- 3要素ソート: 0-2操作
- 2要素を戻す: 2操作
合計: 4-10操作
42の基準: ≤12操作 → 十分な余裕あり
戦略：最小2要素を分離
/*
** 5要素ソート: 2段階分離戦略
** 時間計算量: O(1)
** 操作回数: ≤12
*/
void sort_five(t_state *state)
{
if (state->a.size < 5)
return ;
/* 最小要素をBへ */
push_min_to_b(state);
/* 2番目に小さい要素をBへ */
push_min_to_b(state);
/* 残り3要素をソート */
sort_three(state);
/* 順番に戻す（2番目、最小の順） */
pa(state, 1);
pa(state, 1);
}
/*
** 最小要素をスタックBへ移動
*/
void push_min_to_b(t_state *state)
{
int min_pos;
min_pos = find_min_index_position(&state->a);
rotate_to_top(state, min_pos, state->a.size);
pb(state, 1);
}
最適化：同時操作の活用
/*
** 5要素ソート: 最適化版
** 同時操作（rr, rrr, ss）の活用
*/
void sort_five_optimized(t_state *state)
{
int min1_pos;
int min2_pos;
if (state->a.size < 5)
return ;
/* 2つの最小要素の位置を事前計算 */
find_two_min_positions(state, &min1_pos, &min2_pos);
/* 最適な順序で移動 */
if (should_push_min1_first(min1_pos, min2_pos, state->a.size))
{
push_element_at(state, min1_pos);
push_element_at(state, recalculate_pos(min2_pos, min1_pos));
}
else
{
push_element_at(state, min2_pos);
push_element_at(state, recalculate_pos(min1_pos, min2_pos));
}
sort_three(state);
pa(state, 1);
pa(state, 1);
}
/*
** 2つの最小要素の位置を見つける
*/
void find_two_min_positions(t_state *state, int *min1, int *min2)
{
t_node *current;
int pos;
int min1_idx;
int min2_idx;
*min1 = 0;
*min2 = 0;
min1_idx = INT_MAX;
min2_idx = INT_MAX;
pos = 0;
current = state->a.top;
while (current)
{
if (current->index < min1_idx)
{
min2_idx = min1_idx;
*min2 = *min1;
min1_idx = current->index;
*min1 = pos;
}
else if (current->index < min2_idx)
{
min2_idx = current->index;
*min2 = pos;
}
pos++;
current = current->next;
}
}
---
汎用小規模ソートルーチン
ディスパッチャ関数
/*
** 小規模ソートのディスパッチャ
** サイズに応じて最適なアルゴリズムを選択
*/
void sort_small(t_state *state)
{
if (is_sorted(&state->a))
return ;
if (state->a.size <= 1)
return ;
if (state->a.size == 2)
sort_two(state);
else if (state->a.size == 3)
sort_three(state);
else if (state->a.size == 4)
sort_four(state);
else if (state->a.size == 5)
sort_five(state);
}
/*
** ソート済み判定
*/
int is_sorted(t_stack *stack)
{
t_node *current;
if (!stack->top || !stack->top->next)
return (1);
current = stack->top;
while (current->next)
{
if (current->index > current->next->index)
return (0);
current = current->next;
}
return (1);
}
ヘルパー関数群
/*
** 最小インデックスの位置を見つける
** 時間計算量: O(n)
*/
int find_min_index_position(t_stack *stack)
{
t_node *current;
int min_pos;
int min_idx;
int pos;
if (!stack->top)
return (-1);
min_pos = 0;
min_idx = stack->top->index;
pos = 0;
current = stack->top;
while (current)
{
if (current->index < min_idx)
{
min_idx = current->index;
min_pos = pos;
}
pos++;
current = current->next;
}
return (min_pos);
}
/*
** 最大インデックスの位置を見つける
*/
int find_max_index_position(t_stack *stack)
{
t_node *current;
int max_pos;
int max_idx;
int pos;
if (!stack->top)
return (-1);
max_pos = 0;
max_idx = stack->top->index;
pos = 0;
current = stack->top;
while (current)
{
if (current->index > max_idx)
{
max_idx = current->index;
max_pos = pos;
}
pos++;
current = current->next;
}
return (max_pos);
}
---
特殊ケースの最適化
既ソート済み検出
/*
** 既にソート済みの場合、操作不要
*/
int check_and_handle_sorted(t_state *state)
{
if (is_sorted(&state->a))
return (1);
return (0);
}
逆順の最適処理
/*
** 完全逆順の特殊処理
** [n-1, n-2, ..., 1, 0] の形式
*/
int is_reverse_sorted(t_stack *stack)
{
t_node *current;
if (!stack->top || !stack->top->next)
return (1);
current = stack->top;
while (current->next)
{
if (current->index < current->next->index)
return (0);
current = current->next;
}
return (1);
}
/*
** 逆順3要素の最適処理
** [2,1,0] → sa, rra で [0,1,2]
*/
void handle_reverse_three(t_state *state)
{
sa(state, 1);
rra(state, 1);
}
---
テストと検証
全パターン網羅テスト
/*
** 3要素の全6パターンをテスト
*/
void test_all_three_patterns(void)
{
int patterns[6][3] = {
{0, 1, 2}, {0, 2, 1}, {1, 0, 2},
{1, 2, 0}, {2, 0, 1}, {2, 1, 0}
};
int i;
int ops;
int max_ops;
max_ops = 0;
ft_printf("=== 3-Element Sort Test ===\n");
i = 0;
while (i < 6)
{
ops = test_sort_pattern(patterns[i], 3);
ft_printf("[%d,%d,%d]: %d ops\n",
patterns[i][0], patterns[i][1], patterns[i][2], ops);
if (ops > max_ops)
max_ops = ops;
i++;
}
ft_printf("Max operations: %d (should be ≤ 2)\n", max_ops);
ft_printf("Status: %s\n", max_ops <= 2 ? "PASS" : "FAIL");
}
/*
** 5要素の統計テスト
*/
void test_five_statistics(int iterations)
{
int i;
int ops;
int total_ops;
int max_ops;
int over_limit;
total_ops = 0;
max_ops = 0;
over_limit = 0;
ft_printf("=== 5-Element Sort Test (%d iterations) ===\n", iterations);
i = 0;
while (i < iterations)
{
ops = test_random_five();
total_ops += ops;
if (ops > max_ops)
max_ops = ops;
if (ops > 12)
over_limit++;
i++;
}
ft_printf("Average: %.2f ops\n", (float)total_ops / iterations);
ft_printf("Maximum: %d ops\n", max_ops);
ft_printf("Over limit (>12): %d\n", over_limit);
ft_printf("Status: %s\n", over_limit == 0 ? "PASS" : "FAIL");
}
Fisher-Yatesシャッフル
/*
** Fisher-Yates シャッフルアルゴリズム
** Ronald Fisher & Frank Yates (1938)
** 各順列が等確率で出現することを保証
*/
void fisher_yates_shuffle(int *arr, int n)
{
int i;
int j;
int tmp;
i = n - 1;
while (i > 0)
{
j = rand() % (i + 1);
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i--;
}
}
/*
** ランダムな5要素配列を生成してテスト
*/
int test_random_five(void)
{
int arr[5];
int i;
t_state state;
int initial_ops;
int final_ops;
/* 0,1,2,3,4 を生成 */
i = 0;
while (i < 5)
{
arr[i] = i;
i++;
}
fisher_yates_shuffle(arr, 5);
/* スタックを構築 */
init_state_from_array(&state, arr, 5);
/* ソート実行（操作カウント付き） */
initial_ops = get_operation_count();
sort_five(&state);
final_ops = get_operation_count();
/* 検証 */
if (!is_sorted(&state.a))
ft_printf("ERROR: Not sorted!\n");
cleanup_state(&state);
return (final_ops - initial_ops);
}
---
まとめ：組合せ論から実装へ
この章では、小規模ソートの理論的基盤と最適実装を学んだ：
組合せ論
- Blaise Pascal (1654): 二項係数と順列の数え上げ
- James Stirling (1730): 階乗の近似公式
- n要素の順列数はn!で超指数的に成長
決定木理論
- Ford & Johnson (1959): ソートの情報理論的下界
- 比較ベースソートは最低⌈log₂(n!)⌉回の比較が必要
- 決定木の葉はn!個以上必要
小規模ソートの最適解
| 要素数 | 順列数 | 最大操作数 | 平均操作数 | |--------|--------|------------|------------| | 2 | 2 | 1 | 0.5 | | 3 | 6 | 2 | 1.17 | | 4 | 24 | 5 | ~3.5 | | 5 | 120 | ≤12 | ~8 |
アルゴリズム設計原理
- 完全列挙: n=3では全パターンを網羅
- 分割統治: n≥4では問題を分解
- 帰納法: 小さい問題に帰着させる
- 最短経路: ローテーション方向の最適選択
次章では、これらの基礎アルゴリズムを構成要素として、大規模データ（100〜500要素）のソートアルゴリズムを設計する。