Question
Given disjoint non-empty groups of node IDs, treat each group as an internally connected component. Generate a random set of additional edges connecting all groups, never joining two nodes from the same group. Sample uniformly over concrete inter-group edge sets whose contracted group graph is a spanning tree. This is not a spanning tree over every individual node: internal component connectivity is assumed, not returned. ```python def connect_groups(groups: list, seed: int = 0) -> list: ... ``` ## Requirements - Return exactly `len(groups) - 1` edges when there is more than one group. - Each edge joins nodes from different groups, and all groups become connected. - Use the supplied seed for reproducibility. - Store each edge with the smaller node ID first and return edges in sorted order. - Duplicate node IDs across groups are invalid. - Node IDs are non-boolean integers and `seed` is a non-boolean integer. Empty input returns `[]`; empty groups, duplicate IDs within or across groups and invalid IDs/seeds raise `ValueError` before sampling. Do not modify groups or global random state. A single valid group returns `[]`. - The supplied version-one `run_case` validates structure, ordering, reproducibility and input/global RNG custody rather than requiring a particular seeded edge list. `_spanning_edges` is optional. Structural fixture success is not proof of a uniform distribution; justify the sampling distribution separately. One valid approach applies Wilson's loop-erased random-walk algorithm at group level, chooses group transitions with weight `|Gi| * |Gj|`, and then samples one endpoint uniformly from each selected group. ## Design discussion (not graded) 1. Explain and justify the uniformity claim. 2. Support weighted node-pair probabilities. 3. Generate a connected graph with a requested number of extra edges. 4. Handle extremely large groups without enumerating all possible edges.