0

I am trying to write an algorithm that will match items based on their properties.

I have a list of courses, each course belongs to one or more categories. A single level must have 1 subject from each category. A subject cannot be used for evidence against more than 1 category in a level.

So, for example:

Course x has categories: Cat 1, Cat 2, Cat 3, Cat 4 and Cat 5.

Subject A - Cat 1, Cat 2
Subject B - Cat 2, Cat 3
Subject C - Cat 4
Subject D - Cat 2, Cat 4
Subject E - Cat 5

In this case I would put 

A Cat 1, 
B Cat 3, 
C Cat 4, 
D Cat 2, 
E Cat 5.

A student may not have completed all categories at the time of running the algorithm so it needs to be able to cope with this.

Any help/advice/papers/snippets greatly appreciated. I have 1500 records to match and have had to start this process manually to get it done on time.

amit
  • 175,853
  • 27
  • 231
  • 333
Tom N Tech
  • 260
  • 2
  • 10
  • 1
    Share what you've tried, please. You can sort anything if it implements the `IComparable` interface and you design your custom `compareTo` method: https://msdn.microsoft.com/en-us/library/system.icomparable.compareto(v=vs.110).aspx – TayTay Oct 30 '15 at 17:54
  • What does `B` go to `Cat 3` when it has both `Cat 2` and `Cat 3` but `D` goes to `Cat 2` when it has both `Cat 2` and `Cat 4`? – Justin Niessner Oct 30 '15 at 17:57
  • @JustinNiessner Because each piece must have 1 subject and you're basically trying to make sure each piece have at least one subject. D needs to have 2 since 4 is taken by C which means B must take 3. – Eric Hotinger Oct 30 '15 at 17:57
  • 2
    Normally "sorting by property" should be duplicate of http://stackoverflow.com/questions/3309188/how-to-sort-a-listt-by-a-property-in-the-object, but the question is about scheduling, not sorting... – Alexei Levenkov Oct 30 '15 at 17:59

1 Answers1

1

This looks like a bipartite graph matching problem to me, where the graph consists of two sides: Categories, Subjects. Edges are connectiones of categories to subjects.

The maximal matching of the graph, will also be the optimal result for some course x.

In your example, the bipartite graph is:

G=(V,U,E)
V = { Cat1, Cat2, Cat3, Cat4, Cat5}
U = { Subject A, Subject B, Subject C, Subject D, Subject E} 
E = { (A,1), (A,2), (B,2), (B,3), (C,4), (D,2), (D,4), (E,5) }

This can be solved in various ways (like converting it to maximal flow problem, or using the Hopcroft-Karp algorithm)

amit
  • 175,853
  • 27
  • 231
  • 333
  • Thank you @amit. I have done some research founded upon your answer and have begun developing a solution. I took inspiration from http://stackoverflow.com/questions/6366516/how-does-the-hopcroft-karp-algorithm-work for the actual algorithm implementation. – Tom N Tech Nov 01 '15 at 13:21