Greedy preference-matching algorithm

The problem that this is based on is something like the following:

A matchmaker is working with six clients: John, Joe, Charlie, Jill, Leslie, and Katie. John is compatible with Jill and Leslie, Joe is compatible with Jill. Charlie is compatible with Jill, Leslie, and Katie. How should the matchmaker match them to have the fewest unmatched people?

My idea to solve this was that you should start with the person who has the fewest compatibilities, and match them with the person that they're connected to that has the fewest compatibilities. For example, since Joe is only connected with Jill, you should match them first. Since John is compatible with both Jill and Leslie, he should be matched next. Since Jill is already matched, he must be matched with Leslie. Finally, since Charlie is compatible with the most people, he's matched last.

In this case, of course, it's possible to "match" everyone, but that's not always the case.

My code generates a number of random networks and then tries to compute the maximum number of "matches."

For my testing, I used Excel Solver on the compatibility matrix to see how the Simplex algorithm's output compared with mine. (More details on that testing below, along with an example). In every example I tested, Simplex resulted in a maximum number of "matches" that was identical to mine, although it sometimes resulted in somewhat different matches. (Both answers were correct from what I've seen; these problems may have multiple optimal feasible solutions, there's absolutely no requirement for uniqueness of solutions).

class Program
{
static void Main(string[] args)
{

var random = new Random();

for (int i = 0; i < 10; i++)
{
DoNetwork(random, male, female);
}

Console.WriteLine("Press Enter to exit");
}

private static void DoNetwork(Random random, string[] male, string[] female)
{
// Generate a random array of males
Person[] maleIndividuals = new Person[random.Next(5, 15)];

// Keep track of the names that we've already used so that we don't accidentally give
// two people the same name
HashSet<string> usedNames = new HashSet<string>();

for (int i = 0; i < maleIndividuals.Length; i++)
{
// Select a random male name that we haven't used yet
int randomName = random.Next(0, male.Length);

while (usedNames.Contains(male[randomName]))
{
randomName = random.Next(0, male.Length);
}

// Record the fact that we just used this name

maleIndividuals[i] = new Person
{
Name = male[randomName],
G = Gender.M
};
}

// Do the same thing with females
Person[] femaleIndividuals = new Person[random.Next(5, 15)];

for (int i = 0; i < femaleIndividuals.Length; i++)
{
int randomName = random.Next(0, female.Length);

while (usedNames.Contains(female[randomName]))
{
randomName = random.Next(0, female.Length);
}

femaleIndividuals[i] = new Person
{
Name = female[randomName],
G = Gender.F
};
}

// If the lists are of different lengths, we iterate over the shorter of the two
// By the Pigeonhole Principle, obviously not all of the individuals in the longer list can
// be matched, but we can match all of the individuals in the shorter list
Person[] shorterListOfPersons = maleIndividuals.Length > femaleIndividuals.Length ? maleIndividuals : femaleIndividuals;

foreach (Person p in shorterListOfPersons)
{
// Randomly select how many "matches" this individual will have
int numConnections = shorterListOfPersons == maleIndividuals ? random.Next(1, femaleIndividuals.Length + 1) : random.Next(1, maleIndividuals.Length + 1);

// Keep track of the indices of the individuals we have already connected with

for (int i = 0; i < numConnections; i++)
{
// Add a connection with a random person that we haven't connected with yet
int conn = -1;

do
{
conn = shorterListOfPersons == maleIndividuals ? random.Next(0, femaleIndividuals.Length) : random.Next(0, maleIndividuals.Length);
}

// We must add the connection to both individuals
p.Compatable.Add(shorterListOfPersons == maleIndividuals ? femaleIndividuals[i] : maleIndividuals[i]);

if (shorterListOfPersons == maleIndividuals)
{
}
else
{
}
}
}

Person[] smaller = maleIndividuals.Length > femaleIndividuals.Length ? femaleIndividuals : maleIndividuals;

// Iterate over the individuals in order of least compatabilities to most
Person[] sorted = smaller.OrderBy(p => p.Compatable.Count).ToArray();

foreach (Person p in sorted)
{
// Connect to the person with the fewest compatibilities first
Person leastCompatable = p.Compatable.OrderBy(x => x.Compatable.Count).FirstOrDefault(x => x.Matched == null);

p.Matched = leastCompatable;

// It's perfectly conceivable that someone won't have any matches, so check for null
// to prevent an exception
if (leastCompatable != null)
{
leastCompatable.Matched = p;
}
}

SerializeCompatabilitiesToCSV(maleIndividuals, femaleIndividuals);

SerializeMatchesToCSV(maleIndividuals, femaleIndividuals);

int matched = shorterListOfPersons.Count(p => p.Matched != null);

if (matched < smaller.Length)
{
System.Diagnostics.Debugger.Break();
}

Console.WriteLine($"Matched: {matched} out of a total of {smaller.Length}. There are {maleIndividuals.Length} males and {femaleIndividuals.Length} females."); } private static void SerializeMatchesToCSV(Person[] male, Person[] female) { using (var sw = new StreamWriter("actualNetwork.csv")) { foreach (Person person in male) { sw.Write(","); sw.Write(person.Name); } sw.WriteLine(); foreach (Person person in female) { sw.Write(person.Name); foreach (Person m in male) { sw.Write(","); sw.Write(person.Matched == m ? 1 : 0); } sw.WriteLine(); } } } private static void SerializeCompatabilitiesToCSV(Person[] male, Person[] female) { using (var sw = new StreamWriter("Compatibilities.csv")) { foreach (Person person in male) { sw.Write(","); sw.Write(person.Name); } sw.WriteLine(); foreach (Person person in female) { sw.Write(person.Name); foreach (Person m in male) { sw.Write(","); sw.Write(person.Compatable.Contains(m) ? 1 : 0); } sw.WriteLine(); } } } }  Here's an example of the compatibilities (with 1 indicating "compatible" and 0 indicating "not compatible"): And here's the result of the matching: I used Excel Solver to test what the Simplex method would do with this. It resulted in the following table: As described above, both solutions are feasible and optimal, but they're not identical to each other. Here is the Person class: public class Person { public List<Person> Compatable { get; set; } public string Name { get; set; } public Gender G { get; set; } public Person Matched { get; set; } public Person() { Compatable = new List<Person>(); } }  The male.txt and female.txt are just lists of male and female names (respectively) that I got from some web site. Each line contains a single name. For example, from female.txt: aaren aarika abagael abagail abbe abbey abbi abbie  • The text could just better formatting. Have to derive m/f from the name. An example where greedy failed to find an answer would be nice. Include some of the .txt files. Commented Jun 8, 2018 at 17:43 • Person class is not shown. Commented Jun 8, 2018 at 18:40 • I'm so sorry to interject what could be a stupid question, but any particular reason you're using that algorithm? In economics, these problems are usually solved using a "deferred acceptance" or a "top trading cycles" mechanism, either of which necessarily guarantee the maximum number of "acceptable" (in econ, the term is "stable") matches. Sorry if that was off topic or pointless! Commented Aug 3, 2018 at 2:29 • @AndrewC Not pointless at all. It's actually a fairly new area for me, so any information is helpful. But yes, it is a slightly simpler version of the stable marriage problem. Commented Aug 3, 2018 at 3:21 2 Answers You should separate the initialization of the input from the actual processing. Maybe in two different classes or at least in two or more distinct methods. It is good coding practice and it causes you to focus on each detail isolated. Why are you running the same code 10 times, when you just keep overwrite the same output files? Wouldn't it be more likely to have the compatibility between males and females as part of the input?: John: Jill,Eve,Connie,Kate Jim: Eve,Kate,Carla ...  or else you would probably have some input with the compatibility anyway. This loop can potentially run forever:  while (usedNames.Contains(male[randomName])) { randomName = random.Next(0, male.Length); }  Naming: the list you select here is actually the longest Person[] shorterListOfPersons = maleIndividuals.Length > femaleIndividuals.Length ? maleIndividuals : femaleIndividuals;  You repeat yourself a couple of times:  for (int i = 0; i < maleIndividuals.Length; i++) { // Select a random male name that we haven't used yet int randomName = random.Next(0, male.Length); while (usedNames.Contains(male[randomName])) { randomName = random.Next(0, male.Length); } // Record the fact that we just used this name usedNames.Add(male[randomName]); maleIndividuals[i] = new Person { Name = male[randomName], G = Gender.M }; }  The above code is exactly the same for both males and females. So it would be productive to make a method to handle that: Person[] CreatePersonList(string[] names, Gender gender) { return names.Select(n => new Person { Name = n, G = gender}).ToArray(); }  Why do you have to randomize the initialization of the male/female lists? If you need a randomized output, then you should do the randomization in output selection - not in the input creation. The methods SerializeMatchesToCSV and SerializeCompatabilitiesToCSV are identical except for the output file name, so make one method having the output file name as argument: void SerializeToCSV(string fileName, Peron[] males, Person[] females) { ... }  I don't follow a Lot You fail to provide the definition of person Where you keep selecting random and compare with a HashSet should use a shuffle. Swap the person with the last person or remove the person. Then next time just random range is 1 less. I totally don't follow this int numConnections = shorterListOfPersons == maleIndividuals ? random.Next(1, femaleIndividuals.Length + 1) : random.Next(1, maleIndividuals.Length + 1);  Why would someone have a random number of connection. It seems like intersection would determine the number of connection. I don't get random(5,15) what if there are not 14 people? Your output is only 10 people. Why are you only processing 10 people? It seems like you are mixing the creation of the compatibility with optimizing the matches. That should be separate so you can try new optimization. Check this out. There is no arbitrary 10. It separates the compatibility matrix from the matching. It uses a shuffle to get the random compatible. It is still greedy but it puts you in a spot to work on the algorithm without a lot of other noise. It assign from 1/4 to 3/4 compatible. public static List<PersonMatch> MatchMaker(HashSet<string> males, HashSet<string> females) { List<PersonMatch> personsMatch = new List<PersonMatch>(); if (males.Count == 0) { personsMatch.Add(new PersonMatch("a", gender.m)); personsMatch.Add(new PersonMatch("b", gender.m)); personsMatch.Add(new PersonMatch("c", gender.m)); personsMatch.Add(new PersonMatch("d", gender.m)); personsMatch.Add(new PersonMatch("e", gender.m)); personsMatch.Add(new PersonMatch("f", gender.m)); personsMatch.Add(new PersonMatch("g", gender.m)); personsMatch.Add(new PersonMatch("h", gender.m)); personsMatch.Add(new PersonMatch("i", gender.m)); personsMatch.Add(new PersonMatch("j", gender.m)); personsMatch.Add(new PersonMatch("k", gender.m)); personsMatch.Add(new PersonMatch("l", gender.m)); personsMatch.Add(new PersonMatch("m", gender.m)); } if (females.Count == 0) { personsMatch.Add(new PersonMatch("n", gender.f)); personsMatch.Add(new PersonMatch("o", gender.f)); personsMatch.Add(new PersonMatch("p", gender.f)); personsMatch.Add(new PersonMatch("q", gender.f)); personsMatch.Add(new PersonMatch("r", gender.f)); personsMatch.Add(new PersonMatch("s", gender.f)); personsMatch.Add(new PersonMatch("t", gender.f)); personsMatch.Add(new PersonMatch("u", gender.f)); personsMatch.Add(new PersonMatch("v", gender.f)); personsMatch.Add(new PersonMatch("w", gender.f)); personsMatch.Add(new PersonMatch("x", gender.f)); personsMatch.Add(new PersonMatch("y", gender.f)); personsMatch.Add(new PersonMatch("z", gender.f)); } foreach(PersonMatch m in personsMatch.Where(x => x.Gender == gender.m)) { //Debug.WriteLine(m.Name); foreach(PersonMatch c in GetRandomPersonMatch(personsMatch.Where(x => x.Gender == gender.f).ToList())) { //Debug.WriteLine(c.Name); m.CompatableWith.Add(c); } //Debug.WriteLine(""); } foreach (PersonMatch f in personsMatch.Where(x => x.Gender == gender.f)) { //Debug.WriteLine(f.Name); foreach (PersonMatch c in GetRandomPersonMatch(personsMatch.Where(x => x.Gender == gender.m).ToList())) { //Debug.WriteLine(c.Name); f.CompatableWith.Add(c); } //Debug.WriteLine(""); } foreach (PersonMatch m in personsMatch.Where(x => x.Gender == gender.m)) { foreach (PersonMatch cc in GetPersonCrossCompatable(m, personsMatch.Where(x => x.Gender == gender.f).ToList())) { m.CrossCompatable.Add(cc); } } foreach (PersonMatch m in personsMatch.Where(x => x.Gender == gender.f)) { foreach (PersonMatch cc in GetPersonCrossCompatable(m, personsMatch.Where(x => x.Gender == gender.m).ToList())) { m.CrossCompatable.Add(cc); } } //now get down to business foreach (PersonMatch m in personsMatch.OrderBy(x => x.CrossCompatableCount).Where(x => x.CrossCompatableCount > 0 && !x.Matched)) { if (m.CrossCompatableCount == 1) { m.Match = m.CrossCompatable[0]; m.Match.Match = m; } else { PersonMatch mb = m.CrossCompatable.Where(x => !x.Matched).OrderBy(x => x.CrossCompatableCount).FirstOrDefault(); if (mb != null) { m.Match = mb; m.Match.Match = m; } } //Debug.WriteLine(m.ToString()); } foreach (PersonMatch m in personsMatch.OrderBy(x => x.CrossCompatableCount).ThenBy(x => x.Gender).ThenBy(x => x.Name)) { Debug.WriteLine(m.ToString()); } Debug.WriteLine("Done"); return personsMatch; } public enum gender { m, f }; public class PersonMatch { public string Name { get; } public List<PersonMatch> CompatableWith { get; } = new List<PersonMatch>(); public String CompatableWithString { get { return string.Join(", ", CompatableWith.Select(x => x.Name)); } } public List<PersonMatch> CrossCompatable { get; } = new List<PersonMatch>(); public String CrossCompatableString { get { return string.Join(", ", CrossCompatable.Select(x => x.Name)); } } public int CrossCompatableCount { get { return CrossCompatable.Count(); } } public PersonMatch Match { get; set; } public bool Matched { get { return Match != null; } } public gender Gender { get; } public PersonMatch (string name, gender g) { Name = name; Gender = g; } public override string ToString() { return ($"Name {Name}  Gender {Gender} CrossCompatableCount {CrossCompatableCount}  Match {(Match == null ? "" : Match.Name)}  \n CompatableWith  {CompatableWithString} \n CrossCompatable {CrossCompatableString}");
}
public override int GetHashCode()
{
return (Name + Gender.ToString()).GetHashCode();
}
public override bool Equals(object obj)
{
if(obj== null)
{
return false;
}
PersonMatch other = obj as PersonMatch;
if(other == null)
{
return false;
}
return (Name == other.Name && Gender == other.Gender);
}
}
private static Random rand = new Random();
public static IEnumerable<PersonMatch> GetPersonCrossCompatable(PersonMatch p, List<PersonMatch> pool)
{
//Debug.WriteLine($"GetPersonCrossCompatable {p.Name}"); foreach (PersonMatch cm in pool) { //Debug.WriteLine($"pool {cm.Name}");
if(cm.CompatableWith.Contains(p) && p.CompatableWith.Contains(cm))
{
//Debug.WriteLine(\$"cross match");
yield return cm;
}
}
}
public static IEnumerable<PersonMatch> GetRandomPersonMatch(List<PersonMatch> pool)
{
int wantCount = rand.Next(pool.Count / 4, pool.Count * 3 / 4);
//Debug.WriteLine(wantCount);
for(int i = pool.Count - 1; i > pool.Count - wantCount - 1; i--)
{
int next = rand.Next(i + 1);
yield return pool[next];
if(next != i)
{
PersonMatch temp = pool[i];
pool[i] = pool[next];
pool[next] = temp;
}
}
}

• I agree with much of your remarks. There is a confusing mixing of code that randomly populates people collections versus the key method of performing a compatible Match from an input collection. Commented Jun 8, 2018 at 19:02