couples.jl

using Combinatorics
using Random

couples = 1:8
possible_groups = combinations(couples, 3)

function doit(couples, possible_groups)
    has_not_met = [couple => setdiff(couples, couple) for couple in couples]

    selected_groups = []

    for grp in possible_groups
        # If this grouping includes any couples who have not met each other yet
        if any(!isempty(intersect(grp, unmet)) for unmet in last.(has_not_met))
            push!(selected_groups, grp)
            # Update has_not_met
            map!(has_not_met, has_not_met) do (couple, unmet)
                if couple in grp
                    couple => setdiff!(unmet, grp)
                else
                    couple => unmet
                end
            end
        end
    end

    selected_groups
end

best = doit(couples, possible_groups)
grps = collect(possible_groups)

function lazy_search(best, grps, iterations)
    for _ in 1:iterations
        candidate_grps = doit(couples, shuffle!(grps))
        if length(candidate_grps) < length(best)
            best = candidate_grps
        end
    end
    best
end

best = lazy_search(best, grps, 10^5)

# Best found so far:
best = [
 [3, 6, 7],
 [2, 5, 6],
 [2, 4, 7],
 [3, 5, 8],
 [1, 2, 3],
 [2, 6, 8],
 [4, 7, 8],
 [1, 4, 7],
 [3, 4, 5],
 [1, 5, 7],
 [2, 4, 6],
 [1, 6, 8],
]

# Number of groups each couple is in
[couple => count((in(couple, grp)) for grp in best) for couple in couples]