Algorithm to solve constraint satisfaction problems
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.