How do I find the least number of subsets of 6's without using brut force?
gnh...@gmail.com
the smallest combination of 6s with a range of 10 consecutive numbers?
What is the formula for the least combination of 6s?
Here is the data
1) All the combinations of 4s in a range of 10 numbers
1 1 2 3 4
2 1 2 3 5
3 1 2 3 6
...
full result of all combinations of 4s truncated to save space
.....
208 6 7 9 10
209 6 8 9 10
210 7 8 9 10
2) The result for combining all 4s into the least number
of 6s is 21 combinations of 6s:
I believe there is a way of calculating what is the minimum
combinations
or groups to do that?
Could someone please explain how it works and I can get a better
result than 21?
Because even by using brut force I don't think this is the right
answer?
1 1 2 3 4 5 6
2 1 2 3 4 7 8
3 1 2 3 4 9 10
4 1 2 4 5 7 10
5 1 2 4 6 8 9
6 1 2 5 6 7 9
7 1 2 5 6 8 10
8 1 3 5 6 7 8
9 1 3 5 6 9 10
10 1 3 7 8 9 10
11 1 4 5 8 9 10
12 1 4 6 7 9 10
13 2 3 4 5 8 10
14 2 3 4 6 7 9
15 2 3 5 7 9 10
16 2 3 6 8 9 10
17 2 4 5 7 8 9
18 2 4 6 7 8 10
19 3 4 5 6 7 10
20 3 4 5 6 8 9
21 5 6 7 8 9 10
Brut force = Obtaining these numbers by designing my computer program
crunch every combination one after the others..
3)Any explanation, containing combination, permutation, group
mathematics
will be appreciated. Please answer this post.
Gnh888
Jasen Betts
> How do I combine all the combinations of 4s into
> the smallest combination of 6s with a range of 10 consecutive numbers?
10-4=6
each element of 6s corresponds to the numbers that aren't
in an element of 4s
> I believe there is a way of calculating what is the minimum
> combinations
> or groups to do that?
> Could someone please explain how it works and I can get a better
> result than 21?
> Because even by using brut force I don't think this is the right
> answer?
it's not, you missed some.
> 1 1 2 3 4 5 6
1 2 3 4 5 7
1 2 3 4 5 8
1 2 3 4 5 9
1 2 3 4 5 10
1 2 3 4 6 7
1 2 3 4 6 8
1 2 3 4 6 9
1 2 3 4 6 10
> 2 1 2 3 4 7 8
Bye.
Jasen
gnh...@gmail.com
>10-4=6
I don't understand what "10-4=6" refers to
> it's not, you missed some.
What do you mean I missed some?
I missed some what? ( I checked before posting)
There are 210 combinations of 4's
and there are by coincidence 210 combination of 6's
The lowest combinations of 6s which contains ALL the combination of
4s is 21 combinations of 6s in my calculation.
I said "I am not satisfied with my 21 combination of 6s, I believe
it's possible to have less than 21 combination of 6s to cover all
combinations of 4s". [ This is the reason of my posting because my
result is not the optimum- there is a better result somewhere but I
don't know how to obtain it and prove it ]
I believe the number is 19 combinations of 6s or even lower.
[technically the lowest can only be 14]
The set is 10 numbers [1 ,2,3,4,5,6,7,8,9,10].
With 10 numbers there are 210 combinations of 4s.
Each combinations of 6s can only represent a maximum of 15 combinations
of 4s
The minimum combination of 6's to represent ALL combinations of 4s is
210 /15 = 14
Have you got these 19 or 20 combination of 6s representing the 210
combinations of 4s?
because the 21 combinations of 6's I am showing is correct and does
contain all the combination of 4s..
gnh88
Chip Eastham
What you ask for is called a (10,6,4)-covering design. The smallest
possible such covering has 20 "combinations" of 6:
http://www.ccrwest.org/cover/t_pages/t4/k6/C_10_6_4.html.gz
This is a page from Dan Gordan's La Jolla Covering Repository,
which has a lot of related information on construction and best
known coverings.
regards, chip
gnh...@gmail.com
>But all I can see is this
>C(10,6,4) <=20
>Method of construction:Random Greedy Covering
> and the list below
2 3 5 6 7 8
1 3 7 8 9 10
1 2 4 6 8 9
1 2 3 4 5 10
4 5 6 7 9 10
2 3 4 6 7 10
1 3 4 5 7 9
2 3 4 8 9 10
1 2 5 7 8 10
3 5 6 8 9 10
1 2 3 6 7 9
2 4 5 7 8 9
1 3 4 5 6 8
1 2 5 6 9 10
1 4 6 7 8 10
2 3 4 5 6 9
1 5 6 7 8 9
1 2 3 6 8 10
3 4 5 7 8 10
1 2 4 7 9 10
I can see the best coverings ...
Could you please guide me a bit more, specially on
"a lot of related information on construction".
Guy(gnh888)
"
Proginoskes
I just figured out what gnh888 was asking for, but you beat me to the
answer.
--- Christopher Heckman
Jasen Betts
> There are 210 combinations of 4's
> and there are by coincidence 210 combination of 6's
It's no coincidence, 10-4=6 , each combination of 6 is
the leftovers from on of the combinations of 4
but yeah, that doesn't help you
> The lowest combinations of 6s which contains ALL the combination of
> 4s is 21 combinations of 6s in my calculation.
ok... so you've proven that 21 is sufficient.
> Each combinations of 6s can only represent a maximum of 15 combinations
> of 4s
>
> The minimum combination of 6's to represent ALL combinations of 4s is
> 210 /15 = 14
and that 14 is neccesary.
> Have you got these 19 or 20 combination of 6s representing the 210
> combinations of 4s?
> because the 21 combinations of 6's I am showing is correct and does
> contain all the combination of 4s..
now I think that because 6 is 1.5 * 4 it may be that atleast half of the groups
of 4 must be represented atleast twice in any set of groups of 6 that that includes
all possible groups of 4,
if you can prove that, then 21 is (which is 1.5*14) is both neccessary and
sufficient and you can stop looking.
Bye.
Jasen
Jasen Betts
>>10-4=6
> I don't understand what "10-4=6" refers to
>
>
> I missed some what? ( I checked before posting)
sorry, I misunderstod.
--
Bye.
Jasen
gnh...@gmail.com
Here is the set of 20 combinations of 6's which has all the combination
of 4's in it.
1 2 3 4 7 9
1 2 3 5 6 9
1 2 3 8 9 10
1 2 4 5 7 10
1 2 5 6 8 10
1 3 4 5 6 8
1 3 4 5 9 10
1 3 5 6 7 10
1 3 6 7 8 9
1 4 6 8 9 10
1 5 7 8 9 10
2 3 4 5 6 7
2 3 4 5 8 10
2 3 6 7 8 10
2 4 5 6 9 10
2 4 7 8 9 10
2 5 6 7 8 9
3 4 5 7 8 9
3 4 6 7 9 10
Is this what you want?
Thinking further I would like to be able to do this for 11, 12,
13,14 , etc ...numbers without using brut force.
What's the principle which creates these "corvering sets" for each set
of
numbers 11,12,13,14, etc..
Guy (gnh888)
Chip Eastham
Hi, Guy:
1. I see that you are posting from Google Groups, which
partly excuses not quoting the material I wrote that you
are trying (I think) to ask further questions about. Use
the Reply link that is underneath the additional options,
rather than the immediate Reply button, and Google
Groups will autoquote the message you are replying to.
2. Since you are using Google Groups, I probably don't
need to convince you that Google is your friend. Do a
search from Google's home page using terms from my
answer to your query, e.g. "covering designs". I'm sure
you will quickly spot the site I referenced as La Jolla
Covering Repository by Dan Gordan et al. Or you may
simply wish to "unwind" the URL already mentioned.
3. I thought you asked, in your original post, if there
were a collection of 6-subsets of a set of 10 items that
contains each 4-subset in at least one of the chosen
6-subsets, which involves fewer than 21 of them. So
verify that the (10,6,4)-covering design you see there
is just that, using 20 of them.
4. You came up with your own argument, based on
the fact that a 6-subset only covers fifteen 4-subsets,
that at least 14 = 210/15 of them are required. One
can produce more complicated arguments to show
that in this particular case, 20 is the minimum. You
also ask about creating similar designs for sets with
more than 10(?) elements. I think if you look around
the site mentioned above you will find information on
both topics. The general nomenclature there is a
(v,k,t)-covering design covers all t-subsets of a set
of v elements using various k-subsets of the same.
regards, chip
Patrick Hamlyn
>Jasen
>Here is the set of 20 combinations of 6's which has all the combination
>of 4's in it.
>1 2 3 4 7 9
...
>3 4 6 7 9 10
>Is this what you want?
>
>Thinking further I would like to be able to do this for 11, 12,
>13,14 , etc ...numbers without using brut force.
>
>What's the principle which creates these "corvering sets" for each set
>of
> numbers 11,12,13,14, etc..
>
>Guy (gnh888)
If you Google as suggested, you will probably find that it has been proven that
finding such coverings is NP-complete or somesuch.
In other words finding them for larger sets becomes difficult rather quickly,
and the best methods for doing so usually involve tricky directed searches
rather than pure brute force. Furthermore the directed searches involved are
generally not going to be 'simple algorithms'.
--
Patrick Hamlyn posting from Perth, Western Australia
Windsurfing capital of the Southern Hemisphere
Moderator: polyforms group (polyforms...@egroups.com)
gnh...@gmail.com
Thanks Chip
I hope I've got your instructions right regarding posting with Google.
I searched "covering designs". with Google "unwinding" the URL already
mentioned La Jolla Covering Repository by Dan Gordan et al.
As you predicted I certainly found some interest URL but found nothing
on the
covering for (45,6,4) but plenty on the covering for (49,6,4)?
Where should I search for the covering of (45,6,4) ?
Guy (gnh888)
Chip Eastham
Hi, Guy:
Yes, you have now mastered Google Groups posting!
Earlier you were asking about (10,6,4), and I was pointing
out the La Jolla Covering Repository because it has good
covering designs (v,6,4) up to v = 32. I must have missed
something because now you are asking about larger v:
> Where should I search for the covering of (45,6,4) ?
If the case v=45 is of some specific interest, perhaps
the newsgroup alt.math.recreational is a bit out of its
depth for such a topic. This design requires on the
order of 10,000 blocks.
The larger v are not necessarily more "difficult" although
we naturally expect the designs to require more blocks
for fixed k=6,t=4. I'm curious to know the application
you have in mind, since you now mention a range of v
values but leave k,t fixed.
If you are looking for a more extensive reference, I'm not
sure what to suggest. There's a published CRC Handbook
of Combinatorial Designs, but it might have only a brief
treatment of covering designs. I can ask, if that's what
you are interested in, but I'd hold off on buying a copy
if for no other reason than the 2nd edition is nearing
completion, expected this year.
If you are looking for algorithms, then I suggest you get
more deeply into the "New Constructions" paper by
Gordan et al:
http://www.ccrwest.org/cover/cover.pdf
regards, chip