Decken Sie ein Set mit Vielfachen ab

14

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 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
Post Rock Garf Hunter
quelle
Wenn es keine gibt, sollten Sie einen anderen Wert als eine positive Ganzzahl ausgeben (zum Beispiel 0). Kann unser Programm stattdessen nicht zu undefiniertem Verhalten führen?
Mr. Xcoder
Können Sie auch einen Testfall wie hinzufügen [5..5]? Können wir Dinge wie erhalten [8..4]?
Mr. Xcoder
@ Mr.Xcoder Nein darf es nicht. Programme sollten in der Lage sein, unmögliche Fälle zu identifizieren, nicht nur für immer zu schleifen oder darauf abzustürzen.
Post Rock Garf Hunter
1
" 12Ist ein Vielfaches von beidem 3und 4verhindert, dass sich unsere Sets gegenseitig ausschließen ": warum? Ich sehe in der Problemstellung nichts anderes, was es erfordert 12, in beide Teilmengen zu gehen.
Peter Taylor
1
Und was ist mit den Testfällen? [22,24,26,30]sind alle ein Vielfaches von 2. Sind Sie sicher, dass es nicht besser wäre, dies zu löschen und es mit einer Sandbox zu versehen?
Peter Taylor

Antworten:

6

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

HyperNeutrino
quelle
5

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
Anders Kaseorg
quelle
Dies scheint Fälle ohne Lösungen wie x(3..12).(oder muss ich updaten?) Nicht zu erkennen . Übrigens, können Sie eine gute Einführung in Clingo vorschlagen?
Christian Sievers
1
@ChristianSievers Ups, das war ein Fehler, den ich jetzt behoben habe. Es sollte UNSATISFIABLEin einem solchen Fall ausgegeben werden. Ich habe meistens den Potassco-Führer benutzt .
Anders Kaseorg
4

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

J42161217
quelle
Gute Verwendung vonCheck
Keyu Gan
Warum haben Sie Ihre erste Antwort nicht wiederhergestellt, nachdem Sie eine funktionierende Version hatten?
Neil
Weil dies ein völlig neuer Ansatz war? Gibt es ein Problem?
J42161217
4

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}.

nimi
quelle
3

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
Zacharý
quelle
1
18 Bytes
Undichte Nonne
Vielen Dank! Und danke, dass Sie das nicht selbst eingereicht haben!
Zacharý
Ich habe eine andere 18-Byte-Lösung, die näher an meinem Original liegt. Ich persönlich ṀḊŒPðḍ@þ@⁹Sḟ1ðÐḟḢL
finde
Woah ... ṀḊeigentlich ist das ein cooler Trick!
Zacharý
Hoppla, das funktioniert nicht und mein Umschreiben auch nicht! Dies sollte 0 ausgeben, nicht 1
Zacharý
2

Julia, 91 Bytes

x->(t=[];for i in x z=findfirst(x->x==0,i%(2:maximum(x)));zt?1:push!(t,z) end;length(t))
Tanj
quelle
Ähm ... hast du vergessen, einen Link in den Namen der Sprache aufzunehmen, oder heißt er tatsächlich "[Julia]"?
Zacharý
Sie haben recht, der Name ist Julia ohne Klammern
Tanj
Vielleicht möchten Sie das auch bei Ihren anderen Antworten korrigieren!
Zacharý
Wow, das waren viele Antworten! Und wenn Sie einen Link einfügen möchten, lautet die Syntax[Text to display](link to website)
Zacharý