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?
Sort the tuples lexicographically: always keep the items within in sorted order, so
{1,2,3,4}is okay but{1,2,4,3}is not.Similarly, sort the list of tuples lexicographically:
{1,2,4,5}should come after{1,2,3,6}should come after{1,2,3,5}.Now: Consider pairs of tuples with the same first three elements and different final element,
{a,b,c,d}and{a,b,c,e}, with $d<e$. We now need to search for{a,b,d,e},{a,c,d,e}, and{b,c,d,e}. If all three are there, then{a,b,c,d,e}is a valid 5-tuple.This works relatively quickly: since the 4-tuples are sorted lexicographically, we have a block-diagonal-matrix-like structure of 4-tuple pairs to examine, so instead of 450 million-ish pairs, we get approximately 90000 pairs that we have to search for the last three of. And that search goes quickly: once again, since they're sorted, we can find our targets by bisection.