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 New, unsolved
New entry, edited from material collected for the archive and not yet in a released version.
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
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)
No solution was found in the collected postings.