A counting 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 than brute force?

TIA
 
Explain what you mean by "brute force".

If you mean can it be done without actuallly producing the random
combinations then probably the answer is no. The problem as stated is
not a *probability* question, so a general approach using probability
theory is not applicable.

Presumably the only scope for non-brute force is in the
post-generation stage of the problem.

I'm also not sure what you mean by "overlapping" combinations. You
might explain further there....

Tim.
 
Back
Top