Re: Pairing algorithm

[Lucia Moura <lucia@cs.toronto.edu>]

> ------------------------------------------------------------------------
>    I need some help with an algorithm.
> 
>  I have 12 objects that need to be paired in threes, with NO DUPLICATES,
> until each entity has been paired with all others once.
> 
> Cal C. Pettengill
> CCP Software
> Reno, Nevada, USA
> ------------------------------------------------------------------------

It seems you need a Steiner triple system or related object.

A Steiner triple system of order v  (STS(v)) is a collection of 
3-subsets (or triples) of {1,2,...,v} such that every 2-subset (pair)
in {1,2,...,v} appears EXACTLY in one of the triples.
For example, STS(7): {1,2,3} {1,4,5} {1,6,7} {2,4,6} {2,5,7} {3,4,7} {3,5,6}
But a STS(12) does not exist... 
A STS(v) exists if and only if v = 1 or 3 (mod 6).

If your problem is of the "covering type", you substitute the word
"EXACTLY" by "AT LEAST" in the above definition (i.e. every pair appears
in one of the triples but some pairs may appear more than once).
Such an object is called a "covering by triples" CT(v,1) or 
a 2-(v,3,1) covering design.

The optimal (with smallest number of triples) covering by triples of order v=12 
has 24 triples, and covers every pair once and 6 pairs twice. 
There are constructions in the literature (for instance see Ch.10 of 
the book "Triple Systems" by Colbourn and Rosa, Oxford University Press 1999).

I can send you a CT(12,1), if that is what you need.

Regards,

Lucia Moura

University of Toronto/ The Fields Institute