Algorithm for assigning people to groups

Question

Given a list $L = [1, 2, .., n]$ and a list $C = [(L_i, L_j), ....]$ form a group of pairs $G = g_1, ..., g_{n/2}$ such that:

1. every element of $L$ is assigned to exactly one group
2. $g_k = (L_i, L_j) \Rightarrow (L_i, L_j) \notin C $ (constraint)

I get that there are (potentially) many solutions to this problem. How can one construct a recursive algorithm $group(L, C)$ to that returns a possible grouping?

I get that you can: 1) Create all pairs from $L$ and 2) Create all possible groups of size $n/2$ from the pairs and select one group that is legal.

I see that there are $N_P = {N\choose 2} = \frac{n!}{2!(n-2)!}$ potential pairs in $L$. The number of groups is then ${N_P\choose N/2} = \frac{N_P}{(N/2)!(N_P-N/2)!}$

Then one has to go through all these groups and check if it is legal and return it if so.

Any other solutions?

Answer 1

This problem is equivalent to Perfect Matching

We can view the input as an almost-complete graph, with L as its vertices and every two vertices connected by an edge except for those in C. We then want to find a set of edges that uses every vertex exactly once. This is the perfect matching problem.

To solve this problem, you can use any algorithm for finding a maximal matching, and check if the maximal matching has $n/2$ matches.