Диаграмма Венна

12

При наличии нескольких наборов, например s1={2,3,7}, s2={1,2,4,7,8}и s3={4,7}, диаграмма Венна визуализирует каждый набор с помощью замкнутой кривой и элементов набора, которые находятся внутри или за пределами периметра кривой, в зависимости от того, являются ли они элементом набора или нет. Поскольку все элементы набора появляются только один раз на биграмме Венна, кривые, представляющие каждый набор, должны перекрываться, если элемент присутствует в более чем одном наборе. Мы называем каждое такое перекрытие ячейкой диаграммы Венна.

Это объяснение может быть немного запутанным, поэтому давайте посмотрим на пример.

пример

Венна диаграмма для множеств s1, s2и s3может выглядеть следующим образом :

Клетки этой диаграммы Венна являются (читается сверху вниз, слева направо) {1,8}, {2}, {7}, {4}, {3}, {}и {}.

На практике обычно встречаются только диаграммы Венна из двух или трех множеств, потому что представление диаграмм Венна из четырех или более множеств не очень понятно. Однако они существуют, например, для шести наборов:

CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=1472309

Задание

Учитывая непустое множество наборов натуральных чисел в любом разумном представлении, возвратите набор ячеек диаграммы Венна входных наборов. В частности, не графическое представление не требуется.

  • Вы можете написать полную программу или функцию.
  • Вы можете вернуть столько пустых наборов, сколько есть пустых ячеек (то есть списка всех ячеек) вместо одного пустого множества (то есть множества ячеек).
  • Некоторые разумные способы ввода для приведенного выше примера , включают , но не ограничиваются ими {{2,3,7},{1,2,4,7,8},{4,7}}, [[2,3,7],[1,2,4,7,8],[4,7]], "2,3,7;1,2,4,7,8;4,7"или "2 3 7\n1 2 4 7 8\n4 7". Если вы сомневаетесь, приемлем ли выбранный вами формат ввода, не стесняйтесь спрашивать в комментарии.
  • Ваш выходной формат должен соответствовать вашему входному формату, если это возможно. Обратите внимание, что это правило требует, чтобы ваш формат имел возможность однозначно отображать пустые наборы.
  • Это , поэтому старайтесь использовать как можно меньше байтов на выбранном вами языке. Чтобы поощрять конкуренцию за язык, а не между языками, я не приму ответ.

Тестовые случаи

Вот некоторые входы вместе с возможными выходами:

input -> output
{{2,3,7},{1,2,4,7,8},{4,7}} -> {{1,8},{2},{7},{4},{3},{}} (or {{1,8},{2},{7},{4},{3},{},{}})
{{1,2,3},{4,5,6},{7,8,9}} -> {{1,2,3},{4,5,6},{7,8,9},{}}
{{}} -> {{}}
{{1,2,3},{1,2}} -> {{1,2},{3},{}}
{{4,3,8},{1,2,9,3},{14,7,8,5},{6,11,3,8},{10},{9,4,3,7,10}} -> {{6,11},{10},{4},{3},{8},{5,14},{1,2},{9},{7},{}}
{{2,3,4,7},{},{1,3,7,5,6},{2,3,7,5},{7,2,4,3,6},{1,4,5}} -> {{},{4},{2},{7,3},{1},{6},{5}}
{{1,2,3,4},{1,2,5,6},{1,3,5,7}} -> {{4},{3},{2},{1},{6},{5},{7}}
Laikoni
источник
Я предполагаю, что это так из-за определения набора, но можем ли мы предположить, что в одном из подмножеств не будет дубликатов?
HyperNeutrino
@Hyper Neutrino Да, вы можете предположить, что все наборы без дубликатов.
Лайкони
Возможно, вы могли бы добавить тестовый случай, когда ни одна из ячеек не пуста. Например, {{1,2,3,4}, {1,2,5,6}, {1,3,5,7}}.
Орьян Йохансен,
Как второй не дает {{1,2,3},{4,5,6},{7,8,9},{},{},{},{}}?
Утренняя монахиня
1
@carusocomputing При ближайшем рассмотрении вы обнаружите, что это не настоящая диаграмма Венна, поскольку отсутствуют некоторые возможные перекрытия.
Лайкони

Ответы:

8

Haskell , 71 байт

Анонимная функция, берущая список списков целых чисел и возвращающая аналогичный список.

Используйте как (foldr(\x r->(x\\(id=<<r)):([intersect x,(\\x)]<*>r))[])[[1,2,3],[1,2]].

import Data.List
foldr(\x r->(x\\(id=<<r)):([intersect x,(\\x)]<*>r))[]

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

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

  • Использует операции типа set \\(разность) и intersectfrom Data.List.
  • Складывает список «множеств» (представленных в виде списков) в список ячеек, начиная с пустого списка [].
  • xтекущий набор, добавляемый к диаграмме, и rсписок уже созданных ячеек.
    • x\\(id=<<r)это подмножество элементов x, которых нет ни в одной из уже построенных ячеек.
    • [intersect x,(\\x)]<*>rразбивает каждую ячейку в rсоответствии с ее элементами xили нет.
  • Совершенно определенно не пытается объединить пустые ячейки, поэтому в выводе их немало.
