4
$\begingroup$

Let's take integer numbers from [1..36]. We can generate 376992 different (order is not important) five-number-combinations like (1,3,5,7,12), etc. Such five-number-combinations always have five distinct (unique) numbers. Each such five-number-combination always contains 5 four-number-combinations (like (1,3,12,7), etc.). All 376992 different (unique) five-number-combinations have 58905 different (unique) four-number-combinations. All these four-number-combinations also have all (four) distinct numbers - being a subset of a set with unique numbers.

Five-number-combinations and four-number-combinations (tuple-4) always have 5 or 4 distinct (unique) numbers respectively. This is prohibited: (1,1,2,3,4) or (2,3,5,2)

Then I take at random approximately half of those 58905 different four-number-combinations - let's call them "unused 4-tuples".

Finally I need to generate all possible five-number-combinations each being such that it always consists of 5 unused four-number-combinations. That is all five four-number-combinations within such five-number-combination are from the "unused 4-tuples" set.

Direct (brute-force) algorithm is like this: I take a set of n=28000 unused 4-tuples, generate all combinations from that set by k=5 (binomial(n,k)) and then check that all five 4-tuples in such combination give exactly five numbers from [1..36] (say, I add individual numbers from every 4-tuple [out of every five 4-tuples] into a set and then check if the set contains exactly five numbers). Having checked all possible combinations (of five 4-tuples) I have solved my task.

The only problem is that binomial(30000,5) = 143368518402340005600 :)))

Could you think of some math trick to somehow sieve and shortcut that process, or maybe a tip to a more clever algorithm?

$\endgroup$
4
$\begingroup$

Go over all $\binom{36}{5}$ possible five-number combinations. For each one, calculate the five four-number combinations, and check whether all of them are unused.

In order to check whether a given four-number combination is unused, you can use a table. This will allow each such test to proceed very quickly. You can either use an array of size $36^4$ using the trivial encoding, or a slightly more sophisticated one of size $\binom{36}{4}$.

$\endgroup$

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.