Would this algorithm fail to count solutions $>$ $1$ for Exact-3-cover?


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]]$

Solutions

$ [1,2,3],[4,5,6]$

$ [4,3,2],[5,1,6]$

$ N$ = $ 2$

Yes, there are $ N$ solutions.

Algorithm

  1. Remove sets that have repeating elements

    (eg. [1,1,2] is deleted from $ C$ )

  2. Remove sets that have elements that don’t exist in $ S$

    (eg. [9,5,6] is deleted because $ 9$ not in $ S$ )

  3. Make sure all elements in $ S$ exist in $ C$ .

$ for$ a $ in$ $ range(0, length(s)):$

$ ~~~~~~~~$ $ IF$ $ s[a]$ $ not$ in $ c$ :

$ ~~~~~~~~~~~~~$ OUTPUT NO

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]$

Finally, Decide

$ n$ = $ (‘Enter~for~N:~’))$

$ yes$ = $ 0$

$ for$ a $ in$ $ range$ (0, $ length(c)):$

$ ~~~~~~$ $ if$ $ c$ .count($ c$ [a]) >= $ n$ :

$ ~~~~~~~~~~$ $ yes$ = $ 1$

$ ~~~~~~$ else:

$ ~~~~~~~~~~$ OUTPUT NO

$ ~~~~~~~~~~$ HALT

$ if$ $ yes$ == $ 1$ :

$ ~~~~$ OUTPUT YES

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

  1. There cannot be any sets with elements that don’t exist in $ S$ .

  2. There cannot be any sets with repeating elements.

  3. All elements in $ S$ must exist in $ C$ . Else, a $ no$ is given.
  4. $ N$ must be > $ 1$
  5. If any element in $ C$ occurs < $ N$ times then the output must be $ No$ , because there wouldn’t be at least $ N$ solutions.

Question

Will this algorithm always work if the input is > $ 1$ , and if no how would it fail?