Speed dating algorithm to select the pair of dates

Lets say there are 10 boys and 10 girls in speed date. 10 boys select 4 girls and rank them. 10 girls select 4 boys and rank them. In the end the winning pairs would be returned.

Finer details such as tie-breakers, rules of input params etc, are well documented. Looking for code review, optimization and best practices.

final class Pair {

private final String male;
private final String female;

public Pair(String male, String female) {
this.male = male;
this.female = female;
}

public String getMale() {
return male;
}

public String getFemale() {
return female;
}

@Override
public String toString() {
return male + "  dates: " + female;
}
}

/**
*
* Provides a thread safe solution Solves the speed date problem.
*
* Example:
* --------
* - Lets say there are 10 boys and 10 girls in speed date
* - 10 boys  select 4 girls and rank them.
* - 10 girls select 4 boys  and rank them.
* - in the end the winning pairs would be returned.
*
* Complexity:
* Time complexity: O(nlogn)
* Space complexity: O(n)
*
*/
public class SpeedDateCompute {

private final Map<String, List<String>> maleChoices;
private final Map<String, List<String>> femaleChoices;

/**
* Does not make a deep copy of maps thus client is not expected to change maleChoice, femaleChoice.
* Expects consistency in males and female maps, else results are unpredictable.
*
* By consistency it means:
* - The number of boys and girls should be the same.
* - Each boy and each girl should make same number of choices
* - Choices should mention "only existing members of opposite sex"
*
*
* @param maleChoices
* @param femaleChoices
*/
public SpeedDateCompute(Map<String, List<String>> maleChoices, Map<String, List<String>> femaleChoices) {
validate(maleChoices, femaleChoices);

this.maleChoices = maleChoices;
this.femaleChoices = femaleChoices;
}

private static class Edge {
String male;
String female;
int malesPreference;  // what does male   ranks this female ?
int femalePreference; // what does female ranks this male ?

Edge (String male, String female, int malesPreference, int femalePreference) {
this.male = male;
this.female = female;
this.malesPreference = malesPreference;
this.femalePreference = femalePreference;
}
}

private static class EdgeComparator implements Comparator<Edge> {
@Override
public int compare(Edge edge1, Edge edge2) {
int val = rank (edge1.femalePreference - 1, edge1.malesPreference - 1)
- rank (edge2.femalePreference - 1, edge2.malesPreference - 1);
return val;
}

/*
* Ranking algorithm.
*
* Let notation (1,2) mean - femalePrerence is 1 and malePreference is 2.
* (1, 1) means both rank each other as their best so this pair triumps over (2, 2)
* but there is a tie between (1, 2) and (2, 1)
* As a tie breaker we give preference to feelings of women
* thus (1,2) > (2, 1)
*
* Thus the rule is expanded to
*
* (1, 1) > (1, 2) > (2, 1) > (2, 2)
*
* This can be thought of as a matrix of the form
* (lil lazy to retype the whole thing, plz check the link)
* http://math.stackexchange.com/questions/720797/whats-the-name-of-this-sort-of-matrix
* http://codereview.stackexchange.com/questions/44939/a-matrix-with-square-diagonals-and-transpose-being-increments-of-other
*
* @param row   the female choice
* @param col   the male choice
* @return
*/
private int rank(int row, int col) {
if (row == col) {
return row * row;
}

int rank = (col) * (col) + 1 + (2 * row) ;

if (row < col) {
return rank;
} else {
return rank + 1;
}
}
}

private void validate (Map<String, List<String>> maleChoices, Map<String, List<String>> femaleChoices) {
if (maleChoices == null || femaleChoices == null) {
if (maleChoices != null) {
throw new NullPointerException("female choice map should not be null");
}
if (femaleChoices != null) {
throw new NullPointerException("male choice map should not be null");
}
throw new NullPointerException("no choice map should be null.");
}

if (maleChoices.size() == 0 || femaleChoices.size() == 0) {
if (maleChoices.size() == 0) {
throw new IllegalArgumentException("male choice map should not be empty.");
}
if (femaleChoices.size() == 0) {
throw new IllegalArgumentException("female choice map should not be empty.");
}
throw new IllegalArgumentException("no choice map should be empty.");
}
}

public List<Pair> getPairs() {
final Collection<Edge> edges = parseChoiceMaps();
final List<Edge> sortedEdges = sort(edges);
return createPairs(sortedEdges);
}

/**
* Given a directed bipartite graph, it converts bipartite graph into
* undirected map.
*
* @param choiceMap the bipartite graph of choices
* @return
*/
private Collection<Edge> parseChoiceMaps() {

final Map<String, Edge> combinedMaleChoice = new HashMap<String, Edge>();

synchronized (maleChoices) {
// parsing male choices.
for (Entry<String, List<String>> maleChoice : maleChoices.entrySet()) {
String maleName = maleChoice.getKey();
List<String> females = maleChoice.getValue();
for (int i = 0; i < females.size(); i++) {
// mark female preference as "size" thus assigning the worst rank as default.
combinedMaleChoice.put(maleName + females.get(i), new Edge(maleName, females.get(i), i + 1,
maleChoices.size()));
}
}
}

synchronized (femaleChoices) {
// parsing female choices
for (Entry<String, List<String>> femaleChoice : femaleChoices.entrySet()) {
List<String> males = femaleChoice.getValue();
for (int i = 0; i < males.size(); i++) {
String name = males.get(i) + femaleChoice.getKey();
// check if any male has chosen this female, else skip.
if (combinedMaleChoice.containsKey(name)) {
combinedMaleChoice.get(males.get(i) + femaleChoice.getKey()).femalePreference = i + 1;
}
}
}
}

return combinedMaleChoice.values();
}

private List<Edge> sort(Collection<Edge> edges) {
final List<Edge> edgeList = new ArrayList<Edge>(edges);
Collections.sort(edgeList, new EdgeComparator());
return edgeList;
}

private List<Pair> createPairs(List<Edge> edges) {
final Set<String> hookedUpMales = new LinkedHashSet<String>();
final Set<String> hookedUpFemales = new LinkedHashSet<String>();

for (Edge edge : edges) {
if (hookedUpMales.contains(edge.male) || hookedUpFemales.contains(edge.female)) {
continue;
}
}

return mapSetsToPairs(hookedUpMales, hookedUpFemales);
}

private List<Pair> mapSetsToPairs(Set<String> hookedUpMales, Set<String> hookedUpFemales) {
Iterator<String> maleItr = hookedUpMales.iterator();
Iterator<String> femaleItr = hookedUpFemales.iterator();

final List<Pair> pairs = new ArrayList<Pair>();

while (maleItr.hasNext() && femaleItr.hasNext()) {
maleItr.remove();   // just to optimize space
femaleItr.remove(); // just to optimize space
}
return pairs;
}

public static void main(String[] args) {
/*
* Test case 1
*/
Map<String, List<String>> maleChoice1 = new HashMap<String, List<String>>();
Map<String, List<String>> femaleChoice1 = new HashMap<String, List<String>>();

maleChoice1.put("male1", Arrays.asList("female1", "female2"));
maleChoice1.put("male2", Arrays.asList("female2", "female1"));
femaleChoice1.put("female1", Arrays.asList("male1", "male2"));
femaleChoice1.put("female2", Arrays.asList("male2", "male1"));
SpeedDateCompute speedDateCompute = new SpeedDateCompute(maleChoice1, femaleChoice1);
List<Pair> actualValues = speedDateCompute.getPairs();
assertEquals("male1", actualValues.get(0).getMale());
assertEquals("female1", actualValues.get(0).getFemale());
assertEquals("male2", actualValues.get(1).getMale());
assertEquals("female2", actualValues.get(1).getFemale());

/*
* Test case 2
*/
Map<String, List<String>> maleChoice2 = new HashMap<String, List<String>>();
Map<String, List<String>> femaleChoice2 = new HashMap<String, List<String>>();
maleChoice2.put("male1", Arrays.asList("female2", "female1"));
maleChoice2.put("male2", Arrays.asList("female1", "female2"));
maleChoice2.put("male3", Arrays.asList("female1", "female2"));
femaleChoice2.put("female1", Arrays.asList("male2", "male1"));
femaleChoice2.put("female2", Arrays.asList("male1", "male2"));
femaleChoice2.put("female3", Arrays.asList("male1", "male2"));
speedDateCompute = new SpeedDateCompute(maleChoice2, femaleChoice2);
actualValues = speedDateCompute.getPairs();

assertEquals("male1", actualValues.get(0).getMale());
assertEquals("female2", actualValues.get(0).getFemale());
assertEquals("male2", actualValues.get(1).getMale());
assertEquals("female1", actualValues.get(1).getFemale());

assertEquals(2, actualValues.size());
}
}

