Werfen wir einen Satz von ganzen Zahlen nehmen mehr als 1 und nennen es X . Wir definieren S (i) als die Menge aller durch i teilbaren Elemente von X, wobei i> 1 ist . Möchte aus diesen Teilmengen eine Gruppe von Mengen auswählen, so dass

• Ihre Vereinigung ist die Menge X

• Kein Element von X befindet sich in zwei der Mengen.

Zum Beispiel können wir uns neu gruppieren {3..11}als

      {3,4,5,6,7,8,9,10,11}
S(3): {3,    6,    9,     }
S(4): {  4,      8,       }
S(5): {    5,        10,  }
S(7): {        7,         }
S(11):{                 11}

Einige Mengen können nicht auf diese Weise ausgedrückt werden. Zum Beispiel, wenn wir nehmen {3..12}, 12ist ein Vielfaches von 3 und 4, was verhindert, dass sich unsere Mengen gegenseitig ausschließen.

Einige Mengen können auf mehrere Arten ausgedrückt werden, zum Beispiel {4..8}als

      {4,5,6,7,8}
S(4): {4,      8}
S(5): {  5,     }
S(6): {    6,   }
S(7): {      7, }

es kann aber auch dargestellt werden als

      {4,5,6,7,8}
S(2): {4,  6,  8}
S(5): {  5,     }
S(7): {      7, }

Aufgabe

Unser Ziel ist es, ein Programm zu schreiben, das eine Menge als Eingabe verwendet und die kleinste Anzahl von Teilmengen ausgibt, die diese auf diese Weise abdecken. Wenn es keine gibt, sollten Sie einen anderen Wert als eine positive Ganzzahl ausgeben (zum Beispiel 0).

Dies ist eine Code-Golf- Frage, daher werden die Antworten in Bytes bewertet, wobei weniger Bytes besser sind.

Tests

{3..11}       -> 5
{4..8}        -> 3
{22,24,26,30} -> 1
{5}           -> 1

Python 2 , 167 Bytes

lambda a:([q for q in range(a[-1])if a in[sorted(sum(j,[]))for j in combinations([[p for p in a if p%i<1]for i in range(2,1+a[-1])],q)]]+[0])[0]
from itertools import*

Probieren Sie es online!

-9 Bytes dank Zacharý
-4 Bytes dank Mr. Xcoder
-2 Bytes durch Verwenden von Listen anstelle von Mengen
-5 Bytes durch Verwenden von a in [...]anstatt any([a == ...]).
-2 Bytes dank Mr. Xcoder
-8 Bytes durch Zusammenführen von Anweisungen
-5 Bytes dank Mr. Xcoder
-7 Bytes dank Mr. Xcoder / Zacharý
+7 Bytes zur Behebung des Fehlers
-1 Bytes dank Ovs

Hinweis

Dies ist für größere maximale Zahlen extrem langsam, da es in keiner Weise optimiert ist. es hat nicht innerhalb von 2 minuten auf herrn xcoders gerät für [22, 24, 26, 30].

Clingo , 51 Bytes

{s(2..X)}:-x(X).:-x(X),{s(I):X\I=0}!=1.:~s(I).[1,I]

Demo

$ echo 'x(3..11).' | clingo cover.lp -
clingo version 5.1.0
Reading from cover.lp ...
Solving...
Answer: 1
x(3) x(4) x(5) x(6) x(7) x(8) x(9) x(10) x(11) s(3) s(4) s(5) s(7) s(11)
Optimization: 5
OPTIMUM FOUND

Models       : 1
  Optimum    : yes
Optimization : 5
Calls        : 1
Time         : 0.003s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)
CPU Time     : 0.010s
$ echo 'x(4..8).' | clingo cover.lp -
clingo version 5.1.0
Reading from cover.lp ...
Solving...
Answer: 1
x(4) x(5) x(6) x(7) x(8) s(3) s(4) s(5) s(7)
Optimization: 4
Answer: 2
x(4) x(5) x(6) x(7) x(8) s(2) s(5) s(7)
Optimization: 3
OPTIMUM FOUND

