Re: Algorithm to group all subsets [a,b,c,d] in a set of 10 nmbrs[1..10] into the least of number of subsets[a,b,c,d,e,f] without repetition of numbers in each sets ?My result is 20 subsets[a,b,c,d,e,f] . I need more speed + elegance?
Keith A. Lewis
>Algorithm to group all subsets [a,b,c,d] in a set of 10 nmbrs[1..10]
>into the LEAST number of subsets[a,b,c,d,e,f] without repetition? My
>result is 20 subsets[a,b,c,d,e,f] . I need more speed + elegance?
>
>The set of 10 numbers are { 1,...,10}.
>
>There are 210 subsets of 4 numbers [a,b,c,d] in this set of 10 numbers
>
>I want to find the lowest number of subsets of 6 numbers
>[a,b,c,d,e,f,g] which
>will contain all the subset of 4's[a,b,c,d]
>
>20 is the minimum number of subsets of 6 numbers [a,b,c,d,e,f,g] which
>will contain all the subset of 4's[a,b,c,d] _ see below what my result
>is?
Each set of 6 has 15 different subsets of 4, so to generate all 210 you will
need at least 14 sets of 6.
There are 120 sets of 3. Each of these subsets must appear in groups with
all 7 other numbers, which means each set of 3 must be in at least 3 groups.
The groups themselves each contain 20 subsets of size 3, so that raises the
lower limit to 120*3/20=18.
What do you mean by "without repetition"? If you have more than 14 groups,
you must have a repeated set of 4 somewhere. In your example below,
[1,2,3,9] occurs in all of the first 3 lines.
>What is the"elegant" process (opposed to brut force) to find the
>minimum number of subsets of 6 numbers [a,b,c,d,e,f,g] ??
Without loss of generality you can fix the first group to be [1,2,3,4,5,6].
Then notice that you need [1,2,3] to be in the same group with each of
[7,8,9,10]. You can't do it in just one group; you need at least 2. Now
there's a decision point. You can do [1,2,3,7,8,9] and try to get as many
[1,2,3]'s as possible into 1 group or [1,2,3,4,7,8] and [1,2,3,5,9,10].
Elegance is falling apart.
>I am talking here about an algorithmic process which can be used in
>Basic, C, C++, Java etc programming.
>{the set of numbers are similar to the lotto , meaning NO repetition of
>sets like [ 1,2,3,4] and [2,4,1,3] in the result}
>
>
>1) How does the algorithm works to find the minimum of number o subsets
>of 6 numbers [a,b,c,d,e,f,g] ??
Let's say you have n elements, and you want m groups of them such that each
combination of k is in at least one group.
For any i<=k, you need each C(n,i) to be in the same group with each of
C(n-i,k-i) "completion" sets. Each group of m contains C(m,i) sets of size
i and for each of those, C(m-i,k-i) completion sets.
So each set of i must appear at least ceil(C(n-i,k-i)/C(m-i,k-i)) times in
order to be completed in all possible ways. That establishes a lower bound
for the number of groups at C(n,i)/C(m,i)*ceil(C(n-i,k-i)/C(m-i,k-i)).
It might be possible to simplify this expression.
In this example n=10, m=6, and k=4. Loop for i = 0 to 4 and calculate.
C(10,0)/C(6,0)*ceil(C(10,4)/C(6,4))=14
C(10,1)/C(6,1)*ceil(C(9,3)/C(5,3))=15
C(10,2)/C(6,2)*ceil(C(8,2)/C(4,2))=15
C(10,3)/C(6,3)*ceil(C(7,1)/C(3,1))=18
C(10,4)/C(6,4)*ceil(C(6,0)/C(2,0))=14
Keep the highest, 18 in this case. There's no guarantee that there's a
solution of that size, but you definitely won't find a smaller one.
>
>2) Is it possible to use matrices to resolve this problem? and how?
>==
>
>Combinations of 4's or set of 4's
> [1 2 3 5], [1 2 3 5], [ 1 2 3 6], ....,[6 7 9 10], [6
>8 9 10], [7 8 9 10]
>(please - no permutations)
>
>Combinations of 6's or set of 6's
>[1 2 3 4 5 6], [1 2 3 4 6 7],....,[5 6 7 8 9 10]
>
>Expected result below of 20 sets of 6's or bettor better than below (
>better means less than 20 sets of 6's)
>[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 4 6 7 8]
>[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]
>
--Keith Lewis klewis {at} mitre.org
The above may not (yet) represent the opinions of my employer.
James Waldby
> Algorithm to group all subsets [a,b,c,d] in a set of
> 10 nmbrs[1..10] into the LEAST number of subsets
> [a,b,c,d,e,f] without repetition?
> There are 210 subsets of 4 numbers [a,b,c,d] in this set of 10 numbers
> What is the"elegant" process (opposed to brut force) to find
> the minimum number of subsets of 6 numbers [a,b,c,d,e,f,g] ??
>
> I am talking here about an algorithmic process which can
> be used in Basic, C, C++, Java etc programming.
The set-covering problem is NP-complete [1] so you may
have trouble finding a fast solution, although several
reasonably elegant methods exist. (See eg
http://en.wikipedia.org/wiki/Quine-McCluskey_algorithm ).
Why do you want a solution anyway? What will you do
with it?
-jiw
[1] Let E be the set {q1, q2 ... q210} consisting of the
210 4-tuples over 10 elements, and let S be the set {S0,
S1, ... S209} consisting of the 210 15-member subsets of E
that correspond to the 210 6-tuples over those same 10
elements. You want to pick a minimum number of Si to cover
the 210 items q1...q210. This is an instance of the
NP-complete set cover problem, as described (for example)
at http://en.wikipedia.org/wiki/Set_cover_problem
James Waldby
...
> Without loss of generality you can fix the first group to be [1,2,3,4,5,6].
> Then notice that you need [1,2,3] to be in the same group with each of
> [7,8,9,10]. You can't do it in just one group; you need at least 2. Now
> there's a decision point. You can do [1,2,3,7,8,9] and try to get as many
> [1,2,3]'s as possible into 1 group or [1,2,3,4,7,8] and [1,2,3,5,9,10].
> Elegance is falling apart.
Perhaps slightly better to reason as follows: Let Ci =
ith hex [6-tuple over base elements 1...9,0] of cover.
Wolog, take C0 = 1,2,3,4,5,6. We must have a hex to
cover 7,8,9,0. It will be of form a,b,7,8,9,0, where
a,b are some two of the undistinguished elements
{1,2,3,4,5,6}. Wolog, take a=1, b=2; that is,
C1 = 1,2,7,8,9,0.
Now our sets of undistinguished elements are P={1,2},
Q={3,4,5,6}, and R={7,8,9,0}. There must be a hex to cover
the quad 3,4,5,7 (or equivalently, 3,7,8,9) and that hex
can have content 3457pp', 3457pq, 3457qr, or 3457rr'.
So wolog we can limit C2 to one of the following:
1,2,3,4,5,7; 1,3,4,5,6,7; 3,4,5,6,7,8; 3,4,5,7,8,9.
Using 1,3,7,8, (or equivalently, 1,3,4,7) where I used
3,4,5,7 would give a five-way branch from forms 1378pq,
1378pr, 1378qq', 1378qr, 1378rr'. Using 3,4,7,8 leads to
a 6-way branch with forms ending in pp', pq, pr, qq', qr,
and rr'.
For C3, typically two pairs of base elements remain
undistinguished, from which a small amount of case
reduction is possible.
-jiw
PS: Note to OP -- Use shorter subject lines!
Keith A. Lewis
>The solution , how do you see the big picture to start looking.
>I have a looked at a few websites
>http://www.cs.sunysb.edu/~algorith/files/set-cover.shtml
As James Waldby pointed out, your problem is a special case of the general
"set cover" problem. That algorithm is the most applicable.
>Which direction do you think I should take?
Start with a good set cover algorithm, starting with James Waldby's first 2
"without loss of generality" sets [1,2,3,4,5,6] and [1,2,7,8,9,10] and add
pruning. This instance of the problem is easier than the general case
because all available covering sets are the same size and symetric
configuration.
One pruning idea: You can always order the groups such that after the jth
group of N, a proportion of at least j/N is covered (i.e. you never fall
begind and then catch up). This holds for the 2 starter groups above; in
fact they are maximally disjoint so they produce the highest possible
coverage for 2 groups.
In fact, at any point, if there are j groups left to choose and B
combinations left to cover, you should only consider groups that cover at
least j/B additional combinations. This is probably easy at the beginning
and harder near the end, but it can give you an early warning before you
start to explore a dead-end branch.
>In my previous experience, it's called a lot of ideas to exchange with
>others until it clicks, long hours at night and plenty of programming