Decision Problem: Given a set $S$, is there at least a given $N$ $>$ $1$ amount of solutions, for an $Exact~Cover~by~3-sets$ for $C%$?
$s$ = $1,2,3,4,5,6$
$c$ = $[[1,2,3],[4,3,2],[4,5,6],[5,1,6],[5,6,3]]$
$N$ = $2$
Yes, there are $N$ solutions.
Remove sets that have repeating elements
(eg. [1,1,2] is deleted from $C$)
Remove sets that have elements that don't exist in $S$
(eg. [9,5,6] is deleted because $9$ not in $S$)
Make sure all elements in $S$ exist in $C$.
$for$ a $in$ $range(0, length(s)):$
$~~~~~~~~$$IF$ $s[a]$ $not$ in $c$:
Convert $C$ into a complete list
$WHILE$ $c[i]$ has [brackets]:
$~~~~~~~~~~$ DELETE [BRACKETS] FROM $C$
now $c$ = $[1, 2, 3, 4, 3, 2, 4, 5, 6, 5, 1, 6, 5, 6, 3]$
$n$ = $('Enter~for~N:~'))$
$yes$ = $0$
$for$ a $in$ $range$(0, $length(c)):$
$~~~~~~$$if$ $c$.count($c$[a]) >= $n$ :
$~~~~~~~~~~$$yes$ = $1$
$if$ $yes$ == $1$ :
Edit: The above should do the same below.
yes = 0 for a in range(0, length(s)): if c.count(s[a]) >= n: yes = 1 else: OUTPUT('No') break if yes == 1: OUTPUT('yes')
Facts to consider
There cannot be any sets with elements that don't exist in $S$.
There cannot be any sets with repeating elements.
- All elements in $S$ must exist in $C$. Else, a $no$ is given.
- $N$ must be > $1$
- If any element in $C$ occurs < $N$ times then the output must be $No$, because there wouldn't be at least $N$ solutions.
Will this algorithm always work if the input is > $1$, and if no how would it fail?