trjhtr

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

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;