You have C_4_14 possible combinations (14*13*12*11/(4*3*2*1)) = 1001 possible groups of 4.
You want to be sure that you have all the possible pairs C_2_14 14*13/(2*1) = 91 pairs.
In each group of 4, you have C_2_4 = 6 pairs.
Let's assign a bit for each possible pair (we need a 91 bits integer).
Now each group of 4 can be written as a 91 bit integer signature with only 6 bits set representing the 6 pairs.
The problem now, is to assemble the groups, so that each pair is represented at least once.
This is equivalent to a bitOr operation (no matter whether the pair is in a group OR in another group).
And since we want all the pairs to be represented, we want to choose a subset of the possible 1001 groups, such that the bitOr of the subset is 2^91-1 (all pair are represented at least once).
Since we have 91 pairs, 6 pairs per group, 6*15 < 91 < 6*16, this gives us a lower bound: we need at least 16 groups of 4 to achieve this, maybe more.
At best, we will have 5 pairs of persons meeting twice, at worse, you could have a single pair meeting 6 times.
To solve the problem, we have to choose an indexing of the pairs, for example:
(1,2) = 1
(1,3) = 2
...
(1,14) = 13
(2,3) = 14
...
(2,14) = 25
...
(13,14) = 91
Here is an example Squeak Smalltalk code for forming the pairs
people := #(mary john clara tim julia mike vanessa bob jean harry kim donald morgan roy).
pairMap := Dictionary new: 91.
i := 0.
people combinations: 2 atATimeDo: [:p |
pairMap at: p copy put: (i := i+1)].
Now, for each group of four, we can associate the pair signature:
quadMap := Dictionary new: 1001.
iQuadMap := Dictionary new: 1001.
people combinations: 4 atATimeDo: [:q | | j |
j := 0.
q combinations: 2 atATimeDo: [:p| j := j bitAt: (pairMap at: p) put: 1].
quadMap at: q copy put: j.
iQuadMap at: j put: q copy].
A very naive solution could be to enumerate the combinations of nGroup of quads until we find a combination covering all the pairs. nGroup would start at 16.
allPairs := 1<<91-1.
16 to: 91 do: [:nGroup |
quadMap values combinations: nGroup atATimeDo: [:g |
(g reduce: #bitOr:) = allPairs ifTrue: [^g collect: [:signature | iQuadMap at: signature]]]].
As you can see, the combinatorial is huge, C_16_1001 = 43,051,823,251,587,106,104,672,087,435,021,150 so above loop probably won't be achieved in a reasonable time, and at this stage we don't even know if there is a solution with 16 groups !
We can try some trivial greedy algorithm instead: choose the next group as one maximizing the number of bits (minimizing the overlapping bits) with the solution signature so far.
Overlapping bits can be counted with a bitAnd operation
allPairs := 1<<91-1.
signatureSoFar := 0.
groups := OrderedCollection new.
[ signatureSoFar = allPairs]
whileFalse:
[heap := Heap withAll: quadMap values sortBlock: [:x | (x bitAnd: signatureSoFar ) bitCount] ascending.
groups add: heap first.
signatureSoFar := signatureSoFar bitOr: heap first].
^groups collect: [:qSig | iQuadMap at: qSig]
Running this gives me a solution with 18 groups in a few milliseconds...
Running the greedy algorithm 10000 times with shuffled values gave me no shorter solution (solutions found were between 18 and 20 groups).
Up to you to find if this can be done in less than 18 groups.