-
Where are 10 boys/girls and where are their 4 choices in your test cases? – abuzittin gillifirca Mar 26 '14 at 8:08

This code is really beautiful and well-documented. There are very few parts which could be criticized:

• Don't use objects where they are not applicable. Your SpeedDateCompute class is essentially only characterized by its getPairs method. We might as well make that static, and invoke it as SpeedDateCompute.getPairs(maleChoices, femaleChoices).

Such single-method classes encpasulating an algorithm should only be instantiable if we need to pass the algorithm around as an object.

• Your validate is a bit too complicated. This refactoring produces almost as good error messages, but is less confusing to read.

private void validate (Map<String, List<String>> maleChoices, Map<String, List<String>> femaleChoices) {
if (femaleChoices == null) {
throw new NullPointerException("female choice map should not be null");
}
if (maleChoices == null) {
throw new NullPointerException("male choice map should not be null");
}

if (maleChoices.size() == 0) {
throw new IllegalArgumentException("male choice map should not be empty.");
}
if (femaleChoices.size() == 0) {
throw new IllegalArgumentException("female choice map should not be empty.");
}
}

• Synchronizing on maleChoices and femaleChoices makes little sense. Your documentation already states that the “client is not expected to change maleChoice, femaleChoice”. I would have left it with that, and hope that any users of this class aren't insane enough to share this data between threads. Synchronizing is a fairly expensive operation, so I would wish to avoid it if unnecessary, and offload the responsibility to the client.

