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

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