1
$\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$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ --actually, though I haven't tried it, you might get even better results by performing a grouping operation: put each item into a bin based on its first three elements. $\endgroup$ – Dan Uznanski Jul 23 '18 at 11:59

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.