置換群と状態空間探索：Push_swap操作の数学的基盤
置換群論の歴史
Évariste Galoisと群論の誕生
1830年、20歳のフランスの数学者Évariste Galois（1811-1832）は、5次以上の代数方程式には一般的な解の公式が存在しないことを証明した。この証明の過程で、彼は群論（Group Theory）という全く新しい数学的構造を発見した。
Galoisの人生は悲劇的に短かったが（決闘で21歳で死亡）、彼の遺した理論は現代数学の基盤となった。群論は、対称性を研究する数学であり、置換（要素の並べ替え）は群の最も基本的な例である。
Galoisの置換群 (Symmetric Group):
S_n: n個の要素の全ての置換の集合
例: S_3 = 3個の要素の全置換群
要素数: 3! = 6個の置換
e = (1 2 3) → (1 2 3) 恒等置換
σ₁ = (1 2 3) → (1 3 2) 2と3を交換
σ₂ = (1 2 3) → (3 2 1) 1と3を交換
σ₃ = (1 2 3) → (2 1 3) 1と2を交換
σ₄ = (1 2 3) → (2 3 1) 巡回置換
σ₅ = (1 2 3) → (3 1 2) 巡回置換
群の公理:
1. 閉包性: ∀ a,b ∈ G, a∘b ∈ G
2. 結合律: (a∘b)∘c = a∘(b∘c)
3. 単位元: ∃ e, a∘e = e∘a = a
4. 逆元: ∀ a, ∃ a⁻¹, a∘a⁻¹ = e
Arthur Cayleyとケーリーグラフ
1878年、イギリスの数学者Arthur Cayley（1821-1895）は、群を視覚化する方法としてケーリーグラフ（Cayley Graph）を導入した。これは、群の各要素を頂点とし、生成元による操作を辺として表現するグラフである。
Push_swapプロジェクトは、まさにこのケーリーグラフの探索問題として捉えることができる。各スタックの状態が頂点であり、許可された11の操作が辺である。
Push_swapの状態空間グラフ:
頂点 (V): 全ての可能なスタック状態
|V| = (n+m)! / m! × C(n+m, m)
where n = |A|, m = |B|
辺 (E): 許可された操作による遷移
各頂点から最大11本の辺
実際の辺数は状態による
問題: 初期頂点から目標頂点への最短経路を見つける
---
Push_swap操作の群論的分析
操作の代数的構造
Push_swapの11操作は、厳密には群を構成しない（一部の操作は逆元を持たない状況がある）。しかし、部分的な群構造を分析することで、操作の性質を理解できる。
操作の代数的分類:
1. 対合（Involution）: 2回適用で恒等になる操作
sa ∘ sa = e (スワップの自己逆元性)
sb ∘ sb = e
ss ∘ ss = e
2. 巡回置換（Cyclic Permutation）:
ra^n = e (n回のローテーションで元に戻る、n = スタックサイズ)
rra^n = e
3. 逆操作ペア:
ra ∘ rra = e (ローテーションとその逆)
rb ∘ rrb = e
但し: pa ∘ pb ≠ e (一般に、スタック間移動は逆にならない)
4. 可換性の分析:
sa ∘ sb = sb ∘ sa (異なるスタックへの操作は可換)
ra ∘ rb = rb ∘ ra
sa ∘ ra ≠ ra ∘ sa (同じスタックへの異なる操作は非可換)
状態空間の構造
n個の要素を持つPush_swapの状態空間を分析する：
状態空間の数学的定義:
状態 S = (A, B)
A = スタックAの要素列
B = スタックBの要素列
|A| + |B| = n (要素総数は不変)
状態数の計算:
スタックAにk個、スタックBにn-k個ある場合の状態数:
k! × (n-k)! × C(n, k)
全状態数:
Σ(k=0 to n) C(n,k) × k! × (n-k)! = n! × 2^n
n=5の場合:
5! × 2^5 = 120 × 32 = 3840 状態
---
状態空間探索の理論
幅優先探索と最短経路
最適なPush_swap解（最少操作数）を見つけることは、幅優先探索（BFS）の問題として定式化できる。これは1959年のE.F. Mooreによるアルゴリズムである。
BFSによる最適解探索（理論的アプローチ）:
Algorithm BFS-PushSwap:
Input: 初期状態 S₀, 目標状態 S*
Output: 最短操作列
queue ← {S₀}
visited[S₀] ← (null, null) // (親状態, 適用操作)
while queue not empty:
S ← queue.dequeue()
if S = S* then return reconstruct_path(S)
for each operation op in {sa, sb, ss, pa, pb, ra, rb, rr, rra, rrb, rrr}:
S' ← apply(S, op)
if S' not in visited:
visited[S'] ← (S, op)
queue.enqueue(S')
return "No solution"
計算量:
時間: O(|V| + |E|) = O(n! × 2^n × 11)
空間: O(n! × 2^n)
制約:
n=10: 約4×10^10 状態 → 実用的に不可能
n=5: 約4000 状態 → 理論的に可能
Aアルゴリズムとヒューリスティック
1968年、Peter Hart、Nils Nilsson、Bertram RaphaelはAアルゴリズムを発表した。これは、ヒューリスティック関数を用いて探索を効率化する最適性保証付きアルゴリズムである。
A*によるPush_swap探索:
f(S) = g(S) + h(S)
g(S): 初期状態から状態Sまでの実際のコスト（操作数）
h(S): 状態Sから目標までの推定コスト（ヒューリスティック）
許容可能なヒューリスティック（admissible heuristic）:
h(S) ≤ h*(S) for all S
where h*(S) = 実際の最短距離
Push_swapのヒューリスティック候補:
1. h₁(S) = |B|
(スタックBの全要素を戻す必要がある)
2. h₂(S) = inversions(A) / 2
(転倒数の半分：saで最大1転倒を解消)
3. h₃(S) = Σ displacement(i) / n
(各要素の目標位置からの変位)
---
C言語による操作の完全実装
スタック構造の拡張
最適化のために、末尾ポインタと双方向リストを使用する：
/*
** 拡張スタックノード：双方向リスト
** 末尾アクセスO(1)を実現
*/
typedef struct s_node
{
int value; /* 元の値 */
int index; /* 正規化インデックス [0, n-1] */
struct s_node *next; /* 次のノード */
struct s_node *prev; /* 前のノード */
} t_node;
/*
** スタックメタデータ
** サイズと末尾ポインタを保持
*/
typedef struct s_stack
{
t_node *top; /* スタックの先頭 */
t_node *bottom; /* スタックの末尾（O(1)アクセス用）*/
int size; /* 現在の要素数 */
} t_stack;
/*
** ゲーム状態全体
*/
typedef struct s_state
{
t_stack a; /* スタックA */
t_stack b; /* スタックB */
int total; /* 要素総数（不変）*/
} t_state;
スワップ操作：対合の実装
/*
** swap: 最上部2要素の交換
** 群論: 対合（sa ∘ sa = e）
** 時間計算量: O(1)
*/
static void swap_top(t_stack *stack)
{
t_node *first;
t_node *second;
if (!stack->top || !stack->top->next)
return ;
first = stack->top;
second = first->next;
/* ポインタの再接続 */
first->next = second->next;
if (second->next)
second->next->prev = first;
else
stack->bottom = first; /* secondが末尾だった場合 */
second->next = first;
second->prev = NULL;
first->prev = second;
stack->top = second;
}
void sa(t_state *state, int print)
{
swap_top(&state->a);
if (print)
write(1, "sa\n", 3);
}
void sb(t_state *state, int print)
{
swap_top(&state->b);
if (print)
write(1, "sb\n", 3);
}
/*
** ss: 同時スワップ
** 操作回数最適化: sa + sb を1操作に統合
*/
void ss(t_state *state, int print)
{
swap_top(&state->a);
swap_top(&state->b);
if (print)
write(1, "ss\n", 3);
}
プッシュ操作：スタック間移動
/*
** push: 一方のスタックから他方へ要素を移動
** 時間計算量: O(1)
*/
static void push_element(t_stack *from, t_stack *to)
{
t_node *moved;
if (!from->top)
return ;
/* fromから取り出し */
moved = from->top;
from->top = moved->next;
if (from->top)
from->top->prev = NULL;
else
from->bottom = NULL; /* fromが空になった */
from->size--;
/* toに挿入 */
moved->next = to->top;
moved->prev = NULL;
if (to->top)
to->top->prev = moved;
else
to->bottom = moved; /* toが空だった */
to->top = moved;
to->size++;
}
void pa(t_state *state, int print)
{
push_element(&state->b, &state->a);
if (print)
write(1, "pa\n", 3);
}
void pb(t_state *state, int print)
{
push_element(&state->a, &state->b);
if (print)
write(1, "pb\n", 3);
}
ローテーション操作：巡回置換
/*
** rotate: 先頭を末尾に移動
** 群論: n回適用で単位元（ra^n = e）
** 時間計算量: O(1)（末尾ポインタ使用）
*/
static void rotate_stack(t_stack *stack)
{
t_node *first;
if (!stack->top || !stack->top->next)
return ;
first = stack->top;
/* firstを切り離し */
stack->top = first->next;
stack->top->prev = NULL;
/* firstを末尾に接続 */
first->next = NULL;
first->prev = stack->bottom;
stack->bottom->next = first;
stack->bottom = first;
}
void ra(t_state *state, int print)
{
rotate_stack(&state->a);
if (print)
write(1, "ra\n", 3);
}
void rb(t_state *state, int print)
{
rotate_stack(&state->b);
if (print)
write(1, "rb\n", 3);
}
void rr(t_state *state, int print)
{
rotate_stack(&state->a);
rotate_stack(&state->b);
if (print)
write(1, "rr\n", 3);
}
逆ローテーション操作
/*
** reverse_rotate: 末尾を先頭に移動
** 群論: raの逆元（ra ∘ rra = e）
** 時間計算量: O(1)（双方向リスト使用）
*/
static void reverse_rotate_stack(t_stack *stack)
{
t_node *last;
if (!stack->top || !stack->top->next)
return ;
last = stack->bottom;
/* lastを切り離し */
stack->bottom = last->prev;
stack->bottom->next = NULL;
/* lastを先頭に接続 */
last->prev = NULL;
last->next = stack->top;
stack->top->prev = last;
stack->top = last;
}
void rra(t_state *state, int print)
{
reverse_rotate_stack(&state->a);
if (print)
write(1, "rra\n", 4);
}
void rrb(t_state *state, int print)
{
reverse_rotate_stack(&state->b);
if (print)
write(1, "rrb\n", 4);
}
void rrr(t_state *state, int print)
{
reverse_rotate_stack(&state->a);
reverse_rotate_stack(&state->b);
if (print)
write(1, "rrr\n", 4);
}
---
コスト関数と最適化理論
操作コストの形式的定義
1958年、Richard Bellmanは動的計画法の原理を確立した。Push_swapの最適化は、この原理の応用である。
コスト関数の定義:
単一要素の移動コスト:
cost(position, size) = min(position, size - position)
例: size=10, position=3
forward: 3回 ra
backward: 7回 rra
→ cost = min(3, 7) = 3
符号付きコスト（方向情報を含む）:
signed_cost(pos, size) =
pos if pos ≤ size/2 (正: ra方向)
pos - size if pos > size/2 (負: rra方向)
例: size=10, position=8
signed_cost = 8 - 10 = -2 (2回のrra)
2スタック同期コストの計算
/*
** コスト構造体
*/
typedef struct s_cost
{
int cost_a; /* スタックAでの回転コスト（符号付き）*/
int cost_b; /* スタックBでの回転コスト（符号付き）*/
int total; /* 総操作数 */
} t_cost;
/*
** 符号付き回転コストを計算
** 正: ra/rb方向、負: rra/rrb方向
*/
int signed_rotate_cost(int position, int size)
{
if (position <= size / 2)
return (position);
return (position - size);
}
/*
** 2スタック同期時の総コストを計算
** 同方向ならmax、逆方向なら合計
*/
int calculate_total_cost(int cost_a, int cost_b)
{
int abs_a;
int abs_b;
abs_a = (cost_a >= 0) ? cost_a : -cost_a;
abs_b = (cost_b >= 0) ? cost_b : -cost_b;
/* 同符号（同方向回転）: 同期可能 */
if ((cost_a >= 0 && cost_b >= 0) || (cost_a < 0 && cost_b < 0))
return ((abs_a > abs_b) ? abs_a : abs_b);
/* 異符号（逆方向回転）: 個別に実行 */
return (abs_a + abs_b);
}
/*
** スタックBのi番目の要素をスタックAに移動するコストを計算
*/
t_cost compute_move_cost(t_state *state, int b_position)
{
t_cost cost;
int target_a_pos;
t_node *elem;
elem = get_node_at(state->b.top, b_position);
target_a_pos = find_insert_position(&state->a, elem->index);
cost.cost_a = signed_rotate_cost(target_a_pos, state->a.size);
cost.cost_b = signed_rotate_cost(b_position, state->b.size);
cost.total = calculate_total_cost(cost.cost_a, cost.cost_b);
/* + 1 for pa operation */
cost.total++;
return (cost);
}
貪欲法による最適要素選択
/*
** 最小コストの要素を選択（貪欲法）
** Graham (1966) のスケジューリング理論に基づく
*/
int find_cheapest_in_b(t_state *state)
{
int i;
int best_pos;
t_cost best_cost;
t_cost current;
if (state->b.size == 0)
return (-1);
best_pos = 0;
best_cost = compute_move_cost(state, 0);
i = 1;
while (i < state->b.size)
{
current = compute_move_cost(state, i);
if (current.total < best_cost.total)
{
best_cost = current;
best_pos = i;
}
i++;
}
return (best_pos);
}
---
挿入位置の計算
ソート済みスタックへの挿入
/*
** スタックAで要素を挿入すべき位置を見つける
** 二分探索の変形：循環ソート済みリストでの位置
*/
int find_insert_position(t_stack *a, int index)
{
t_node *current;
int pos;
int best_pos;
int best_index;
if (!a->top)
return (0);
/* indexより大きい最小の値を探す */
best_index = INT_MAX;
best_pos = 0;
pos = 0;
current = a->top;
while (current)
{
if (current->index > index && current->index < best_index)
{
best_index = current->index;
best_pos = pos;
}
pos++;
current = current->next;
}
/* 見つからなければ最小値の位置（循環） */
if (best_index == INT_MAX)
best_pos = find_min_index_position(a);
return (best_pos);
}
/*
** 最小インデックスの位置を見つける
*/
int find_min_index_position(t_stack *stack)
{
t_node *current;
int min_pos;
int min_idx;
int pos;
if (!stack->top)
return (0);
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);
}
---
操作の実行と同期
コストに基づく最適な回転実行
/*
** コストに基づいて最適な回転を実行
** 同期可能な場合はrr/rrrを使用
*/
void execute_rotations(t_state *state, t_cost cost)
{
/* 同方向の同期回転 */
while (cost.cost_a > 0 && cost.cost_b > 0)
{
rr(state, 1);
cost.cost_a--;
cost.cost_b--;
}
while (cost.cost_a < 0 && cost.cost_b < 0)
{
rrr(state, 1);
cost.cost_a++;
cost.cost_b++;
}
/* 残りの個別回転 */
while (cost.cost_a > 0)
{
ra(state, 1);
cost.cost_a--;
}
while (cost.cost_a < 0)
{
rra(state, 1);
cost.cost_a++;
}
while (cost.cost_b > 0)
{
rb(state, 1);
cost.cost_b--;
}
while (cost.cost_b < 0)
{
rrb(state, 1);
cost.cost_b++;
}
}
/*
** 最安の要素を移動する完全な操作
*/
void move_cheapest_to_a(t_state *state)
{
int cheapest_pos;
t_cost cost;
cheapest_pos = find_cheapest_in_b(state);
if (cheapest_pos < 0)
return ;
cost = compute_move_cost(state, cheapest_pos);
execute_rotations(state, cost);
pa(state, 1);
}
---
操作の冪等性と逆元
冪等操作と最適化
/*
** 操作の冪等性チェック
** 冪等操作: 複数回適用しても結果が変わらない
** Push_swapでは純粋な冪等操作はないが、
** 循環性を利用した最適化が可能
*/
/*
** n回のraは恒等操作（n = スタックサイズ）
** これを利用して不要な操作を検出
*/
int is_redundant_rotation(int cost, int size)
{
/* コストがサイズの倍数なら無意味 */
return ((cost % size) == 0);
}
/*
** 逆操作ペアの検出と削除
*/
typedef enum e_operation
{
OP_SA, OP_SB, OP_SS,
OP_PA, OP_PB,
OP_RA, OP_RB, OP_RR,
OP_RRA, OP_RRB, OP_RRR
} t_operation;
int are_inverse_operations(t_operation op1, t_operation op2)
{
/* 自己逆元 */
if (op1 == OP_SA && op2 == OP_SA)
return (1);
if (op1 == OP_SB && op2 == OP_SB)
return (1);
/* 逆元ペア */
if ((op1 == OP_RA && op2 == OP_RRA) ||
(op1 == OP_RRA && op2 == OP_RA))
return (1);
if ((op1 == OP_RB && op2 == OP_RRB) ||
(op1 == OP_RRB && op2 == OP_RB))
return (1);
return (0);
}
---
デバッグと可視化
状態空間の可視化
/*
** スタック状態の表示（デバッグ用）
*/
void print_state(t_state *state)
{
t_node *a;
t_node *b;
a = state->a.top;
b = state->b.top;
ft_printf("\n╔═══════════════════════════════╗\n");
ft_printf("║ Stack A │ Stack B ║\n");
ft_printf("╠═══════════════╪═══════════════╣\n");
while (a || b)
{
ft_printf("║");
if (a)
{
ft_printf(" %4d [%2d] ", a->value, a->index);
a = a->next;
}
else
ft_printf(" ");
ft_printf("│");
if (b)
{
ft_printf(" %4d [%2d] ", b->value, b->index);
b = b->next;
}
else
ft_printf(" ");
ft_printf("║\n");
}
ft_printf("╠═══════════════╪═══════════════╣\n");
ft_printf("║ Size: %3d │ Size: %3d ║\n",
state->a.size, state->b.size);
ft_printf("╚═══════════════════════════════╝\n");
}
/*
** コスト行列の表示
*/
void print_cost_matrix(t_state *state)
{
int i;
t_cost cost;
t_node *b;
ft_printf("\nCost Matrix (B → A):\n");
ft_printf("╔══════╦═════════╦═════════╦═══════╗\n");
ft_printf("║ Pos ║ Cost A ║ Cost B ║ Total ║\n");
ft_printf("╠══════╬═════════╬═════════╬═══════╣\n");
i = 0;
b = state->b.top;
while (b)
{
cost = compute_move_cost(state, i);
ft_printf("║ %4d ║ %+6d ║ %+6d ║ %5d ║\n",
i, cost.cost_a, cost.cost_b, cost.total);
i++;
b = b->next;
}
ft_printf("╚══════╩═════════╩═════════╩═══════╝\n");
}
---
まとめ：数学的基盤から実装へ
この章では、Push_swap操作の数学的基盤を学んだ：
群論
- Évariste Galois (1830): 群論の創始、置換群の理論
- Arthur Cayley (1878): ケーリーグラフによる群の可視化
- 操作の代数的性質：対合、巡回置換、逆元
状態空間探索
- E.F. Moore (1959): 幅優先探索アルゴリズム
- Hart, Nilsson, Raphael* (1968): Aアルゴリズム
- 状態空間のサイズ：n! × 2^n
最適化理論
- Richard Bellman (1958): 動的計画法の原理
- コスト関数の設計：符号付きコスト、同期コスト
- 貪欲法による近似解
実装
- 双方向リストによるO(1)操作
- 同期回転（rr/rrr）の活用
- 最適挿入位置の計算
次章では、これらの理論を応用して、小規模データ（3〜5要素）の最適ソートアルゴリズムを設計する。