finding smallest combinations of a list form another list

[buckau]

Hi I am trying to create a function that will compare one list of elements against another list of elements and find the smallest number of enters from the first list that will contain all the elements in the second list.
e.g. lets say I have 8 items constructed in to blocks of 6 items this will give me an array containing 6 elements x 28 rows
Array1(28,6)

1) - 1, 2, 3, 4, 5, 6
2) - 1, 2, 3, 4, 5, 7
3) - 1, 2, 3, 4, 5, 8
4) - 1, 2, 3, 4, 6, 7
5) - 1, 2, 3, 4, 6, 8
6) - 1, 2, 3, 4, 7, 8
7) - 1, 2, 3, 5, 6, 7
8) - 1, 2, 3, 5, 6, 8
9) - 1, 2, 3, 5, 7, 8
10) - 1, 2, 3, 6, 7, 8
11) - 1, 2, 4, 5, 6, 7
12) - 1, 2, 4, 5, 6, 8
13) - 1, 2, 4, 5, 7, 8
14) - 1, 2, 4, 6, 7, 8
15) - 1, 2, 5, 6, 7, 8
16) - 1, 3, 4, 5, 6, 7
17) - 1, 3, 4, 5, 6, 8
18) - 1, 3, 4, 5, 7, 8
19) - 1, 3, 4, 6, 7, 8
20) - 1, 3, 5, 6, 7, 8
21) - 1, 4, 5, 6, 7, 8
22) - 2, 3, 4, 5, 6, 7
23) - 2, 3, 4, 5, 6, 8
24) - 2, 3, 4, 5, 7, 8
25) - 2, 3, 4, 6, 7, 8
26) - 2, 3, 5, 6, 7, 8
27) - 2, 4, 5, 6, 7, 8
28) - 3, 4, 5, 6, 7, 8

I now wont to reduce this array to the smallest amount or rows that will contain all the element combinations of a second array that uses the same 8 items but is constructed in blocks of 5 items giving me 56 rows of 5 elements Array2(56,5)
e.g.
Array2(56,5)
1 - 1, 2, 3, 4, 5
2 - 1, 2, 3, 4, 6
3 - 1, 2, 3, 4, 7
4 - 1, 2, 3, 4, 8
5 - 1, 2, 3, 5, 6
6 - 1, 2, 3, 5, 7
7 - 1, 2, 3, 5, 8
8 - 1, 2, 3, 6, 7
9 - 1, 2, 3, 6, 8
10 - 1, 2, 3, 7, 8
11 - 1, 2, 4, 5, 6
12 - 1, 2, 4, 5, 7
13 - 1, 2, 4, 5, 8
14 - 1, 2, 4, 6, 7
15 - 1, 2, 4, 6, 8
16 - 1, 2, 4, 7, 8
17 - 1, 2, 5, 6, 7
18 - 1, 2, 5, 6, 8
19 - 1, 2, 5, 7, 8
20 - 1, 2, 6, 7, 8
21 - 1, 3, 4, 5, 6
22 - 1, 3, 4, 5, 7
23 - 1, 3, 4, 5, 8
24 - 1, 3, 4, 6, 7
25 - 1, 3, 4, 6, 8
26 - 1, 3, 4, 7, 8
27 - 1, 3, 5, 6, 7
28 - 1, 3, 5, 6, 8
29 - 1, 3, 5, 7, 8
30 - 1, 3, 6, 7, 8
31 - 1, 4, 5, 6, 7
32 - 1, 4, 5, 6, 8
33 - 1, 4, 5, 7, 8
34 - 1, 4, 6, 7, 8
35 - 1, 5, 6, 7, 8
36 - 2, 3, 4, 5, 6
37 - 2, 3, 4, 5, 7
38 - 2, 3, 4, 5, 8
39 - 2, 3, 4, 6, 7
40 - 2, 3, 4, 6, 8
41 - 2, 3, 4, 7, 8
42 - 2, 3, 5, 6, 7
43 - 2, 3, 5, 6, 8
44 - 2, 3, 5, 7, 8
45 - 2, 3, 6, 7, 8
46 - 2, 4, 5, 6, 7
47 - 2, 4, 5, 6, 8
48 - 2, 4, 5, 7, 8
49 - 2, 4, 6, 7, 8
50 - 2, 5, 6, 7, 8
51 - 3, 4, 5, 6, 7
52 - 3, 4, 5, 6, 8
53 - 3, 4, 5, 7, 8
54 - 3, 4, 6, 7, 8
55 - 3, 5, 6, 7, 8
56 - 4, 5, 6, 7, 8

