1
$\begingroup$

I have group of people. Each person can be described by few characteristics:

age, occupation, city, favorite_color

I would like to generate 60 random people and combine them into pairs. With a constrain that no person in a pair can share any characteristic, for example I can't have two people in a pair whose favorite_color is green.

I was thinking about using Backtracking algorithm to solve it.

What other algorithms I could use to solve this particular problem? I would like to research and implement some.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Use an algorithm to find a perfect matching in a graph. Build a graph where each vertex represents a person, and draw an edge between each two people who don't share any characteristic, then look for a perfect matching. If none exists, you can throw away that data and generate a new random sample, and repeat until you find a valid solution.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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