• The keys in combinedMaleChoice are a simple concatentation of the male and female names. While in practice very unlikely, this could lead to clashes (along the lines of "AA" + "B" vs. "A" + "AB"). You could use a Map<String, Map<String, Edge>> instead, or a separator that is guaranteed to not occur in the name: maleName + "\0" + femaleName.

This is part of a larger issue that names are not unique. For real-world code, you need some unique identifier. This is one reason why I would like to encapsulate the involved persons in a class of their own, e.g:

public static abstract class Person<Likes extends Person> {
private final String name;
private final List<Likes> likes = new ArrayList<>();

public Person(String name) {
this.name = name;
}

public String name() {
return this.name;
}

public List<Likes> likes() {
return this.likes;
}

public List<Likes> likes(List<Likes> others) {
return this.likes;
}

@Override
public String toString() {
return this.name();
}

// "equals" defaults to pointer equivalence, which is what we want
}

public static class Male extends Person<Female> {
public Male(String name) {
super(name);
}

@Override
public boolean equals(Object that) {
return that instanceof Male && super.equals(that);
}
}

public static class Female extends Person<Male> {
public Female(String name) {
super(name);
}

@Override
public boolean equals(Object that) {
return that instanceof Female && super.equals(that);
}
}


This also allows us to better leverage the type system than only relying on Strings – the downside is that the client will need more initialization code to prepare the Persons.

• There is no substantial difference between Pair and Edge. I'd combine both into one class.

• You made your code far more complicated than necessary by splitting logic into createPairs and mapSetsToPairs. You create two LinkedHashSets and then iterate over both in parallel. We can do all of that in one loop:

private List<Pair> createPairs(List<Edge> edges) {
final Set<String> hookedUpMales = new HashSet<>();
final Set<String> hookedUpFemales = new HashSet<>();
final List<Pair> hookedUpPairs = new ArrayList<>();

for (Edge edge : edges) {
if (hookedUpMales.contains(edge.male) || hookedUpFemales.contains(edge.female)) {
continue;
}
}

return hookedUpPairs;
}

• If you are targeting Java 7, you don't have to spell out all generics, and can use the diamond operator instead:

// final List<Edge> edgeList = new ArrayList<Edge>(edges);
final List<Edge> edgeList = new ArrayList<>(edges);

• Your tests are buggy. While you guarantee that you return the optimal pairs, you do not guarantee any order when two pairs have the same preferences. Therefore in your first test, actualValues.get(0).getMale() may be male2 rather than male1. Instead:

1. Test that the number of returned pairs is correct
2. Test that the collection of pairs contains an expected pair. This implies that you should override equals and hashCode for the Pair class.
• In parseChoiceMaps, you assign i + 1 as a preference, then decrement that value again when calculating your rank. This index shuffling servers no purpose, and can be removed by using zero-based preferences

I did a bit of refactoring incl. introducing a Person class and unifying Edge and Pair, and the result is in fact quite nice: http://ideone.com/RSTcUu

Further observations:

• Your JavaDoc contains Markdown-like lists. IIRC, you can use a restricted subset of HTML for formatting instead.

