Overlapping combinations problem
 

Hi all,

Given some parameters N,k,t,B where N=k=t and B1
- 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 a
Combinations appearing once =10
twice =288
3 times=190
4 times=7

How can we count the above faster that brute force?

TIA

Overlapping combinations problem
 

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.

--
Regards,
Tom Ogilvy





Dizzy wrote in message
le.rogers.com...
Hi all,

Given some parameters N,k,t,B where N=k=t and B1
- 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 a
Combinations appearing once =10
twice =288
3 times=190
4 times=7

How can we count the above faster that brute force?

TIA

Overlapping combinations problem
 

Tom Ogilvy wrote:
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.

--
Regards,
Tom Ogilvy



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,





Dizzy wrote in message
le.rogers.com...

Hi all,

Given some parameters N,k,t,B where N=k=t and B1
- 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 a
Combinations appearing once =10
twice =288
3 times=190
4 times=7

How can we count the above faster that brute force?

TIA