Making 5-tuples out of their respective 4-tuples

Question

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?

Answer 1

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}$.