It should end up with an array containing 4 rows of 6 elements
1,2,3,4,5,6
1,2,3,4,7,8
1,2,5,6,7,8
3,4,5,6,7,8

I have tried comparing each set of elements from Array2 against each set of elements in array1 and counting how many times each row in array1 matches all the elements in array2 but all the rows come up with the same answer of 16

1) - 1, 2, 3, 4, 5, 6, 16
2) - 1, 2, 3, 4, 5, 7, 16
3) - 1, 2, 3, 4, 5, 8, 16
4) - 1, 2, 3, 4, 6, 7, 16
5) - 1, 2, 3, 4, 6, 8, 16
6) - 1, 2, 3, 4, 7, 8, 16
7) - 1, 2, 3, 5, 6, 7, 16
8) - 1, 2, 3, 5, 6, 8, 16
9) - 1, 2, 3, 5, 7, 8, 16
10) - 1, 2, 3, 6, 7, 8, 16
11) - 1, 2, 4, 5, 6, 7, 16
12) - 1, 2, 4, 5, 6, 8, 16
13) - 1, 2, 4, 5, 7, 8, 16
14) - 1, 2, 4, 6, 7, 8, 16
15) - 1, 2, 5, 6, 7, 8, 16
16) - 1, 3, 4, 5, 6, 7, 16
17) - 1, 3, 4, 5, 6, 8, 16
18) - 1, 3, 4, 5, 7, 8, 16
19) - 1, 3, 4, 6, 7, 8, 16
20) - 1, 3, 5, 6, 7, 8, 16
21) - 1, 4, 5, 6, 7, 8, 16
22) - 2, 3, 4, 5, 6, 7, 16
23) - 2, 3, 4, 5, 6, 8, 16
24) - 2, 3, 4, 5, 7, 8, 16
25) - 2, 3, 4, 6, 7, 8, 16
26) - 2, 3, 5, 6, 7, 8, 16
27) - 2, 4, 5, 6, 7, 8, 16
28) - 3, 4, 5, 6, 7, 8, 16

I am using VBA in Access2000
Can any one offer a solution to this for me to try out?
Thanks

 

[gemma-the-husky]

i dont understand this

in the first example, you are looking for combinations perming 6 from which is 28 items as you say (effectively 8*7/1*2)

but what are you then trying to do to produce the second set. I realy dont understand this.

 

[buckau]

Hi thanks for the response
In the first array Array1 (28,6) I have all the possible combinations of 6 from 8
In the second array (Array2 (56,5) I have all the possible combinations of 5 from 8
The next step is to find the minimum amount of rows in Array1 that will cover all the items in array2 giving a pick 6 with a 5 from 6 guarantee
I should end up with from Array2 as the elements that will achieve this

1) 1,2,3,4,5,6
6) 1,2,3,4,7,8
15) 1,2,5,6,7,8
28) 3,4,5,6,7,8

My problem is that I cannot find out a way of doing this every thing I try keeps Cumming up with the same result! Was hopping sone one could have some suggestions on how to filter or sort this first array Array1 against Array2 to achieve this end.

 

[gemma-the-husky]

ah i see

6 from 8 is (8x7/1x2 = 28) (ie same as 2 from 8)
5 from 8 is (8x7x6/1x2x3 = 56) (ie same as 3 from 8)

are you in UK - sounds similar to the football coupon plan, where eg, you pick 16 selections, and you were guaranteed a first dividend if you had 10 draws - that sort of thing?

if so, i'm really not sure - i'm pretty good at working out the probabliities in general, but i'm not sure how to construct a limited number of lines, that offer certain guarantees.

how do you KNOW? the answer should be 4 rows - its interesting because each number occurs 3 times in the 4 rows. So is there a formula that calculates the number of rows you need? Or is all you need to select 4 rows SUCH that each number occurs 3 times.

if that is all then wouldnt these 4 rows below ALSO give you the same guarantee - none of which are the same as yours. And if you put these 4 with your 4, to give an 8 row selection, what guarantee would that give you.

And if you KNOW the outcome you need, then it should be possible to construct an algorithm to give you the correct result.

alternative selection of rows
123  678
12 45 78
 234567
1 3456 8

These things always involved a bit of luck - ie if you were lucky you may get all 6, but the guarantee was something like, if you pick 6, then you are guaranteed at least 5 (or 2 lots of 5) etc

 

[buckau]

Hi thanks for the reply
I know the answer is supposed to be 4 rows because I am using a method that was created by some one else and in this example the answer is 4 rows if the selection is changed to a pool of 9 items (numbers) and the set size is 6 and the guarantee is 5 from 6 (eg if 6 of the 9 are picked then at least 5 will be in one row) the number of rows increases to 8

