How do you find and list stable roommate matches with SQL or PHP?

Question

Prerequisites

I have two tables. A list of people in one table, and how they prefer each other in a foreign key lookup table. The first table is only the list of people. The other is where they all list a few other people they would prefer to have as a roommate.

Table People:

• List of people with ID, name and surname, etc

Table Choices:

• List of choosers (FK People ID)
• List of chosen ones (FK People ID)

Question

How can I list matches with SQL (or PHP)? That is, where one person is also on the list on the person he wanted to have as a roommate? Basically you have a chooser with a list of chosen ones. How would you check if the chooser is also on the list of one of his or her chosen ones?

Basically I want a report with every stable match, that is where the chooser is also on the list of at least one of his or her chosen ones.

I am guessing a for loop would do the trick, but how would you even put together the first iteration? Much less the rest of the loop?

Answer 1

Join based solution:

SELECT
    r1.name as name1,
    r2.name as name2
FROM
    roommate r1
JOIN
    roommate_pair rp1 ON r1.id = rp1.chooser_id
JOIN
    roommate r2 ON r2.id = rp1.choosen_id
JOIN
    roommate_pair rp2 ON r2.id = rp2.chooser_id
WHERE
    rp2.choosen_id = r1.id
GROUP BY
    CONCAT(GREATEST(r1.id,r2.id),'-',LEAST(r1.id,r2.id))

Last GROUP BY is to remove duplicate matches in swapped columns. Working SQL Fiddle

Answer 2

SELECT a.chooser, a.chosen
FROM roommates a,roommates b
WHERE a.chooser = b.chosen
AND a.chosen = b.chooser;

Using the above query you should get the cross-referenced id's... You do, however, get doubles (both references are returned). See SQL Fiddle. You could do a check on that in your PHP-code.