Przykryj zestaw wielokrotnościami

14

Weźmy zbiór liczb większych niż 1 i nazwać X . Zdefiniujemy S (i) jako zbiór wszystkich elementów X podzielnych przez i, gdzie i> 1 . Chciałbym wybrać z tych podzbiorów grupę takich zestawów

  • Ich związek jest zbiorem X

  • Żaden element X nie znajduje się w dwóch zestawach.

Na przykład możemy przegrupować {3..11}jako

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

Niektórych zestawów nie można wyrazić w ten sposób. Na przykład, jeśli weźmiemy {3..12}, 12jest wielokrotnością zarówno 3, jak i 4, co zapobiega wzajemnemu wykluczaniu się naszych zestawów.

Niektóre zestawy można na przykład wyrazić na wiele sposobów {4..8} można je przedstawić jako

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

ale można to również przedstawić jako

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

Zadanie

Naszym celem jest napisanie programu, który pobierze zestaw jako dane wejściowe i wyprowadzi najmniejszą liczbę podzbiorów, które pokrywają go w ten sposób. Jeśli nie ma, powinieneś podać jakąś wartość inną niż dodatnia liczba całkowita (na przykład0 ).

To jest pytanie w więc odpowiedzi będą oceniane w bajtach, przy czym mniej bajtów jest lepszych.

Testy

{3..11}       -> 5
{4..8}        -> 3
{22,24,26,30} -> 1
{5}           -> 1
Post Rock Garf Hunter
źródło
Jeśli nie ma, powinieneś podać wartość inną niż dodatnia liczba całkowita (na przykład 0). Czy nasz program nie może zamiast tego spowodować niezdefiniowanego zachowania?
Pan Xcoder,
Czy możesz również dodać przypadek testowy [5..5]? Czy możemy otrzymać takie rzeczy [8..4]?
Pan Xcoder,
@ Mr.Xcoder Nie, może nie. Programy powinny być w stanie identyfikować niemożliwe przypadki, nie tylko zapętlając je na zawsze lub zawieszając się na nich.
Post Rock Garf Hunter
1
12jest wielokrotnością obu 3i 4zapobiega wzajemnemu wykluczaniu się naszych zbiorów ”: dlaczego? W opisie problemu nie widzę nic innego, co wymagałoby 12przejścia do obu podzbiorów.
Peter Taylor
1
A co z przypadkami testowymi? [22,24,26,30]są wielokrotnościami 2. Czy jesteś pewien, że nie byłoby lepiej, aby usunąć to i piaskownicy?
Peter Taylor

Odpowiedzi:

6

Python 2 , 167 bajtów

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*

Wypróbuj online!

-9 bajtów dzięki Zacharýowi
-4 bajty dzięki Mr. Xcoder
-2 bajtów za pomocą list zamiast zestawów
-5 bajtów za pomocą a in [...]zamiast any([a == ...]).
-2 bajty dzięki Mr. Xcoder
-8 bajtów poprzez połączenie instrukcji
-5 bajtów dzięki Mr. Xcoder
-7 bajtów dzięki Mr. Xcoder / Zacharý
+7 bajtów do naprawy błędu
-1 bajt dzięki ovs

Uwaga

Jest to bardzo wolne w przypadku większych liczb maksymalnych, ponieważ nie jest w żaden sposób zoptymalizowane; dla urządzenia pana Xcodera nie nastąpiło to w ciągu 2 minut [22, 24, 26, 30].

HyperNeutrino
źródło
5

Clingo , 51 bajtów

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

Próbny

$ 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
źródło
Wydaje się, że nie wykrywa to przypadków bez rozwiązań takich jak x(3..12).(czy muszę aktualizować?). BTW, czy możesz zasugerować dobre wprowadzenie do clingo?
Christian Sievers
1
@ChristianSievers Ups, to był błąd, który teraz naprawiłem. W UNSATISFIABLEtakim przypadku powinien wypisać dane. Najczęściej korzystałem z przewodnika Potassco .
Anders Kaseorg
4

Mathematica, 105 bajtów

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


Wypróbuj online,
skopiuj i wklej kod za pomocą Ctrl + V,
wklej dane wejściowe na końcu kodu,
naciśnij Shift + Enter, aby uruchomić

Wejście

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

przyjmuje listę jako dane
wyjściowe 0, jeśli ich nie ma

J42161217
źródło
Ładne użycieCheck
Keyu Gan
Dlaczego nie usunąłeś swojej pierwszej odpowiedzi, gdy posiadałeś już działającą wersję?
Neil
Ponieważ to było zupełnie nowe podejście? Jest jakiś problem?
J42161217,
4

Haskell, 136 bajtów

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

Wypróbuj online!

Jak to działa

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

Poświęć dużo czasu {22,24,26,30}.

nimi
źródło
3

Galaretka, 38 35 34 33 31 28 25 24 23 20 19 bajtów

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

-5 bajtów dzięki Leaky Nun

Wypróbuj online!

Myślę, że trzeci przypadek testowy działa, ale jest bardzo wolny. 0jest generowany, gdy nie ma rozwiązań.

Wyjaśnienie (mogło dojść do błędnego wyjaśnienia):

ṀḊŒ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ý
źródło
1
18 bajtów
Leaky Nun
Dzięki! I dziękuję, że sam tego nie zgłosiłeś!
Zacharý
Mam inne 18-bajtowe rozwiązanie bliższe mojemu oryginałowi, bardziej podoba mi się ten:ṀḊŒPðḍ@þ@⁹Sḟ1ðÐḟḢL
Zacharý
Woah ... ṀḊto naprawdę fajna sztuczka!
Zacharý
Ups, to nie działa, podobnie jak moje przepisywanie! To powinno dać wynik 0, a nie 1
Zacharý
2

Julia, 91 bajtów

x->(t=[];for i in x z=findfirst(x->x==0,i%(2:maximum(x)));zt?1:push!(t,z) end;length(t))
Tanj
źródło
Um ... zapomniałeś dołączyć link do nazwy języka, czy faktycznie nazywa się on „[Julia]”?
Zacharý
Masz rację, nazywa się Julia bez nawiasów
Tanj
Możesz to naprawić również w innych odpowiedziach!
Zacharý
Wow, to było wiele odpowiedzi! A jeśli chcesz wstawić link, jego składnia to[Text to display](link to website)
Zacharý