search

ilyakava / sup

A web app to bring together a company's members
32 stars 14 forks source link

Use backtracking #73

Open dblock opened 7 years ago

dblock commented 7 years ago

Here's a simple and effective approach: https://github.com/dblock/slack-sup/blob/master/slack-sup/models/round.rb#L64. Could use some improvement as described in https://github.com/jimwise/ambit/issues/1

ilyakava commented 7 years ago

Nice repo you've got there. You'll notice I closed a bunch of issues here b/c your repo should be the future of sup. Any code that I may write in the future would be only related to taking a graph as input, and throwing a partition into triangles as output.

As far as backtracking goes, this repo uses the concept.

ilyakava commented 7 years ago

As you note in the comment on ambit, for this particular problem, there are so many bad triplets. If we take a look at a graph where connects indicate a person may meet with another person, it is very sparse. That is the motivation for not using a generate and check method in this repo.

In the 3DM and PIT issues in fact the assumption is that all valid triplets have been generated, and all that remains is to pick as many as possible that don't overlap. This latter problem is much more computationally intensive.

dblock commented 7 years ago

Btw, we're now using slack-sup at Artsy, https://sup.playplay.io