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)
{
string[] male = File.ReadAllLines("male.txt");
string[] female = File.ReadAllLines("female.txt");
var random = new Random();
for (int i = 0; i < 10; i++)
{
DoNetwork(random, male, female);
}
Console.WriteLine("Press Enter to exit");
Console.ReadLine();
}
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
usedNames.Add(male[randomName]);
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);
}
usedNames.Add(female[randomName]);
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
HashSet<int> alreadyConnected = new HashSet<int>();
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);
}
while (alreadyConnected.Contains(conn));
alreadyConnected.Add(conn);
// We must add the connection to both individuals
p.Compatable.Add(shorterListOfPersons == maleIndividuals ? femaleIndividuals[i] : maleIndividuals[i]);
if (shorterListOfPersons == maleIndividuals)
{
femaleIndividuals[i].Compatable.Add(p);
}
else
{
maleIndividuals[i].Compatable.Add(p);
}
}
}
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