1,2,3,4,5,6
1,2,3,4,7,8
1,2,5,6,7,8
3,4,5,6,7,8
1,2,3,5,7,9
1,2,4,6,7,9
1,2,4,5,8,9
1,2,3,6,8,9
The idea is to reduce the amount of possible combinations to the minimum and still maintain the guarantee
I have created a function that will create all the possible combinations of a pool of numbers from 3 to 100 in sets 3 to 20 and it works very fast and well I am now trying to create another function that will create the guarantee elements result
I first create all possible combinations pool =8 Set size = 6 = 28 combinations I then create all possible combinations of the guarantee that I wish pool= 8 set size = 5 (a guarantee of 5) . and this is where I am having the problem to compare the first set against the guarantee set and come up with the most probable combinations the full fill the guarantee.

 

[gemma-the-husky]

I know the answer is supposed to be 4 rows because I am using a method that was created by some one else and in this example the answer is 4 rows if the selection is changed to a pool of 9 items (numbers) and the set size is 6 and the guarantee is 5 from 6 (eg if 6 of the 9 are picked then at least 5 will be in one row) the number of rows increases to 8

so there are 2 issues

1) what is the formula that identIfies the number of rows you need - IE HOW DO YOU know the answer is a set of 4, or 8 rows

2) what is the algorithm that produces a set of rows that satifies the formula criteria

it seems to me that you probably need to know the answer to 1) in order to produce the answer 2)

 

[gemma-the-husky]

the selection from 9 candidates is subtly different

1,2,3,4,5,6
1,2,3,4,7,8
1,2,5,6,7,8
3,4,5,6,7,8
1,2,3,5,7,9
1,2,4,6,7,9
1,2,4,5,8,9
1,2,3,6,8,9

the frequencies here are

1 7
2 7
3 5
4 5
5 5
6 5
7 5
8 5
9 4

so how do you know
a) this gives the guaranteee and/or
b) you cant achieve this with fewer than 8 rows


----------
eg i just tried empirically to see what happens in your first case (6 from 8. and 5 from 8)
using only 3 rows

123456
134578
245678

gets 5 from 6, for every row of 6 except 1 - (123678) - Now I am sure your supposition that you need 4 rows is correct, but how do you prove that you need 4 rows to do this, and that you couldnt find a different set of 3 rows to satisfy the guarantee.

 

[buckau]

Hi again
I agree with every thing you are saying and that’s my problem I do not know how to do that!
A calculate how many rows there should be. Though I do not know if this is very significant, if you can cross check the 2 arrays then it should be possible to keep looping through until no more reductions are possible! As for the formula I believe it is

C = (v,k,t,m,I,b)
C = Covering Design
V = total numbers (pool i.e. 8)
K = Numbers per set (i.e. 6)
T = Minimum hit size (i.e. 5) Guarantee
M = if within the v- (total numbers) have maximum hits of (ie.6) Guarantee from hits
I = guarantees how many times t-minimum hits will occur within the design (ie.5)
B = number of sets (>= 1)

Example 1: c (31,6,2,2,1,31)
= A wheel (with 31 nbr, 6 nbr per set, minimum hits 2, if within total numbers have 2 hits, quantity of 2 hits =1, with 31 sets)

Example 2: c (49,6,3,6,1,168)
= A wheel (with 49 nbr, 6 nbr per set, minimum hits 3, if within total numbers have 6 hits, quantity of 3 hits =1, with 168 sets)

All of this I have obtained from other sources and books but non explain how to convert this in to code and that what I am having a problem with.
That is why I am working on a small set of numbers e.g pool of 8 numbers and sets of 6 numbers with a guarantee of 5 from 6 if 6 of the 8 pool numbers are hits almost every one I know of that has this combination has come up with the same set of 4 rows as the answer so if I cam code to achieve this then I can test the code against others combinations and sets to see if the code is solid and accurate
There are other variations of this formula where they have omitted the I and or the b
C = (v,k,t,m,b)
C = (v,k,t,m)
There has to be a simple way to do this calculation using code!

 

[gemma-the-husky]

i dont think we are going to find this easily by first principles

i think I would need to see some alogorthim for this

i dont really like the idea of selecting a solution, and trying to improve it - that doesnt sound sufficeintly rigorous

can you quote any online sources - although its a lot of work, and I cant guarantee I will have time to look at it

 

[buckau]

the only code i have been able to find in is Python and i can not work it out