Algorithm that generates a group of men and women who are each interested in everyone from the other gender

In my dating app, I need to compile lists of men and women where all of the men in the list are potentially interested in all of the women in the list, and vice versa.

That is, in a list of 10 men and 10 women, any given women matches the criteria set by all 10 men and any given man matches the criteria of all 10 women. I don't want any men in the group who aren't of interest to all the women, and vice versa.

The criteria is very simple. The properties for each person are:

• Age
• Interests (array)
• Desired partner's age range

Example: if `Man1` is described as

• 31
• Cooking, tennis, math
• 20, 31

A `29` year old woman who likes tennis and is looking for a man between `x<=31` and `y>=31` is a match.

I've been thinking about how to implement this, but it's unlike any simple data fetching/manipulation I've ever done. The reason is because rather than being a single query, (i.e. get all people where `gender=female` AND `age>=low & age<=hight` etc..) the query has to be checked anew each time when a new person is added. That is, each time a new man or woman is added to the list, all subsequent people have to be checked against them too (because I don't want to add a man who one or more women don't find interesting).

Does anyone have any ideas on a strategy for implementing this algorithm.

As an aside, I am using MongoDB, so if comfortable for you, it would be great to speak in those terms.

Thank you very much in advance!

• I can't think of a complete solution to this, but I'm certain it'd involve either triggers or views or both, so while you're waiting for a full answer you may want to read up on MongoDB's support for triggers and views. Mar 22, 2015 at 11:42
• How do you create the list? How does it begin? By specifying a single person, or a set, or by declaring some starting criteria? Every time you add someone you'll need to update (necessarily restrict) the constraints to be in the list, so the order in which you add people is going to matter. Mar 22, 2015 at 11:42
• I might use an elastic search tool like lucene. Tag people with these fields (what they require and offer) and search on the basis of this later. May not work, but worth looking ar. Mar 22, 2015 at 11:49
• Are you looking for one group, the biggest possible group, all possible groups, all possible groups which cannot be increased by adding another person? Or disjoint groups? Please clarify. Mar 22, 2015 at 12:30
• @DocBrown I want the algorithm to take as input, a number specifying the amount of each gender. To keep it simple, the number of men and women should be the same. So a single integer input defines both Mar 22, 2015 at 12:53

In other words, the whole database would have to undergo some major reindexing (recalculating all the matches) every time a new person is added.

The strategy in such cases is to maintain a smaller, cached dataset ("delta"), in this case containing new people added throughout the day, which gets merged into the database on a daily basis - could be at night, where the server isn't so busy.

How would it work in your case?

Every new person is added into delta - sort of a waiting room. For these people, we can calculate their "top 10" matches immediately.

Old users don't get to see new users just yet. (Or you might recalculate 10 top matches only for people who popped up as top 10 matches for that new person, as that shouldn't be too expensive in terms of resources).

Every night delta gets merged into the main index and everybody's matches get recalculated.

The tradeoff here is that new people may not appear immediately in search results.

I think you are looking for bipartite(men/women) complete(all men like all women and viceversa). I would tackle the problem from a graph perspective where each user is a node and two nodes are connected if they are mutually interested. Then you can create a matrix and apply some kind of clustering or graph pattern mining. If you think this can help I can provide links when at home(writing from my mobile). I don't know if MongoDB can solve this problem.

• wow I literally just left a comment to this end! Mar 23, 2015 at 11:17
• Glad we are on the same page.if you go for the clustering the size of the groups will be given by the solution but not sure how to guarantee the completeness. From the pattern mining the completeness can be guaranteed more easily. From the graph perspective it can also help to calculate another table indicating how many common matches the nodes have. Mar 23, 2015 at 11:34