For my algorithm, is there some function that will tell me exactly when my list of 3-sets will probably have an exact-cover?

Question

Algorithm.

• Write down a set of integers and call it Universe $X$. Make sure the quantity of elements is always divisible by $3$.
• Create a list, by writing down 3-sets by random with no intentions of creating an exact cover of $X$.

An exact cover is a combination of $k$ $3sets$ that "cover" each element in $X$ without overlap. $k$ is always the length of $X$ divided by $3$.

Rules for the algorithm.

1. Do not write down 3-sets more than once. (Edit: 3-sets may be selected more than once, but duplicates must be removed in the list.)
2. Only create 3-sets that have elements in $X$
3. Sets are ordered from smallest to largest values.
4. Do not stop, use as a while loop. (Edit: Keep writing down random 3-sets.)

Question

Using the manual algorithm above for all universes of $X$, is there some function that will tell me exactly when my list of 3-sets will probably have an exact-cover?

Say $|X|$ = $3k$, how many random 3-sets do I need in the list to have > 60% probability that there is an exact cover?

Examples

Given $X$ with 3-elements, a list of 3-sets would only require one random guess.

$X$ = 1,2,3

Exact Cover {1,2,3}

As $X$ gets larger it takes more random guesses for a combination of $k$ sets to form an exact cover.

$X$ = 1,2,3,4,5,6

{1,2,5},{3,5,6},{1,3,4},{1,2,4}

Exact Cover {1,2,4},{3,5,6}

Answer 1

For $|X|=6$ there are $20\ 3-$sets. You are looking to get one of these sets and its complement. If you have chosen $k$ sets so far and not found an exact-cover, there are $k$ of the ones that are left that will give you one and $20-2k$ that will not, so the chance you will get one is $\frac k{20-k}$. After two draws you have about $0.0526$ of having a cover, after three $0.1579$, after four $0.3065$, after five $0.4799$ and after six $0.6533$. It gets harder for larger $|X|$ because there is not an easy way to say which sets you are looking for. I think I would just write a simulation and see how it comes out.

Here is an approach for larger $k$. There are ${3k \choose 3}\ 3-$sets. There are ${{3k \choose 3} \choose k}\ k-$sets of $3-$sets. There are $\frac {(3k)!}{3!^kk!}$ exact-covers. We make the assumption that when you add a $3-$set to the list each $k-$set of $3-$sets has an equal in independent probability to be an exact-cover. I don't know how to justify this, but it should not be too far wrong. We can then compute how many $3-$sets we need to have a good chance of an exact cover based on the number of $k-$sets. The chance a $k-$set is an exact cover is $\frac {\frac {(3k)!}{3!^kk!}}{{{3k \choose 3} \choose k}}$. If we have chosen $m\ 3-$sets we have ${m \choose k}\ k-$sets of $3-$ sets. We should have an exact cover about when $${m \choose k}=\frac {{{3k \choose 3} \choose k}}{\frac {(3k)!}{3!^kk!}}$$
This gives $$\begin {array} {r r r r r} k&\text{numerator}&\text{denominator}&{m \choose k}&m \\ 3&95284&280&340.3&14\\ 4&94966795&15400&6167&21\\ 5&1.589\cdot10^{11}&1401400&113432&29 \end {array}$$