rec.puzzles Archive

Table A lists all 70 combinations of the 8 letters A-H taken 4 at a time; table B lists all 28 combinations taken 6 at a time.

combinatorics/covering.records

Problem

Table A lists all 70 combinations of the 8 letters A-H taken 4 at a
time; table B lists all 28 combinations taken 6 at a time.  Select the
smallest set of records from table B such that every record of table A
is contained in at least one selected record.  Seven records are known
to suffice; can it be done with fewer?  What algorithm finds such a
set, and what law gives its size, here and for other cases (e.g. 10
letters in groups of 4 covered by groups of 6, 7 or 8)?

[ Editor: problem statement reconstructed from the posting. ]
Show solution
Seven is the minimum for 8 letters; 6 records cannot cover all 70
groups of 4.  This is the covering number C(8,6,4) = 7.

The trick is to look at what each record leaves out.  A record of 6
letters omits 2 letters, and it contains a group of 4 exactly when
the 2 omitted letters are both among the 4 letters the group omits.
So choosing records is choosing pairs of letters (the omitted pairs),
and the requirement is: every set of 4 letters (the complement of a
group) contains one of the chosen pairs.  Think of the chosen pairs
as the edges of a graph on the 8 letters; the requirement is that no
4 letters are pairwise unjoined.  By Turan's theorem (1941) the
fewest edges with that property are obtained by splitting the letters
into 3 groups as equal as possible, {3, 3, 2}, and joining every pair
inside a group: 3 + 3 + 1 = 7 edges.  Fewer edges always leave 4
pairwise unjoined letters, so 7 is optimal.

Solution E in the posting is exactly of this kind: its records omit
GH, EF, CF, CE, BD, AH and AG, i.e. the pairs inside the groups
{C, E, F}, {A, G, H} and {B, D}.  A recipe for a solution: split
A..H into ABC, DEF, GH and take the 7 records that omit AB, AC, BC,
DE, DF, EF or GH:

  CDEFGH  BDEFGH  ADEFGH  ABCFGH  ABCEGH  ABCDGH  ABCDEF

The same argument gives a formula whenever the records have 2 letters
fewer than the alphabet (v letters, groups of t, records of v - 2):
split the v letters into v - t - 1 groups as equal as possible and
take one record for each pair inside a group.  So for 10 letters,
groups of 4 and records of 8: five groups of 2, i.e. 5 records.  When
the records have 1 letter fewer than the alphabet, t + 1 records are
needed (for 7 letters, groups of 4, records of 6: 5, as the posting
found).

In general the problem is that of a covering design: C(v,k,t) is the
fewest k-subsets of a v-set covering every t-subset.  There is no
closed formula; the standard lower bound is Schonheim's,

  C(v,k,t) >= ceil( v/k ceil( (v-1)/(k-1) ... ceil( (v-t+1)/(k-t+1) )
              ... ) ),

and good coverings are found by computer search (greedy choice of
the record covering most uncovered groups, then local improvement,
simulated annealing, or exact branch and bound / integer programming
for small cases).  Tables of the best known coverings are kept in the
La Jolla Covering Repository (D. Gordon).  The greedy method of the
posting, take the first record covering an uncovered group, is far
from optimal; "take the record covering the most uncovered groups"
is much better, and is within a factor of about 1 + ln C(k,t) of
the optimum (the classical bound for greedy set covering).

