---
title: "algorithm-stable-marriage — Mova code model"
description: "Mova code model of algorithms/src/stable_marriage/mod.rs: components with their labels, obernants and the model text."
url: "https://groupants.elamur.ai/free/en/mova/algorithms/src/stable_marriage/mod.rs.groupant/"
---
Elamur: [Mova](https://md.mova.elamur.ai/free/en/) · [Dictionary](https://md.dictionary.elamur.ai/free/en/) · [Research](https://md.research.elamur.ai/free/en/) · **Groupants**

This page as HTML: <https://groupants.elamur.ai/free/en/mova/algorithms/src/stable_marriage/mod.rs.groupant/>

# algorithm-stable-marriage

The groupant beside algorithms/src/stable_marriage/mod.rs in the Mova repository: what the code computes, what it never does, how to go back from its outputs, its invariants, cost and checks.

## Facts

- **kind:** groupant
- **status:** partial descriptive instance
- **source:** [`algorithms/src/stable_marriage/mod.rs`](https://github.com/ElamurAI/mova-free/blob/main/algorithms/src/stable_marriage/mod.rs)
- **source SHA-256:** `245bad78eb11d5b0…`
- **repository folder:** [`algorithms/src/stable_marriage/mod.rs.groupant`](https://github.com/ElamurAI/mova-free/tree/main/algorithms/src/stable_marriage/mod.rs.groupant)
- **repository commit:** `855da7bd4a7b`

> **Implementation material.** A Mova code model describes this code at one source revision: partial models, finite checks and their stated scope. It is not a reviewed general exposition, and its labels are shown as written, never raised.

## Components

| component | label | where |
|---|---|---|
| **approximant** | partial | [approximant](#approximant) |
| **ast** | partial | `syntax.json` |
| **descriptant** | present | [descriptant](#descriptant) |
| **invariant** | partial | [invariant](#invariant) |
| **tests** | executed bounded checks | [tests](#tests) |

## Obernants

The typed relations around the forward model: the behaviour complement (what the code never does), the reverse reconstruction (every input compatible with an output) and specialised views.

| id | type | label | where |
|---|---|---|---|
| `behavior-complement` | behavior_complement | partial source derived model | [behavior-complement](#behavior-complement) |
| `reverse-reconstruction` | reverse_reconstruction | partial source derived model | [reverse-reconstruction](#reverse-reconstruction) |
| `proposal-budget` | monotone_progress | partial source derived model | [proposal-budget](#proposal-budget) |
| `optimality-fiber` | stable_lattice_extreme | partial source derived model | [optimality-fiber](#optimality-fiber) |
| `validation-partition` | first_failure_partition | partial source derived model | [validation-partition](#validation-partition) |

## Model text


### descriptant

#### Description and epoch memory

Two equal-sized populations with complete strict n-entry permutation rows; total 2*n*n entries at most 2000000. Empty populations allowed.

2026-10-30 initial epoch: chose existing matching plus explicit alternating closure for cover, and FIFO deferred acceptance plus inverse receiver ranks for marriage. Prospective cost: Validation, rank construction and at most n squared proposals cost O(n squared); ranks use O(n squared) auxiliary storage and queues/mates O(n). Budget arithmetic is checked before allocation; allocation failure is untyped. No approximation surrogate is useful for the exact witness contract.

Independent finite oracles inspect both primal/dual cover cardinalities and every stable permutation at small sizes. Original source and fixtures; citation describes the classical method. Models and partial syntax do not prove semantics; macros remain opaque and semantic AST is absent.

### approximant

#### Forward and cost

Validate equal sizes, checked quadratic budget, then proposer and receiver rows. Build receiver inverse ranks. FIFO free proposers propose to the next untried receiver; a receiver retains its best proposal so far and requeues the rejected proposer. Return receiver index per proposer when the queue empties.

Validation, rank construction and at most n squared proposals cost O(n squared); ranks use O(n squared) auxiliary storage and queues/mates O(n). Budget arithmetic is checked before allocation; allocation failure is untyped.

Attribution: D. Gale and L. S. Shapley, College Admissions and the Stability of Marriage, American Mathematical Monthly 69(1) (1962), 9–15. Implementation and fixtures are original. No optimization or speedup is claimed.

### invariant

#### Invariants

Each receiver holds at most one proposer; each held proposer is absent from the free queue. A proposer never repeats a proposal. Receiver held ranks strictly improve on replacement. Completeness prevents preference exhaustion by a free proposer. Final mates form a permutation without blocking pairs and are proposer-optimal among stable permutations.

Test enumeration uses independent subset/assignment predicates rather than repeating production traversal. Bounds do not prove unbounded behavior.

### catalog

## Typed models

Source snapshot: `245bad78eb11d5b0f2f865a72a2ccf0541a146269c3531e42fb6d355fe55e26e`. Domain: Two equal-sized populations with complete strict n-entry permutation rows; total 2*n*n entries at most 2000000. Empty populations allowed.

Each relation is source-derived, exact as a specification; finite executable evidence is partial. Assumes deterministic std-only execution with successful allocation. No executable inverse solver or approximation error cap is claimed.

### behavior-complement

Universe: two preference matrices crossed with candidate receiver vectors and errors. Absent successful behaviors include a non-permutation, a blocking pair (p,r) where both prefer each other to assigned mates, or a stable permutation giving a proposer a worse partner than another stable permutation. Invalid row lengths/permutations cannot succeed. Unequal sizes beat the budget error, which beats malformed rows; within each row, length beats duplicate/out-of-range entry. The finite exhaustive oracle supports these exact source-derived constraints without a general Rust proof.

### reverse-reconstruction

For an observed permutation m, retain every pair of complete preference matrices for which m is stable and proposer-optimal: for each stable alternative s and proposer p, rank_p(m[p]) <= rank_p(s[p]). This finite relational characterization is ambiguous: with two proposers each ranking a distinct receiver first, either strict ordering in each receiver row still yields m. Observing a matching loses unproposed suffixes and proposal/rejection history. Error preimages comprise all profiles sharing the first failed validation predicate and observed indices.

### proposal-budget

The sum of next-proposal cursors increases exactly once per loop and is bounded by n squared. Receiver ranks only improve; a rejected proposer can never obtain that receiver in a proposer-optimal stable solution. Complete strict preferences are required.

### optimality-fiber

Fix preferences and enumerate all n! assignments; discard blocking assignments. For each proposer, the returned partner has minimum ordinal rank among the remaining assignments. Tests enumerate every profile up to n=3; this is finite evidence only.

### validation-partition

Equal size is inspected before checked total entries, then proposer rows before receiver rows. Row length is inspected before entry validity, duplicates share the invalid-preference variant. Later malformed rows remain unconstrained in an early-error preimage.

### tests

#### Bounded checks

All 46674 strict preference profiles for n=0 through 3: every assignment checked for blocking pairs and every stable alternative compared proposer by proposer. Replacement witness; row/duplicate/range/error precedence; n=1000 boundary and n=1001 rejection. Three named tests.

Debug and release run twice with normalized named outcomes. Compiled production mutants flip the cover left complement and receiver replacement comparison respectively; named oracle assertions reject them. Restored positives and strict algorithms clippy are required. External receipts bind final source/evidence hashes. No timing or full-system claim.

See [executed receipts](https://md.groupants.elamur.ai/free/en/mova/algorithms/src/stable_marriage/mod.rs.groupant/#evidence) for final source hashes, named control failures and repeated test log hashes. All checks stated above completed.

### evidence

#### Executed evidence, 2026-10-30

Source SHA-256: `245bad78eb11d5b0f2f865a72a2ccf0541a146269c3531e42fb6d355fe55e26e`. Three tests passed twice in debug and twice in release with identical normalized named results across all four runs. Both restored debug suites passed. Strict algorithms all-targets Clippy and narrow rustfmt checks passed. Four syntax projections repeated byte-identically; structural scaffold passed twice with identical reports (one intentionally missing external scaffold sidecar).

- `stable_marriage-debug-1.log`: `1cc0bb3ad3f61e469e7d0cad8e599f68e00fa38e58b23443bcbc968bb74000f2`
- `stable_marriage-debug-2.log`: `c58528570e494e55479656404370958481b56ad9a169f8b0c3bbc1d024e635d8`
- `stable_marriage-release-1.log`: `f21c6a741c558489f5f82244bb5aa1175e88a2e4215a0475b83f29d7ef8e58ee`
- `stable_marriage-release-2.log`: `e276961b9bcd1acba127bf4fd564a3eab98d805207f4cb1a79f4c03f11d8d13b`
- `stable_marriage-restored.log`: `35e1ef64eae39d69d913ad0b46522792295273bdd0abd535163d8cd62a88a477`
- `marriage-mutant.log`: `c2d96973907a7c62f74fd385378c46db21fc0df733de17cfcc5cf38885aa6ee6`

Compiled receiver rank comparison reversal was rejected by `receiver_replacement_witness`: [0,1] instead of [1,0].

Raw logs remain in the external wave14 graphs run bundle. Earlier tooling attempts exposed two Clippy style findings, absent rg, and stale syntax outputs; final receipts above bind corrected sources and successful checks. No source correctness repair was required by positive oracle findings. No general proof, speedup, full-system or allocation-failure claim.