Models       : 2
  Optimum    : yes
Optimization : 3
Calls        : 1
Time         : 0.001s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)
CPU Time     : 0.000s
$ echo 'x(22;24;26;30).' | clingo cover.lp -
clingo version 5.1.0
Reading from cover.lp ...
Solving...
Answer: 1
x(22) x(24) x(26) x(30) s(5) s(8) s(22) s(26)
Optimization: 4
Answer: 2
x(22) x(24) x(26) x(30) s(3) s(22) s(26)
Optimization: 3
Answer: 3
x(22) x(24) x(26) x(30) s(2)
Optimization: 1
OPTIMUM FOUND

Models       : 3
  Optimum    : yes
Optimization : 1
Calls        : 1
Time         : 0.004s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)
CPU Time     : 0.000s
$ echo 'x(5).' | clingo cover.lp -
clingo version 5.1.0
Reading from cover.lp ...
Solving...
Answer: 1
x(5) s(5)
Optimization: 1
OPTIMUM FOUND

Models       : 1
  Optimum    : yes
Optimization : 1
Calls        : 1
Time         : 0.001s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)
CPU Time     : 0.000s

Mathematica, 105 Bytes

Length@Select[Subsets@Table[Select[s,Mod[#,i]==0&],{i,2,Max[s=#]}],Sort@Flatten@#==Sort@s&][[1]]~Check~0&

Probieren Sie es online aus,
kopieren Sie den Code und fügen Sie ihn mit Strg + V ein,
fügen Sie die Eingabe am Ende des Codes ein,drücken Siedie
Umschalttaste und die Eingabetaste, um ihn auszuführen

Eingang

[{3,4,5,6,7,8,9,10,11}]

Nimmt eine Liste als Eingangsausgang
0, wenn keine vorhanden sind

Haskell, 136 Bytes

import Data.List
f l|m<-maximum l=(sort[n|(n,c)<-[(length s,[i|j<-s,i<-[j,2*j..m],elem i l])|s<-subsequences[2..m]],c\\l==l\\c]++[0])!!0

Probieren Sie es online!

Wie es funktioniert

f l     =                           -- input set is l
   |m<-maximum l                    -- bind m to maximum of l
       [   |s<-subsequences[2..m]]  -- for all subsequences s of [2..m]
        (length s, )                -- make a pair where the first element is the length of s
            [i|j<-s,i<-[j,2*j..m],elem i l]
                                    -- and the second element all multiples of the numbers of s that are also in l
     [n|(n,c)<-       ,c\\l==l\\c]  -- for all such pairs (n,c), keep the n when c has the same elements as l, i.e. each element exactly once
   sort[ ]++[0]                     -- sort those n and append a 0 (if there's no match, the list of n is empty)
 (     )!!0                         -- pick the first element

Nehmen Sie viel Zeit für {22,24,26,30}.

Jelly, 38 35 34 33 31 28 25 24 23 20 19 Bytes

ṀḊŒPð%þ@⁹¬Sḟ1ðÐḟL€Ḣ

-5 Bytes dank Leaky Nun

Probieren Sie es online!

Ich denke, der dritte Testfall funktioniert, ist aber sehr langsam. 0wird ausgegeben, wenn keine Lösungen vorliegen.

Erklärung (könnte diese Erklärung falsch verstanden haben):

ṀḊŒPð%þ@⁹¬Sḟ1ðÐḟL€Ḣ     (input z)
ṀḊ                      - 2 .. max(z)
  ŒP                    - powerset
    ð                   - new dyadic chain
     %þ@⁹               - modulo table of z and that
         ¬              - logical not
          S             - sum
           ḟ1           - filter out 1's
             ðÐḟ        - filter out elements that satisfy that condition
                L€      - length of each element
                  Ḣ     - first element

Julia, 91 Bytes

x->(t=[];for i in x z=findfirst(x->x==0,i%(2:maximum(x)));z∈t?1:push!(t,z) end;length(t))