• Your ranking algorithm seems terribly flawed. I understand that you need some absolute ordering, but a modified Manhattan Distance or Euclidean Distance would probably do a better job. For example with f = 10, m = 0 (where f is the female preference, m the male preference) we get a rank of 22. Now we might have another edge with f = 0, m = 9. I would expect this second edge to be sorted before the first one. But it has a rank of 101, which is far worse! In other words, the choice of males is weighted more heavily.

A related problem is that you assign a preference for females even when they have shown no interest in that specific male. For example, consider this:

male1 likes female1
male2 likes female2
female1 likes male1
female2 likes male1


The pairing male1 – female1 is expected, as both like each other. However, male2 – female2 is dubious. Due to your implementation, the reverse is not true:

male1 likes female1
male2 likes female1
female1 likes male1
female2 likes male2


will only return the male1 – female1 pairing.

Better rankings that use the female rankings to break ties could be a modified Manhattan Distance:

rank = (m + f) * max + f


or Euclidean Distance:

rank = (int) (Math.sqrt(m*m + f*f) * max + f)


where max is the maximum rating involved in this comparison.

-

Computationally speaking, I don't have anything to add what has already been said. @amon did a really comprehensive review of your code. However, there are some serious sociological and/or ethical flaws in your code. I would say that, genderly speaking, it could be made more generic:

• Sexual orientation: first of all, you are assuming that boys love girls and girls love boys. This is incorrect. You would have to take into account homosexual and bisexual people too. That would mean that your Person instances should also have a variable specifying what is the sexual orientation of the instance. You could use a percentage to roughly represent whether the subjects are more interested in males or in females; that percentage could be taken into account in the rating algorithm.
• Sex: if we only restrict ourselves to biology and biological values, you totally overlook intersexual people. That may be very offensive since many of them have a hard time finding a place in society and try to conform to one gender while there is no "dedicated" gender for intersexual people. That could feel like an insult. Also, some try to assume an intersexual identity instead of trying to conform to "male" and "female".
• Gender: we can safely assume that reducing people to what they have between their legs is a bad idea overall. Therefore, you could consider their gender instead. However, you will have trouble: there are as many genders as we can think of (for example, Facebook recently added 56 gender options instead to complete "male" and "female"). With the current design, your code would become overly complicated if you tried to represent even the most well-known ones.

To conclude, one solution would be to make two lists of Individuals. Not only would it be more respectful towards many many people in the world, but you could also get rid of your Male and Female classes: that would make your code more generic while probably shorter and simpler too. Everywhere you have variable names containing male or female, you can replace them by person1 and person2 or individual1 and individual2. Moreover, that kind of genericity would allow your code to be adapted to more complex problems (for example, a problem of Ménage à trois speed dating).

Never forget that you should treat people as people, and consider how they define themselves before considering how you would like them to be.

-
I considered doing a s/Male/HeterosexualMale/g etc. in my refactoring, and the implementation can be easily adapted to handle arbitrary sexual orientations. There is no need for the input sets to be divided into male/female, except that the preferences of the latter group is used during the sorting to break ties between two pairings. This deal-braking mechanism has to be consistent, which is difficult to realize otherwise (comparing the names is not possible, as there could be ties here as well, and I don't want to untangle those love triangles). – amon Mar 26 '14 at 16:15
@amon Deal-breaking will always be the problem anyway :p – Morwenn Mar 26 '14 at 16:19
So your argument is that the problem itself has to be changed. Why? Are you the one who assigned this task? Maybe the intended audience is exactly how the problem states it. Next time I write a program to sort football fans and you will object that people who hate football and like basketball instead should be also included? Nothing in your answer actually answers the question, you just argue that the question should be changed to look for a solution for a completely different problem. This is codreview, not political sciences. – vsz Mar 26 '14 at 16:56
This algo was supposed to be bipartite graph - i could not think of any example but male/female pair to better convey my ideas. However noted your point and apologies for everyone – JavaDeveloper Mar 26 '14 at 17:09
@vsz My argument was that I was just trying to do something different. For fun actually (those are social sciences by the way, not political sciences). I expected that I would get that kind of answers and was actually waiting for them. That's pretty entertaining :) – Morwenn Mar 27 '14 at 8:25

Looks good, I didn't work through the logic of your algorithms, but generally looked if things could be done more efficiently and nothing grabbed my attention.

The one comment I do have is on your validate() method, it checks for null and empty maps, but I believe you have an additional requirement that they are the same size? If so, this should be part of the validate() method as well.

-