0
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.