菜单
For two-sided matching: hospital-resident, stable marriage, college admissions. Gale-Shapley algorithm for stable matching with preferences.
用 Codex 或 Claude 帮你安装 复制这段 Prompt，粘贴到 Codex、Claude 或其他助手里，让它检查 Skill 页面并帮你完成安装。
基于 SOC 职业分类
Conducts iterative deep research on any topic using web search, progressive exploration, and structured synthesis. Use when asked for comprehensive research, deep investigation, thorough analysis, or multi-source exploration of any topic. Triggers: research, investigate, deep dive, comprehensive analysis, explore thoroughly, find everything about.
For cross-cutting concerns: add behavior without modifying functions, caching, timing, logging, validation wrappers.
For performance work: measure before changing, profile to find bottlenecks, compare before and after.
For symbolic computation: ASTs, mathematical expressions, code that manipulates code structure, expression transformations.
For ordered processing: A* search, Dijkstra, event simulation, task scheduling. Efficient min/max extraction with heap-based queue.
For dynamic programming: overlapping subproblems, recursive solutions with repeated computations, memoization to avoid redundant work.
| name | match-stable-pairs |
| description | For two-sided matching: hospital-resident, stable marriage, college admissions. Gale-Shapley algorithm for stable matching with preferences. |
Gale-Shapley Algorithm: Proposers propose in preference order; acceptors tentatively accept best offer so far.
def stable_matching(proposer_prefs, acceptor_prefs):
"""Find stable matching using Gale-Shapley algorithm.
Returns dict mapping proposers to matched acceptors.
Proposer-optimal: proposers get best partner possible.
"""
n = len(proposer_prefs)
# Track state
unmatched = set(range(n)) # Unmatched proposers
matched = {} # acceptor -> proposer
proposals = [list(prefs) for prefs in proposer_prefs] # Remaining preferences
while unmatched:
proposer = unmatched.pop()
if not proposals[proposer]:
continue # Proposer exhausted all options
acceptor = proposals[proposer].pop(0) # Best remaining choice
if acceptor not in matched:
# Acceptor is free, tentatively accept
matched[acceptor] = proposer
elif acceptor_prefs[acceptor].index(proposer) < \
acceptor_prefs[acceptor].index(matched[acceptor]):
# Acceptor prefers new proposer
unmatched.add(matched[acceptor]) # Old match becomes unmatched
matched[acceptor] = proposer
else:
# Acceptor rejects, proposer tries again
unmatched.add(proposer)
return {p: a for a, p in matched.items()}
def stable_matching(P, A):
"""Stable matching with preference arrays.
P[i][j] = proposer i's preference for acceptor j (lower = better)
A[i][j] = acceptor i's preference for proposer j (lower = better)
"""
n = len(P)
ids = range(n)
unmatched = set(ids)
matched = {} # acceptor -> proposer
# Pre-sort: for each proposer, list acceptors by preference
proposals = [sorted(ids, key=lambda a: P[p][a]) for p in ids]
while unmatched:
p = unmatched.pop()
a = proposals[p].pop() # Best remaining acceptor
if a not in matched:
matched[a] = p
elif A[a][p] < A[a][matched[a]]: # a prefers p to current
unmatched.add(matched[a])
matched[a] = p
else:
unmatched.add(p) # Rejected, try again
return {(p, a) for a, p in matched.items()}