Орджан Йохансен
источник
Та же идея, что и у моей реализации, но на два байта короче. Отлично сработано!
Лайкони
4

Желе , 14 17 байт

FṀ‘³iþ¬Ḅµ;ṀḶ$ĠṖṖ€

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

Передача функции (поскольку формат, по которому Jelly печатает списки по умолчанию, не предусматривает двусторонней передачи - он не может прочитать собственный выходной формат - но функция вводит и выводит в одном и том же формате). Ссылка TIO содержит нижний колонтитул, который выполняет функцию и печатает ее вывод в том же формате, что и анализируемый ввод.

объяснение

FṀ‘³iþ¬Ḅµ;ṀḶ$ĠṖṖ€
FṀ‘               Find the largest number that appears in any of the input sets, + 1
   ³ þ            For each number from 1 to that number, and each of the input sets
    i ¬             find whether the number is missing from the set
       Ḅ          Convert the list of missing sets into a single number using binary
         ;        Append
        µ ṀḶ$     all numbers from 0 to the maximum value minus 1
             Ġ    Group indexes by values
              ṖṖ€ Delete the last group and last element of other groups

Требование, чтобы мы выводили хотя бы один пустой набор, если не все разделы диаграммы Венна используются, позволяет взять на себя более половины программы здесь (она отвечает за то, чтобы убедиться, что у нас есть хотя бы одна группа для несовпадающих элементов, что позволяет нам чтобы отслеживать, сколько наборов было изначально, плюс последние девять байтов исходного кода, за исключением Ġ). Основной способ, которым мы реализуем это, состоит в том, чтобы гарантировать, что все 2 ^ n подмножества диаграмм Венна имеют по крайней мере одну запись, добавив фиктивную запись, которая заполнит раздел «без наборов» и (позже) фиктивную запись для каждого другой раздел, затем Ġвыведет группу для каждого подмножества, которую мы можем удалить, используя ṖṖ€.


источник
Хм, нет ограничений не более чем на 7 наборов, а в одном из тестовых случаев есть больше.
Орджан Йохансен,
Я предположил, что исходный набор имел длину 3, потому что так работают диаграммы Венна, но, видимо, нет? В таком случае, возможно, мне нужен другой способ добавить пустой набор, только если не все разделы диаграммы Венна заполнены. Это что-то вроде неприятного недостатка в том, что в остальном довольно элегантный вопрос.
Ну, вы могли бы заменить 7 на 2 ^ n-1, я полагаю.
Орджан Йохансен,
Я нашел способ получить значение 2 ^ n-1, соответствующее спецификации, но это мучительно долго. Надеюсь, есть более короткий путь, но даже в этом случае этот вопрос расстраивает.
4

Perl 5, 79 байт

sub{for$.(0..@_){$x{$_}+=2**$.for@{$_[$.]}};push@{$h{$x{$_}}},$_ for keys%x;%h}

Вводит в виде списка анонимных массивов, таких как [[2,3,7], [1,2,4,7,8], [4,7]). Выводит хеш, где ключи являются метками, а значения - анонимными массивами, соответствующими выходным наборам.

В рамках полной программы:

*x=
sub{for$.(0..@_){$x{$_}+=2**$.for@{$_[$.]}};push@{$h{$x{$_}}},$_ for keys%x;%h};
%x=x([2,3,7],[1,2,4,7,8],[4,7]);
print"Set $_:@{$x{$_}}\n"for keys%x;

Объяснение:

Дает каждому набору целое число в качестве метки $.. Создает хеш, в котором хранится целое число для каждого уникального элемента $_. Добавляет 2**$.для каждого набора, который $_появляется, эффективно создавая двоичную карту, показывающую, в каких наборах появляется каждый элемент. Наконец, создает анонимный массив для каждой ячейки диаграммы Венна и помещает элементы, появляющиеся в соответствующих наборах, в массив. Таким образом, каждый элемент каждого массива существует в одинаковых наборах и, следовательно, в одной и той же ячейке диаграммы Венна.

Крис
источник
3

Pyth , 11 байт

m-@Fds-Qdty

Тестирование.

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

Каждая область диаграммы Венна представляет элементы, которые находятся в [определенных комбинациях наборов], но не в [других наборах].

Итак, мы генерируем все возможные комбинации (и удаляем пустые комбинации), находя набор мощности входа.

Для каждой сгенерированной комбинации мы находим пересечение наборов в комбинации и отфильтровываем элементы, которые находятся в других наборах.

m-@Fds-Qdty  input as Q
          y  power set
         t   remove the first one (empty combination)
m            for each combination d:
  @Fd            find the intersection of all the sets in d
 -               filter out those who are in
     s               the union of
      -Qd            the sets not in the combination
                     (input minus combination)
Дрянная Монахиня
источник
2

JavaScript (ES6), 123 байта

a=>a.map((b,i)=>b.map(e=>m[e]|=1<<i),m=[])&&[...Array(1<<a.length)].map((_,i)=>m.map((e,j)=>e==i&&j).filter(j=>j)).slice(1)
Нил
источник