При наличии нескольких наборов, например 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}}
источник
{{1,2,3},{4,5,6},{7,8,9},{},{},{},{}}
?Ответы:
Haskell , 71 байт
Анонимная функция, берущая список списков целых чисел и возвращающая аналогичный список.
Используйте как
(foldr(\x r->(x\\(id=<<r)):([intersect x,(\\x)]<*>r))[])[[1,2,3],[1,2]]
.Попробуйте онлайн!
Как это устроено
\\
(разность) иintersect
fromData.List
.[]
.x
текущий набор, добавляемый к диаграмме, иr
список уже созданных ячеек.x\\(id=<<r)
это подмножество элементовx
, которых нет ни в одной из уже построенных ячеек.[intersect x,(\\x)]<*>r
разбивает каждую ячейку вr
соответствии с ее элементамиx
или нет.источник
Желе ,
1417 байтПопробуйте онлайн!
Передача функции (поскольку формат, по которому Jelly печатает списки по умолчанию, не предусматривает двусторонней передачи - он не может прочитать собственный выходной формат - но функция вводит и выводит в одном и том же формате). Ссылка TIO содержит нижний колонтитул, который выполняет функцию и печатает ее вывод в том же формате, что и анализируемый ввод.
объяснение
Требование, чтобы мы выводили хотя бы один пустой набор, если не все разделы диаграммы Венна используются, позволяет взять на себя более половины программы здесь (она отвечает за то,
’
чтобы убедиться, что у нас есть хотя бы одна группа для несовпадающих элементов, что позволяет нам чтобы отслеживать, сколько наборов было изначально, плюс последние девять байтов исходного кода, за исключениемĠ
). Основной способ, которым мы реализуем это, состоит в том, чтобы гарантировать, что все 2 ^ n подмножества диаграмм Венна имеют по крайней мере одну запись, добавив фиктивную запись, которая заполнит раздел «без наборов» и (позже) фиктивную запись для каждого другой раздел, затемĠ
выведет группу для каждого подмножества, которую мы можем удалить, используяṖṖ€
.источник
Perl 5, 79 байт
Вводит в виде списка анонимных массивов, таких как [[2,3,7], [1,2,4,7,8], [4,7]). Выводит хеш, где ключи являются метками, а значения - анонимными массивами, соответствующими выходным наборам.
В рамках полной программы:
Объяснение:
Дает каждому набору целое число в качестве метки
$.
. Создает хеш, в котором хранится целое число для каждого уникального элемента$_
. Добавляет2**$.
для каждого набора, который$_
появляется, эффективно создавая двоичную карту, показывающую, в каких наборах появляется каждый элемент. Наконец, создает анонимный массив для каждой ячейки диаграммы Венна и помещает элементы, появляющиеся в соответствующих наборах, в массив. Таким образом, каждый элемент каждого массива существует в одинаковых наборах и, следовательно, в одной и той же ячейке диаграммы Венна.источник
Pyth , 11 байт
Тестирование.
Как это устроено
Каждая область диаграммы Венна представляет элементы, которые находятся в [определенных комбинациях наборов], но не в [других наборах].
Итак, мы генерируем все возможные комбинации (и удаляем пустые комбинации), находя набор мощности входа.
Для каждой сгенерированной комбинации мы находим пересечение наборов в комбинации и отфильтровываем элементы, которые находятся в других наборах.
источник
JavaScript (ES6), 123 байта
источник