Computed here (C++ exact search, the first record fixed by symmetry,
plus randomized greedy for upper bounds):

  C(7,6,4) = 5    C(8,6,4) = 7    C(9,6,4) = 12    C(10,8,4) = 5
  C(10,7,4): between 9 and 12 (exact search ruled out 8 within a
             minute; greedy found 12; Schonheim's bound is 9)
  C(10,6,4): between 19 and 20 (Schonheim's bound 19; greedy found
             20; exact search ruled out 15 within a minute)

The exact values for 10 letters with records of 6 or 7 would need a
longer exact search than was run here; the repository mentioned above
lists the best known values.
-- Claude (rec.puzzles Oracle, 2026-11-02)

[ Editor: the material collected earlier follows. ]

Goal: to select the minimum set of records in table B that covers
all the records in table A! Interestingly, I've written a few
programs in BASIC that have selected 15,12,11 and 8 records but
I do know you can select as few as 7 records that perform the same
task. What's the algorithm that can be used to select these records,
and not only in this case but, suppose you want to cover a table of 10
characters combined in groups of 4, in another table with these very same
characters combined in groups of 6, 7 or 8, etc.

Sample follows (8 chars. in groups of 4 and 6)
===============================================

Table A                        Table B
Chars: A B C D E F G H         Chars:A B C D E F G H
Combined in groups of 4:       Combined in groups of 6:
08-04-01                       08-06-01
------------------------       ------------------------
01: A B C D ---->---------.--- 01: A B C D E F <-- ex: this record covers
02: A B C E ----->--------|    02: A B C D E G     the recs. 01,02,03,06,07,
03: A B C F ------>-------|    03: A B C D E H     10,16,17,20,26,36,37,40,
04: A B C G               |    04: A B C D F G     46 & 56, in table A,
05: A B C H               |    05: A B C D F H     i.e., 15 hits, right?
06: A B D E ------->------|    06: A B C D G H     but that's true for every
07: A B D F               |    07: A B C E F G     record in this table -
08: A B D G               |    08: A B C E F H     but there's a best set of
09: A B D H               |    09: A B C E G H     them that can cover all of
10: A B E F -------->-----'    10: A B C F G H     the recs. in table A. How
11: A B E G                    11: A B D E F G     can we select them?
12: A B E H                    12: A B D E F H
13: A B F G                    13: A B D E G H
14: A B F H                    14: A B D F G H
15: A B G H                    15: A B E F G H
16: A C D E  ..etc             16: A C D E F G
17: A C D F                    17: A C D E F H
18: A C D G                    18: A C D E G H
19: A C D H                    19: A C D F G H
20: A C E F                    20: A C E F G H
21: A C E G                    21: A D E F G H
22: A C E H                    22: B C D E F G
23: A C F G                    23: B C D E F H
24: A C F H                    24: B C D E G H
25: A C G H                    25: B C D F G H
26: A D E F                    26: B C E F G H
27: A D E G                    27: B D E F G H
28: A D E H                    28: C D E F G H
29: A D F G
30: A D F H
31: A D G H
32: A E F G
33: A E F H
34: A E G H
35: A F G H
36: B C D E
37: B C D F
38: B C D G
39: B C D H
40: B C E F
41: B C E G
42: B C E H
43: B C F G
44: B C F H
45: B C G H
46: B D E F
47: B D E G
48: B D E H
49: B D F G
50: B D F H
51: B D G H
52: B E F G
53: B E F H
54: B E G H
55: B F G H
56: C D E F
57: C D E G
58: C D E H
59: C D F G
60: C D F H
61: C D G H
62: C E F G
63: C E F H
64: C E G H
65: C F G H
66: D E F G
67: D E F H
68: D E G H
69: D F G H
70: E F G H


Solutions we've reached: (all these sets contain all the records in table A)

Solution A                      Solution B                  Solution C
Process  A                      Process  B                  Process  C
----------                      ----------                  ----------
08(46)11.a                      08(46)11.b                  08(46)11.c

01: A B C D E F                 03: A B C D E H             01: A B C D E F
02: A B C D E G                 06: A B C D G H             10: A B C F G H
03: A B C D E H                 10: A B C F G H             14: A B D F G H
04: A B C D F G                 14: A B D F G H             15: A B E F G H
05: A B C D F H                 15: A B E F G H             19: A C D F G H
06: A B C D G H                 19: A C D F G H             20: A C E F G H
07: A B C E F G                 20: A C E F G H             21: A D E F G H
08: A B C E F H                 21: A D E F G H             25: B C D F G H
09: A B C E G H                 25: B C D F G H             26: B C E F G H
10: A B C F G H                 26: B C E F G H             27: B D E F G H
11: A B D E F G                 27: B D E F G H             28: C D E F G H
12: A B D E F H                 28: C D E F G H             -------------------
13: A B D E G H                 -------------------         11 records selected
14: A B D F G H                 12 records selected
15: A B E F G H
--------------------
Interesting, the 1st
15 records!


Solution D                      Solution E                  Solution F
Process  D                      Process  E                  Process  F
----------                      ----------                  ----------
08(46)11.d                      08(46)11.e                  08(46)11.f

01: A B C D E F                 01: A B C D E F             ??????????
06: A B C D G H                 06: A B C D G H             is it possible
15: A B E F G H                 13: A B D E G H             to select even
20: A C E F G H                 14: A B D F G H             less records?
21: A D E F G H                 20: A C E F G H             ??????????
26: B C E F G H                 22: B C D E F G
27: B D E F G H                 23: B C D E F H
28: C D E F G H                 ------------------
------------------              7 records selected
8 records selected


How I've reached Solution A:
Quite naive:

   set an empty table that will hold the final result (condensed table)
   start checking every entry in the table A(4 chars)
    if final table is empty then
     |select the 1st record in table B(6 chars) that has--
(a)--| --all the chars of the record in table A
     |save this record in the final table
    else
      scan the final table checking for a record that covers the record of--
       --table A
      if not found then do step (a)
    end if
   end checking table A

You can tell how many records will be selected by this algorithm applying
the following formula:

#of Recs = (Mathematical Formulas)  - Formation Law

a = Rate of Combining - group for the first  combining (the lowest) = 4
b = Rate of Combining - group for the second combining (the greatest) = 6
c = Quantity of elements to combining = 8

b - a = d   6 - 4 = 2
c - (b - a) = 8 - 2 = 6

Combining six (6) elements with a Rate of 4 groups


 a     4          6 x 5 x 4 x 3          [Editor: was 6 x 5 x 4 x 4]
C   = C  = ---->  ------------- = 3 x 5 = 15
 c     6          1 x 2 x 3 x 4


For the other algorithms I've adopted a similar solution, but 1st I
created a 3rd table containing each record of table B broken into
as many records of table A as it would be possible to combine. Then,
I've selected the records that had the widest range of covering the
records of table A, by its order. I can send these codes both in
QuickBasic(tm) and/or CA-Clipper(tm) upon request.

Just as a guide, it is possible to achieve the following results:


     |# total|# total| # total of records selected in the group of 6, that
# of |combin.|combin.| cover all the records in the group of 4
chars| 4 x 4 | 6 x 6 |        ===Processes Applied===
-----|-------|-------|----------------------------------------------------
     |       |       |  A  |  B  |  C  |  D  |  E  |   F  |
     |       |       |-----|-----|-----|-----|-----|------|
07   |    35 |     7 |   5 |     |     |     |     |   ?  |
08   |    70 |    28 |  15 |  12 |  11 |  8  |  7  |   ?  |
09   |   126 |    84 |  35 |     |     |     |     |   ?  |
10   |   210 |   210 |  70 |     |     |     |     |   ?  |
11   |   330 |   462 | 126 |     |     |     |     |   ?  |
12   |   495 |   924 | 210 |     |     |     |     |   ?  |
13   |   715 | 1.716 | 330 |     |     |     |     |   ?  |
14   | 1.001 | 3.003 | 495 |     |     |     |     |   ?  |

...etc

Questions:

01 - What's the algorithm that defines the solution E?

02 - What's the Law that applies to calculates the number of records
     for the solution E?

03 - Is it possible to determine a solution F, to reduce even more, the
     number of combinations found (12 - process E / solution E)? If so,
     what is it:
           03.1 - the algorithm that defines solution F?
           03.2 - the Law for calculating the number of records for the
                  solution F?

[ Editor: Solution E above has 7 records, not 12. ]

-- Ismenio de Melo Sousa <ismenio@elogica.com.br>  (January 1997)