Overlapping combinations problem

  • Thread starter Thread starter Dizzy
  • Start date Start date
D

Dizzy

Hi all,

Given some parameters N,k,t,B where N>=k>=t and B>1
- Generate B random combinations from 1 to N of size k
- Calculate the unique and overlapping combinations of size t
that belong to the B combinations.

Ex:
N=12 k=4 t=3 B=7

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

My results are:
Combinations appearing once =10
twice =288
3 times=190
4 times=7

How can we count the above faster that brute force?

TIA
 
Are you generating all combinations of size 3 from each of the 7 four digit
combinations. Or are you generating 3 digit combinations from the pool of 7
* 4 = 28 numbers? It is unclear to me what you are actually doing to get
your results.
 
Tom said:
Are you generating all combinations of size 3 from each of the 7 four digit
combinations. Or are you generating 3 digit combinations from the pool of 7
* 4 = 28 numbers? It is unclear to me what you are actually doing to get
your results.
Click to expand...

Hi Tom,

We generate all the combinations of c(N,k)=495
Then we compare every combination above, with the given B=7.
If that combination intersects any of the given 7 in at least t=3
elements then we have a match.
If one other of the 7 given also intersects that combination in at least
t points then than combination overlaps and appears twice.
That is how my list was generated.


Example:
The first combination we compare is
{1,2,3,4}
From the given 7, the 6th intersects the above in 3 elements {1,2,3}
So this one appears only once in our collection of sets.

The second is {1,2,3,5}
This one intersects the 1st & 6th set in 3 points so this one appears twice.
..
..
..
{1,3,6,10}
This one intersects the 2nd ,3rd & 6th so it appears 3 times
and so on.

But counting with brute force is very inefficient
when N and k is increasing.
I imagine that shall be some other way of doing this mathematically.
Like counting the overlapping N-tuplets of the given sets.
If you can imagine of any other way that this can be done faster I'll
appreciate your input.

I have prepared a worksheet that can do this by brute force.
If you wish to see it I'll post it.

Thanks again for your input.

Dizzy,
 
Back
Top