Skip to content

Instantly share code, notes, and snippets.

@sampritipanda

sampritipanda/pair_organiser.rb

Last active November 5, 2015 08:34
Show Gist options
  • Save sampritipanda/3a255be92a9b3bcc53c2 to your computer and use it in GitHub Desktop.
Save sampritipanda/3a255be92a9b3bcc53c2 to your computer and use it in GitHub Desktop.
Download ZIP
Finding all possible bipartite matchings in a set of nodes.
Raw
pair_organiser.rb
def recursive(a, b)
n = a.length
if n == 0 or n == 1 then
p b
return
end
(1...n).each do |i|
recursive(a - [a[0], a[i]], b + [[a[0], a[i]]])
end
end
a = %w{Pablo Dan Andrew Tom}
recursive(a, [])
# Output:
# [["Pablo", "Dan"], ["Andrew", "Tom"]]
# [["Pablo", "Andrew"], ["Dan", "Tom"]]
# [["Pablo", "Tom"], ["Dan", "Andrew"]]
@tansaku
Copy link

tansaku commented Nov 5, 2015

thanks @sampritipanda. I just tried that with 8:

2.2.3 :012 > a = ["Pablo", "Dan", "Andrew", "Tom", "Rob", "Jay", "Norm", "Yev"]
 => ["Pablo", "Dan", "Andrew", "Tom", "Rob", "Jay", "Norm", "Yev"] 
