# How to generate all sets of 3 elements within sets of 5, drawn from 45 possibles?
**URL:** https://boards.straightdope.com/t/how-to-generate-all-sets-of-3-elements-within-sets-of-5-drawn-from-45-possibles/481027
**Category:** Factual Questions
**Created:** [January 13, 2009, 3:00am UTC](https://boards.straightdope.com/t/how-to-generate-all-sets-of-3-elements-within-sets-of-5-drawn-from-45-possibles/481027 "2009-01-13T03:00:40Z")
**Posts on this page:** 10
**Page:** 1
### Author:  [@jharvey963](https://boards.straightdope.com/u/jharvey963)
#### Post date: [January 13, 2009, 3:00am UTC](https://boards.straightdope.com/t/how-to-generate-all-sets-of-3-elements-within-sets-of-5-drawn-from-45-possibles/481027/1 "2009-01-13T03:00:40Z")
Assume your domain is the integers from 1 through 45. Your task is to create groups of 5 numbers at a time, such that all groups of 3 (unordered) numbers are represented within some group of five.
One group of 5 numbers is chosen without replacement from the 45 possibles. The next group of 5 is also chosen without replacement from the full 45 numbers. So there are no duplicate numbers WITHIN one group of 5, but duplicates are allowed in different groups of 5.
For example, let’s take the group of 5 numbers: 1, 2, 3, 4, 5.
This group of 5 contains the following groups of 3 numbers:
1 2 3; 1 2 4; 1 2 5; 1 3 4; 1 3 5; 1 4 5
2 3 4; 2 3 5; 2 4 5; 3 4 5;
The number of groups of 3 within a group of 5 is “5 choose 3”, or (5!) / ((3!) \* (2!)) = 10
So my questions are:
- What is the minimum number of groups of 5 needed to encompass all possible groups of 3 numbers from the numbers 1 - 45? And how is this number calculated?
- How do you then generate all these groups of 5 numbers? What algorithm do you use?
- How do you generalize this result to, say, all groups of 2 or 4 numbers?
Thanks,
J.
p.s., no, this isn’t a homework problem. It’s just something I’m trying to figure out for myself. And unfortunately, my statistics knowledge has been lost in long term storage. 🙂
---
### Author:  [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)
#### Post date: [January 13, 2009, 3:13am UTC](https://boards.straightdope.com/t/how-to-generate-all-sets-of-3-elements-within-sets-of-5-drawn-from-45-possibles/481027/2 "2009-01-13T03:13:03Z")
Start by generating the appropriate [De Bruijn sequence](http://en.wikipedia.org/wiki/De_Bruijn_sequence). Construct groups of five by taking the first through fifth elements, the second through sixth elements, etc. until you’ve exhausted the sequence. I’m not claiming that this is the minimal set of groups of five elements, but it should work.
---
### Author:  [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)
#### Post date: [January 13, 2009, 3:17am UTC](https://boards.straightdope.com/t/how-to-generate-all-sets-of-3-elements-within-sets-of-5-drawn-from-45-possibles/481027/3 "2009-01-13T03:17:27Z")
I don’t think I understand your setup. You say you choose the groups of 5 “without replacement” from the total 45, yet every possible group of 3 should be contained within one of these groups of 5? How could that possibly work? Surely, some of these groups of 5 will have to overlap, no?
ETA: Nevermind, I read more carefully. No duplicates within a group, but duplicates allowed “between” groups. Sorry, I should’ve seen it; you were quite explicit.
---
### Author:  [@MikeS](https://boards.straightdope.com/u/MikeS)
#### Post date: [January 13, 2009, 3:20pm UTC](https://boards.straightdope.com/t/how-to-generate-all-sets-of-3-elements-within-sets-of-5-drawn-from-45-possibles/481027/4 "2009-01-13T15:20:06Z")
If you’re only trying to ensure that all possible pairs appear at least once in a subset, rather than all triplets, this called a [block design](http://en.wikipedia.org/wiki/Block_design) in combinatorics. Specifically, you want a “balanced incomplete block design” of type (b, 45, r, 5, lambda). If you look at the equations near the top of the Wiki page, you’ll see that you end up with r = 11\*lambda and b = 9r; this means that the smallest block design must have 99 subsets.
Further down in the wiki article, there’s a bit about the generalization to t-designs; your original problem is a 3-design with (v,k,lambda) = (45,5,lambda). If such a design exists for lambda = 1, and I’m interpreting those equations correctly, it has to have b[sub]0[/sub] = 1419 sets in it.
The actual construction of such a design is another question, though. I’ll ponder it a little more during the day today if I have time, but hopefully I’ve given you something to get the ball rolling if you want to research this further.
---
### Author:  [@jharvey963](https://boards.straightdope.com/u/jharvey963)
#### Post date: [January 13, 2009, 3:36pm UTC](https://boards.straightdope.com/t/how-to-generate-all-sets-of-3-elements-within-sets-of-5-drawn-from-45-possibles/481027/5 "2009-01-13T15:36:16Z")
> [@MikeS](#):
>
> If you’re only trying to ensure that all possible pairs . . . If you look at the equations near the top of the Wiki page, you’ll see that you end up with r = 11\*lambda and b = 9r; this means that the smallest block design must have 99 subsets.
>
> Further down in the wiki article, there’s a bit about the generalization to t-designs; your original problem is a 3-design with (v,k,lambda) = (45,5,lambda). If such a design exists for lambda = 1, and I’m interpreting those equations correctly, it has to have b[sub]0[/sub] = 1419 sets in it.
>
> . . .
Interesting numbers - 99 and 1419. Remember that I showed 1 set of 5 held 10 combinations of 3? It also holds 10 combinations of 2.
45 choose 3 = 14190. Divide this by 10 combinations per group of 5 = 1419
45 choose 2 = 990. Divide this by 10 combinations per group of 5 = 99
J.
---
### Author:  [@Omphaloskeptic](https://boards.straightdope.com/u/Omphaloskeptic)
#### Post date: [January 13, 2009, 6:47pm UTC](https://boards.straightdope.com/t/how-to-generate-all-sets-of-3-elements-within-sets-of-5-drawn-from-45-possibles/481027/6 "2009-01-13T18:47:41Z")
The block-design inequalities provide lower bounds, but these are not always achievable. It’s not too hard to show that they can’t be satisfied in this case: a 1419-set solution doesn’t exist. The bound of 1419 assumes that each subset of three elements occurs in exactly one 5-element subset (= “block”), so we just have to show that some 3-subsets must occur in more than one block.
There are 43 distinct subsets of three elements where two of the elements (call them x and y) are given. Each block containing both x and y contains three other elements, so it provides exactly three of these 3-subsets. So the number of such subsets generated by any list of blocks is divisible by 3. Since 43, the number of distinct 3-subsets containing x and y, is not divisible by 3, at least one of these 3-subsets must be repeated.
Clearly then we need at least 15 blocks containing x and y, giving 45 3-subsets (with two repeats). This improves the lower bound (45 choose 3)/(5 choose 3)=1419 to 1419\*45/43=1485. I don’t know if this bound is achievable either, though.
---
### Author:  [@MikeS](https://boards.straightdope.com/u/MikeS)
#### Post date: [January 13, 2009, 7:08pm UTC](https://boards.straightdope.com/t/how-to-generate-all-sets-of-3-elements-within-sets-of-5-drawn-from-45-possibles/481027/7 "2009-01-13T19:08:48Z")
> [@Omphaloskeptic](#):
>
> Clearly then we need at least 15 blocks containing x and y, giving 45 3-subsets (with two repeats). This improves the lower bound (45 choose 3)/(5 choose 3)=1419 to 1419\*45/43=1485. I don’t know if this bound is achievable either, though.
This, of course, means that you’ll have what’s called a “covering design” — specifically, a design where all subsets of a given size occur _at least_ lambda times, rather than _exactly_ lambda times. Believe it or not, there’s a [catalog of these](http://www.ccrwest.org/cover.html) available online, complete with [a size-1617 covering design](http://www.ccrwest.org/cover/t_pages/t3/k5/C_45_5_3.html) for t = 3, k = 5, v = 45.
---
### Author:  [@jharvey963](https://boards.straightdope.com/u/jharvey963)
#### Post date: [January 13, 2009, 7:18pm UTC](https://boards.straightdope.com/t/how-to-generate-all-sets-of-3-elements-within-sets-of-5-drawn-from-45-possibles/481027/8 "2009-01-13T19:18:31Z")
> [@MikeS](#):
>
> This, of course, means that you’ll have what’s called a “covering design” — specifically, a design where all subsets of a given size occur _at least_ lambda times, rather than _exactly_ lambda times. Believe it or not, there’s a [catalog of these](http://www.ccrwest.org/cover.html) available online, complete with [a size-1617 covering design](http://www.ccrwest.org/cover/t_pages/t3/k5/C_45_5_3.html) for t = 3, k = 5, v = 45.
THIS is why I love the dope. The breadth and depth of knowledge here is amazing.
J.
---
### Author:  [@jharvey963](https://boards.straightdope.com/u/jharvey963)
#### Post date: [January 13, 2009, 10:11pm UTC](https://boards.straightdope.com/t/how-to-generate-all-sets-of-3-elements-within-sets-of-5-drawn-from-45-possibles/481027/9 "2009-01-13T22:11:18Z")
> [@ultrafilter](#):
>
> Start by generating the appropriate [De Bruijn sequence](http://en.wikipedia.org/wiki/De_Bruijn_sequence). Construct groups of five by taking the first through fifth elements, the second through sixth elements, etc. until you’ve exhausted the sequence. I’m not claiming that this is the minimal set of groups of five elements, but it should work.
Now that I’ve had a chance to look at this, no, this isn’t what I’m looking for. The De Bruijn sequence is meant for ordered sequences, whereas my problem deals with unordered groups. (For me, 1 2 and 2 1 are the same group, whereas they are 2 different sequences in De Bruijn.)
Thanks, though.
J.
---
### Author:  [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)
#### Post date: [January 13, 2009, 10:12pm UTC](https://boards.straightdope.com/t/how-to-generate-all-sets-of-3-elements-within-sets-of-5-drawn-from-45-possibles/481027/10 "2009-01-13T22:12:03Z")
Well, as **ultrafilter** said, his method will work; it just won’t be minimal.