# Algorithm for assigning people to groups

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?

# 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.