2.2.3 :013 > recursive(a, [])
[["Pablo", "Dan"], ["Andrew", "Tom"], ["Rob", "Jay"], ["Norm", "Yev"]]
[["Pablo", "Dan"], ["Andrew", "Tom"], ["Rob", "Norm"], ["Jay", "Yev"]]
[["Pablo", "Dan"], ["Andrew", "Tom"], ["Rob", "Yev"], ["Jay", "Norm"]]
[["Pablo", "Dan"], ["Andrew", "Rob"], ["Tom", "Jay"], ["Norm", "Yev"]]
[["Pablo", "Dan"], ["Andrew", "Rob"], ["Tom", "Norm"], ["Jay", "Yev"]]
[["Pablo", "Dan"], ["Andrew", "Rob"], ["Tom", "Yev"], ["Jay", "Norm"]]
[["Pablo", "Dan"], ["Andrew", "Jay"], ["Tom", "Rob"], ["Norm", "Yev"]]
[["Pablo", "Dan"], ["Andrew", "Jay"], ["Tom", "Norm"], ["Rob", "Yev"]]
[["Pablo", "Dan"], ["Andrew", "Jay"], ["Tom", "Yev"], ["Rob", "Norm"]]
[["Pablo", "Dan"], ["Andrew", "Norm"], ["Tom", "Rob"], ["Jay", "Yev"]]
[["Pablo", "Dan"], ["Andrew", "Norm"], ["Tom", "Jay"], ["Rob", "Yev"]]
[["Pablo", "Dan"], ["Andrew", "Norm"], ["Tom", "Yev"], ["Rob", "Jay"]]
[["Pablo", "Dan"], ["Andrew", "Yev"], ["Tom", "Rob"], ["Jay", "Norm"]]
[["Pablo", "Dan"], ["Andrew", "Yev"], ["Tom", "Jay"], ["Rob", "Norm"]]
[["Pablo", "Dan"], ["Andrew", "Yev"], ["Tom", "Norm"], ["Rob", "Jay"]]
[["Pablo", "Andrew"], ["Dan", "Tom"], ["Rob", "Jay"], ["Norm", "Yev"]]
[["Pablo", "Andrew"], ["Dan", "Tom"], ["Rob", "Norm"], ["Jay", "Yev"]]
[["Pablo", "Andrew"], ["Dan", "Tom"], ["Rob", "Yev"], ["Jay", "Norm"]]
[["Pablo", "Andrew"], ["Dan", "Rob"], ["Tom", "Jay"], ["Norm", "Yev"]]
[["Pablo", "Andrew"], ["Dan", "Rob"], ["Tom", "Norm"], ["Jay", "Yev"]]
[["Pablo", "Andrew"], ["Dan", "Rob"], ["Tom", "Yev"], ["Jay", "Norm"]]
[["Pablo", "Andrew"], ["Dan", "Jay"], ["Tom", "Rob"], ["Norm", "Yev"]]
[["Pablo", "Andrew"], ["Dan", "Jay"], ["Tom", "Norm"], ["Rob", "Yev"]]
[["Pablo", "Andrew"], ["Dan", "Jay"], ["Tom", "Yev"], ["Rob", "Norm"]]
[["Pablo", "Andrew"], ["Dan", "Norm"], ["Tom", "Rob"], ["Jay", "Yev"]]
[["Pablo", "Andrew"], ["Dan", "Norm"], ["Tom", "Jay"], ["Rob", "Yev"]]
[["Pablo", "Andrew"], ["Dan", "Norm"], ["Tom", "Yev"], ["Rob", "Jay"]]
[["Pablo", "Andrew"], ["Dan", "Yev"], ["Tom", "Rob"], ["Jay", "Norm"]]
[["Pablo", "Andrew"], ["Dan", "Yev"], ["Tom", "Jay"], ["Rob", "Norm"]]
[["Pablo", "Andrew"], ["Dan", "Yev"], ["Tom", "Norm"], ["Rob", "Jay"]]
[["Pablo", "Tom"], ["Dan", "Andrew"], ["Rob", "Jay"], ["Norm", "Yev"]]
[["Pablo", "Tom"], ["Dan", "Andrew"], ["Rob", "Norm"], ["Jay", "Yev"]]
[["Pablo", "Tom"], ["Dan", "Andrew"], ["Rob", "Yev"], ["Jay", "Norm"]]
[["Pablo", "Tom"], ["Dan", "Rob"], ["Andrew", "Jay"], ["Norm", "Yev"]]
[["Pablo", "Tom"], ["Dan", "Rob"], ["Andrew", "Norm"], ["Jay", "Yev"]]
[["Pablo", "Tom"], ["Dan", "Rob"], ["Andrew", "Yev"], ["Jay", "Norm"]]
[["Pablo", "Tom"], ["Dan", "Jay"], ["Andrew", "Rob"], ["Norm", "Yev"]]
[["Pablo", "Tom"], ["Dan", "Jay"], ["Andrew", "Norm"], ["Rob", "Yev"]]
[["Pablo", "Tom"], ["Dan", "Jay"], ["Andrew", "Yev"], ["Rob", "Norm"]]
[["Pablo", "Tom"], ["Dan", "Norm"], ["Andrew", "Rob"], ["Jay", "Yev"]]
[["Pablo", "Tom"], ["Dan", "Norm"], ["Andrew", "Jay"], ["Rob", "Yev"]]
[["Pablo", "Tom"], ["Dan", "Norm"], ["Andrew", "Yev"], ["Rob", "Jay"]]
[["Pablo", "Tom"], ["Dan", "Yev"], ["Andrew", "Rob"], ["Jay", "Norm"]]
[["Pablo", "Tom"], ["Dan", "Yev"], ["Andrew", "Jay"], ["Rob", "Norm"]]
[["Pablo", "Tom"], ["Dan", "Yev"], ["Andrew", "Norm"], ["Rob", "Jay"]]
[["Pablo", "Rob"], ["Dan", "Andrew"], ["Tom", "Jay"], ["Norm", "Yev"]]
[["Pablo", "Rob"], ["Dan", "Andrew"], ["Tom", "Norm"], ["Jay", "Yev"]]
[["Pablo", "Rob"], ["Dan", "Andrew"], ["Tom", "Yev"], ["Jay", "Norm"]]
[["Pablo", "Rob"], ["Dan", "Tom"], ["Andrew", "Jay"], ["Norm", "Yev"]]
[["Pablo", "Rob"], ["Dan", "Tom"], ["Andrew", "Norm"], ["Jay", "Yev"]]
[["Pablo", "Rob"], ["Dan", "Tom"], ["Andrew", "Yev"], ["Jay", "Norm"]]
[["Pablo", "Rob"], ["Dan", "Jay"], ["Andrew", "Tom"], ["Norm", "Yev"]]
[["Pablo", "Rob"], ["Dan", "Jay"], ["Andrew", "Norm"], ["Tom", "Yev"]]
[["Pablo", "Rob"], ["Dan", "Jay"], ["Andrew", "Yev"], ["Tom", "Norm"]]
[["Pablo", "Rob"], ["Dan", "Norm"], ["Andrew", "Tom"], ["Jay", "Yev"]]
[["Pablo", "Rob"], ["Dan", "Norm"], ["Andrew", "Jay"], ["Tom", "Yev"]]
[["Pablo", "Rob"], ["Dan", "Norm"], ["Andrew", "Yev"], ["Tom", "Jay"]]
[["Pablo", "Rob"], ["Dan", "Yev"], ["Andrew", "Tom"], ["Jay", "Norm"]]
[["Pablo", "Rob"], ["Dan", "Yev"], ["Andrew", "Jay"], ["Tom", "Norm"]]
[["Pablo", "Rob"], ["Dan", "Yev"], ["Andrew", "Norm"], ["Tom", "Jay"]]
[["Pablo", "Jay"], ["Dan", "Andrew"], ["Tom", "Rob"], ["Norm", "Yev"]]
[["Pablo", "Jay"], ["Dan", "Andrew"], ["Tom", "Norm"], ["Rob", "Yev"]]
[["Pablo", "Jay"], ["Dan", "Andrew"], ["Tom", "Yev"], ["Rob", "Norm"]]
[["Pablo", "Jay"], ["Dan", "Tom"], ["Andrew", "Rob"], ["Norm", "Yev"]]
[["Pablo", "Jay"], ["Dan", "Tom"], ["Andrew", "Norm"], ["Rob", "Yev"]]
[["Pablo", "Jay"], ["Dan", "Tom"], ["Andrew", "Yev"], ["Rob", "Norm"]]
[["Pablo", "Jay"], ["Dan", "Rob"], ["Andrew", "Tom"], ["Norm", "Yev"]]
[["Pablo", "Jay"], ["Dan", "Rob"], ["Andrew", "Norm"], ["Tom", "Yev"]]
[["Pablo", "Jay"], ["Dan", "Rob"], ["Andrew", "Yev"], ["Tom", "Norm"]]
[["Pablo", "Jay"], ["Dan", "Norm"], ["Andrew", "Tom"], ["Rob", "Yev"]]
[["Pablo", "Jay"], ["Dan", "Norm"], ["Andrew", "Rob"], ["Tom", "Yev"]]
[["Pablo", "Jay"], ["Dan", "Norm"], ["Andrew", "Yev"], ["Tom", "Rob"]]
[["Pablo", "Jay"], ["Dan", "Yev"], ["Andrew", "Tom"], ["Rob", "Norm"]]
[["Pablo", "Jay"], ["Dan", "Yev"], ["Andrew", "Rob"], ["Tom", "Norm"]]
[["Pablo", "Jay"], ["Dan", "Yev"], ["Andrew", "Norm"], ["Tom", "Rob"]]
[["Pablo", "Norm"], ["Dan", "Andrew"], ["Tom", "Rob"], ["Jay", "Yev"]]
[["Pablo", "Norm"], ["Dan", "Andrew"], ["Tom", "Jay"], ["Rob", "Yev"]]
[["Pablo", "Norm"], ["Dan", "Andrew"], ["Tom", "Yev"], ["Rob", "Jay"]]
[["Pablo", "Norm"], ["Dan", "Tom"], ["Andrew", "Rob"], ["Jay", "Yev"]]
[["Pablo", "Norm"], ["Dan", "Tom"], ["Andrew", "Jay"], ["Rob", "Yev"]]
[["Pablo", "Norm"], ["Dan", "Tom"], ["Andrew", "Yev"], ["Rob", "Jay"]]
[["Pablo", "Norm"], ["Dan", "Rob"], ["Andrew", "Tom"], ["Jay", "Yev"]]
[["Pablo", "Norm"], ["Dan", "Rob"], ["Andrew", "Jay"], ["Tom", "Yev"]]
[["Pablo", "Norm"], ["Dan", "Rob"], ["Andrew", "Yev"], ["Tom", "Jay"]]
[["Pablo", "Norm"], ["Dan", "Jay"], ["Andrew", "Tom"], ["Rob", "Yev"]]
[["Pablo", "Norm"], ["Dan", "Jay"], ["Andrew", "Rob"], ["Tom", "Yev"]]
[["Pablo", "Norm"], ["Dan", "Jay"], ["Andrew", "Yev"], ["Tom", "Rob"]]
[["Pablo", "Norm"], ["Dan", "Yev"], ["Andrew", "Tom"], ["Rob", "Jay"]]
[["Pablo", "Norm"], ["Dan", "Yev"], ["Andrew", "Rob"], ["Tom", "Jay"]]
[["Pablo", "Norm"], ["Dan", "Yev"], ["Andrew", "Jay"], ["Tom", "Rob"]]
[["Pablo", "Yev"], ["Dan", "Andrew"], ["Tom", "Rob"], ["Jay", "Norm"]]
[["Pablo", "Yev"], ["Dan", "Andrew"], ["Tom", "Jay"], ["Rob", "Norm"]]
[["Pablo", "Yev"], ["Dan", "Andrew"], ["Tom", "Norm"], ["Rob", "Jay"]]
[["Pablo", "Yev"], ["Dan", "Tom"], ["Andrew", "Rob"], ["Jay", "Norm"]]
[["Pablo", "Yev"], ["Dan", "Tom"], ["Andrew", "Jay"], ["Rob", "Norm"]]
[["Pablo", "Yev"], ["Dan", "Tom"], ["Andrew", "Norm"], ["Rob", "Jay"]]
[["Pablo", "Yev"], ["Dan", "Rob"], ["Andrew", "Tom"], ["Jay", "Norm"]]
[["Pablo", "Yev"], ["Dan", "Rob"], ["Andrew", "Jay"], ["Tom", "Norm"]]
[["Pablo", "Yev"], ["Dan", "Rob"], ["Andrew", "Norm"], ["Tom", "Jay"]]
[["Pablo", "Yev"], ["Dan", "Jay"], ["Andrew", "Tom"], ["Rob", "Norm"]]
[["Pablo", "Yev"], ["Dan", "Jay"], ["Andrew", "Rob"], ["Tom", "Norm"]]
[["Pablo", "Yev"], ["Dan", "Jay"], ["Andrew", "Norm"], ["Tom", "Rob"]]
[["Pablo", "Yev"], ["Dan", "Norm"], ["Andrew", "Tom"], ["Rob", "Jay"]]
[["Pablo", "Yev"], ["Dan", "Norm"], ["Andrew", "Rob"], ["Tom", "Jay"]]
[["Pablo", "Yev"], ["Dan", "Norm"], ["Andrew", "Jay"], ["Tom", "Rob"]]

and it's not quite generating what we need. That's generating a superset, and what we need is all the unique subsets of that group that make up a pairing assignment for a given day so that you can have people pairing with as many other people as possible without repeats ..

For 8 individuals there are only 7 unique pairings - it's those we want, not this bigger set - but maybe this is a useful start ...

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment