0
$\begingroup$

Lets say ,I have 100 numbers(1 to 100).I have to create various combinations of 10 numbers out of these 100 numbers such that no two combinations have more than 5 numbers in common given a particular number can be used max three times. E.g.

  1. Combination 1: 1,2,3,4,5,6,7,8,9,10
  2. Combination 2: 1,2,3,4,5,11,12,13,14,15
  3. Combination 3: 1,2,3,4,5,16,17,18,19,20
  4. Combination 4: 6,7,8,9,10,11,12,13,14,15

Here Combination 1,2,3 have numbers 1 to 5 in common whereas combination 1 and 4 have numbers 6 to 10 in common. I am finding it difficult to understand how to approach this problem. What would be the starting point if I have to apply this logic on N numbers.

$\endgroup$
  • $\begingroup$ What's stopping you from just cutting the list of numbers into 10 consecutive pieces? $\endgroup$ – Contravariant Jun 12 '17 at 14:58
  • $\begingroup$ @Contravariant I didn't get you.Can you please elaborate $\endgroup$ – Himanshu Goyal Jun 13 '17 at 4:26
  • $\begingroup$ As far as I can tell you could just use the combinations "1,2,3,4,5,6,7,8,9,10" followed by "11,12,13,14,15,16,17,18,19,20" etc. etc. As far as I can tell these satisfy your requirements, so I was wondering why you didn't just do that. $\endgroup$ – Contravariant Jun 14 '17 at 11:47
0
$\begingroup$

While your question being unclear, my simplest approach is fix the five common numbers for each combination and then assign each remaining number to any combination only once. This can give you 19 different combinations.This can be implemented very quickly but the max. number of allowed combinations is very limited, namely 19. If you clarify your problem, then I should be able to give you a better answer.

$\endgroup$
  • $\begingroup$ How to decide which five numbers have to be fixed? There can be 252 ways of picking 5 numbers out of 10. $\endgroup$ – Himanshu Goyal Jun 13 '17 at 4:22
0
$\begingroup$

Too long for a comment.

It's not clear whether you want to count these combinations, or generate them.

I suspect your problem doesn't have a pretty solution in either case.

If you want to generate them I suggest an algorithm that finds the next one, keeping a list of all the ones found so far to check against for more than five matches. You can generate the next candidate randomly from a list of digits used fewer than three times.

How you implement this efficiently may depend on the computer language you're using.

Edit

Whether this is efficient or scalable enough depends on many things you haven't told us.

About how large is $N$? About how many combinations do you need? Is the cost of generating the combinations likely to be the performance bottleneck in your application? You may be asking an xy question - perhaps you need to think more about the problem you started with that led to this one.

Saving lists of useful information including combinations generated so far may well be efficient enough. You can easily keep track of how often you've used each number. Each combination of $10$ numbers from among $100$ could be represented as a $10$ digit integer in base $100$. Since $100^{10} = 10^{20} < 2^{32}$, integers will do the job easily; they can be stored so that binary search finds them. You might get useful suggestions on a site like https://cs.stackexchange.com/questions/tagged/data-structures where folks have more expertise in data structures and algorithms.

$\endgroup$
  • $\begingroup$ @Contravariant I think if the OP wants a probability of inclusion that's constant on all the possible choices the problem may be even harder. $\endgroup$ – Ethan Bolker Jun 12 '17 at 14:58
  • $\begingroup$ I want to generate these combinations.Every time while generating a combination I need to form a combination of 5 numbers and check if it is already used or not in any of the previous combinations.If not then proceed otherwise keep forming the combination of 5 numbers such that it is not used in any previous combinations.This would not be a scalable solution I believe. $\endgroup$ – Himanshu Goyal Jun 13 '17 at 4:58
  • $\begingroup$ @HimanshuGoyal See my edits. Hope they help. $\endgroup$ – Ethan Bolker Jun 13 '17 at 12:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.