Help improve generation of sets of 3

[dblock]

I'm using ambit in https://github.com/dblock/slack-sup, specifically in https://github.com/dblock/slack-sup/blob/master/slack-sup/models/round.rb#L31, which is a rewrite of a much more complex https://github.com/artsy/sup.

In plain English: we want people to meet every week with some people from the company they haven't met in a long time.

We generate as many permutations of N (eg. 3) people out of M (eg. ~200 in our company), such as people appear only once, then we repeat a week later, but this time make sure that no 2 people in a triad have met last time (or in the past 3 months).

Two questions:

• Currently I was only able to avoid having people appear multiple times in the result set by storing the fact that they are meeting "centrally" and then checking against it, is there a better way to avoid backtracking over any of the people already in existing triads?

• The result is not always the most optimal, and I had to bake in abandoning after 60 seconds or so. Any suggestions of not having to do that or turning this into a selection of sets of triads? For example: 1) find a set of triads until no more triads are possible 2) store if more triads than last time 3) repeat with a new selection. I couldn't get that working.

PS: this gem, ambit, is a ... gem, an incredibly elegant solution to generic backtracking!

[jimwise]

Thank you for the kind words -- sorry for the slow response!

Looking through the linked issue, and will see if I have any suggestions

[jimwise]

Looking at this quickly, since met_recently abandons any combination where two of the users have met recently (if I'm reading this right!), you should be able to use #mark and #cut! to cut out any branch of the backtracking tree where a recently-met user appears. This will keep you from continuing to generate (and reject) such combinations.

[dblock]

Thanks @jimwise!

[dblock]

It has been a while, I came back to this problem, still using this library!

The goal is to generate the best possible group of N (3 in the example below) people to meet. Then do it again, avoiding having people that already met in the same group.

#!/usr/bin/ruby

require 'rubygems'
require 'ambit'

@best_solutions = []
@solutions = []

def choose_group_of_3(remaining_items, groups)
  @solutions << groups if remaining_items.size < 3

  group = [
    Ambit.choose(remaining_items),
    Ambit.choose(remaining_items),
    Ambit.choose(remaining_items)
  ]
  Ambit.fail! if group.uniq.length != group.length # no dups
  Ambit.fail! if groups.any? { |solved_group| solved_group.intersection(group).length > 0 } # any group already contains item
  Ambit.fail! if @best_solutions.any? { |best_solution| best_solution.any? { |best_solution_group| best_solution_group.intersection(group).length > 1 } } # any two intersecting in a previous solution

  remaining_items = remaining_items.reject { |item| group.include?(item) }
  choose_group_of_3(remaining_items, groups + [group])
end

def solve
  items = (1..12).to_a

  @solutions = []

  begin
    choose_group_of_3(items, [])
    Ambit.fail!
  rescue Ambit::ChoicesExhausted
  end

  best_solution = @solutions.sort_by { |s| -s.length }.first
  p best_solution
  @best_solutions << best_solution
end

3.times do
  solve
end

This implementation suffers from several problems that I can't seem to figure out.

1. I'd like to make N variable, but any loops cause Ambit to rewind in ways that I don't understand, so I can't figure out how to make group = .... Ambit.choose N items. The set of choices could also be reduced once an item is pulled, avoiding the first Ambit.fail but I don't know how to do that.

2. This implementation doesn't seem to find the best group. Here are 3 results.

   [[1, 2, 3], [4, 5, 7], [8, 9, 10], [11, 12, 13]]
   [[1, 4, 10], [2, 5, 11], [3, 7, 12]]
   [[1, 5, 6], [2, 4, 8], [3, 9, 11], [7, 10, 13]]

   The second run found a solution with 3 groups, but there was a better solution with 4 groups found in the 3rd iteration.

3. Collecting the final best result using @ is awkward, how can I extract groups when Ambit gives up?

4. I'd like to reject the solution that has fewer groups than the previous solution in the same iteration earlier.

https://github.com/dblock/ambit/blob/group-of-3/examples/grouop_of_3.rb

Appreciate any help.

[dblock]

I think I got it. I needed to return the result once there are not enough items to choose from and not keep remaining_items locally but pass it through to choose_group_of_3.

#!/usr/bin/ruby

require 'rubygems'
require 'ambit'

@solutions = []

def choose_group_of_3(remaining_items, groups)
  Ambit.assert(@solutions.none? { |previous| (previous & groups).length.positive? })
  return groups if remaining_items.size < 3

  group = [
    Ambit.choose(remaining_items),
    Ambit.choose(remaining_items),
    Ambit.choose(remaining_items)
  ].sort

  Ambit.assert(group.uniq.length == group.length) # no dups

  choose_group_of_3(remaining_items.reject { |item| group.include?(item) }, groups + [group])
end

def solve
  items = (1..12).to_a

  begin
    solution = choose_group_of_3(items, [])
    @solutions << solution
    p solution
  rescue Ambit::ChoicesExhausted
  end
end

100.times do
  solve
end

This quickly finds the first 50 or so, then starts taking a while.

[[1, 2, 3], [4, 5, 6], [7, 8, 9], [10, 11, 12]]
[[1, 2, 4], [3, 5, 6], [7, 8, 10], [9, 11, 12]]
[[1, 2, 5], [3, 4, 6], [7, 8, 11], [9, 10, 12]]
[[1, 2, 6], [3, 4, 5], [7, 8, 12], [9, 10, 11]]
[[1, 2, 7], [3, 4, 8], [5, 9, 10], [6, 11, 12]]
[[1, 2, 8], [3, 4, 7], [5, 9, 11], [6, 10, 12]]
[[1, 2, 9], [3, 4, 10], [5, 6, 7], [8, 11, 12]]
[[1, 2, 10], [3, 4, 9], [5, 6, 8], [7, 11, 12]]
[[1, 2, 11], [3, 4, 12], [5, 7, 8], [6, 9, 10]]
...