Покройте набор с кратными

14

Давайте множество целых чисел больше 1 и назовем его X . Мы определим S (i) как множество всех членов X, делимых на i, где i> 1 . Хотел бы выбрать из этих подмножеств группу таких, что

  • Их союз - это множество X

  • Ни один элемент X не входит в два множества.

Например, мы можем перегруппироваться {3..11}как

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

Некоторые наборы не могут быть выражены таким образом. Например, если мы возьмем {3..12}, 12это кратное 3 и 4, предотвращающее взаимное исключение наших наборов.

Некоторые наборы могут быть выражены несколькими способами, например {4..8}могут быть представлены как

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

но это также может быть представлено как

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

задача

Наша цель - написать программу, которая будет принимать набор в качестве входных данных и выводить наименьшее количество подмножеств, которые покрывают его таким образом. Если их нет, вы должны вывести некоторое значение, отличное от положительного целого числа (например 0).

Это вопрос поэтому ответы будут оцениваться в байтах, причем меньше байтов будет лучше.

тесты

{3..11}       -> 5
{4..8}        -> 3
{22,24,26,30} -> 1
{5}           -> 1
Пост Рок Гарф Хантер
источник
Если их нет, вы должны вывести некоторое значение, отличное от положительного целого числа (например, 0). Разве наша программа не может привести к неопределенному поведению?
г-н Xcoder
Кроме того, вы можете добавить тестовый пример, как [5..5]? Можем ли мы получить такие вещи, как [8..4]?
г-н Xcoder
@ Mr.Xcoder Нет, не может. Программы должны быть в состоянии выявлять невозможные случаи, а не просто зацикливаться на них навсегда.
Пост Рок Гарф Хантер
1
« 12является множителем того и другого 3и 4мешает нашим сетам быть взаимоисключающими »: почему? Я не вижу ничего другого в постановке задачи, которая требует включения 12в оба подмножества.
Питер Тейлор
1
Кроме того, что с тестовыми случаями? [22,24,26,30]все кратны 2. Вы уверены, что было бы не лучше удалить это и поместить в песочницу?
Питер Тейлор

Ответы:

6

Python 2 , 167 байт

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*

Попробуйте онлайн!

-9 байтов благодаря Zacharý
-4 байта благодаря Mr. Xcoder
-2 байта, используя списки вместо наборов
-5 байтов, используя a in [...]вместо any([a == ...]).
-2 байта благодаря Mr. Xcoder
-8 байтов за счет слияния операторов
-5 байтов благодаря Mr. Xcoder
-7 байтов благодаря Mr. Xcoder / Zacharý
+7 байтов, чтобы исправить ошибку
-1 байт благодаря ovs

нота

Это очень медленно для больших максимальных чисел, потому что оно никоим образом не оптимизировано; это не было в течение 2 минут на устройстве мистера Xcoder для [22, 24, 26, 30].

HyperNeutrino
источник
5

Клинго , 51 байт

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

демонстрация

$ 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
Андерс Касеорг
источник
Это, кажется, не обнаруживает случаи без решений, как x(3..12).(или мне нужно обновить?). Кстати, вы можете предложить хорошее введение в клинго?
Кристиан Сиверс
1
@ChristianSievers Ой, это была ошибка, которую я сейчас исправил. Это должно вывести UNSATISFIABLEв таком случае. Я в основном использовал руководство Потасско .
Андерс Касеорг
4

Mathematica, 105 байт

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


Попробуйте онлайн
скопируйте и вставьте код с помощью Ctrl + V,
вставьте ввод в конце кода,
нажмите Shift + Enter для запуска

вход

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

принимает список в качестве входных
выходов 0, если их нет

J42161217
источник
Хорошее использованиеCheck
Кейу Ган
Почему вы не восстановили свой первый ответ, когда у вас была рабочая версия?
Нил
Потому что это был совершенно новый подход? Есть проблема?
J42161217,
4

Haskell, 136 байт

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

Попробуйте онлайн!

Как это устроено

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

Потратьте много времени на {22,24,26,30}.

Ними
источник
3

Желе, 38 35 34 33 31 28 25 24 23 20 19 байт

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

-5 байт благодаря Leaky Nun

Попробуйте онлайн!

Я думаю, что третий контрольный пример работает, но он очень медленный. 0выводится, когда нет решений.

Объяснение (возможно, неправильно поняли это объяснение):

ṀḊŒ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
Zachary
источник
1
18 байтов
прохудившаяся монахиня
Благодарность! И спасибо, что не подали это сами!
Захари
У меня есть другое 18-байтовое решение, более близкое к моему оригиналу, мне лично это нравится больше:ṀḊŒPðḍ@þ@⁹Sḟ1ðÐḟḢL
Zacharý
Вау ... на ṀḊсамом деле это действительно крутой трюк!
Захари
Ой, это не работает, и мой переписать тоже! Это должно вывести 0, а не 1
Zacharý
2

Юлия, 91 байт

x->(t=[];for i in x z=findfirst(x->x==0,i%(2:maximum(x)));zt?1:push!(t,z) end;length(t))
Tanj
источник
Хм ... вы забыли включить ссылку в название языка или она на самом деле называется "[Джулия]"?
Захари
Вы правы, зовут Юля без скобок
Tanj
Возможно, вы захотите исправить это и на других ваших ответах!
Захари
Вау, это было много ответов! И если вы хотите вставить ссылку, синтаксис[Text to display](link to website)
Zacharý