Вызов
Учитывая набор T
подмножеств конечного множества S={1,2,3,...,n}
, определите, T
является ли топология или нет.
объяснение
Powerset P(S)
некоторого множества S
является множество всех подмножеств S
. Некоторые примеры:
S = {}, P(S) = {{}}
S = {1}, P(S) = {{}, {1}}
S = {1,2}, P(S) = {{}, {1}, {2}, {1,2}}
S = {1,2,3}, P(S) = {{}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}
Топология T
на множестве S
является подмножеством P(S)
со следующими свойствами:
{}
находится вT
иS
находится вT
- Если
A
иB
есть,T
то и их пересечениеA ∩ B
- Если
A
иB
есть,T
то таков и их союзA ∪ B
*
* Это определение не совсем верно, но оно верно для конечных множеств, что достаточно для целей этой задачи. Фактическая аксиома также учитывает бесконечные союзы, но это не имеет значения в конечном случае.
Детали
- Вы можете предположить, что
S = {1,2,...,n}
(или альтернативноS = {0,1,...,n}
) гдеn
наибольшее целое число, которое появляется в наборахT
. - Формат ввода является гибким: вы можете использовать строку, список списков или набор списков или любой аналогичный формат, с которым может работать ваш язык. Вы также можете использовать наборы, как,
S = {0,1,...,n}
если это более удобно. - Выход должен быть truthey или falsey.
- Вы можете принять
n
(или альтернативноn+1
илиn-1
) в качестве дополнительного входа. - Если вы работаете с упорядоченными списками, вы можете предположить, что числа в наборе отсортированы. Вы также можете предположить, что список имеет определенный порядок (например, лексикографический.
- Поскольку мы представляем наборы, вы можете предположить, что никакие две записи их списка-представления не равны.
Примеры
Топологии
{{}} over {}
{{},{1}} over {1}
P(S) over S (see in the explanation)
{{},{1},{1,2}} over {1,2}
{{},{1},{2,3},{1,2,3}} over {1,2,3}
{{1}, {1,2,3}, {1,4,5,6}, {1,2,3,4,5,6}, {}, {2,3}, {4,5,6}, {2,3,4,5,6}}
{{}, {1}, {2,3}, {2}, {4,5,6}, {5,6}, {5}, {2,5,6}, {2,5}, {1,5}, {1,2,3,4,5,6}, {1,2,3}, {1,2}, {1,4,5,6}, {1,5,6}, {1,2,5,6}, {2,3,4,5,6}, {2,3,5,6}, {2,3,5}, {1,2,3,5}, {2,4,5,6}, {1,2,5}, {1,2,3,5,6}, {1,2,4,5,6}}
{{}, {1}, {1,2}, {1,2,3}, {1,2,3,4}, {1,2,3,4,5}, {1,2,3,4,5,6}, {1,2,3,4,5,6,7}, {1,2,3,4,5,6,7,8}, {1,2,3,4,5,6,7,8,9}}
{{}, {1}, {1,2,3}, {1,2,3,4,5}, {1,2,3,4,5,6,7}, {1,2,3,4,5,6,7,8,9}}
не-Топология
{{1}} because {} is not contained
{{},{2}} because {1,2} is not contained
{{},{1,2},{2,3}} because the union {1,2,3} is not contained
{{},{1},{1,2},{2,3},{1,2,3}} because the intersection of {1,2} and {2,3} is not contained
{{},{1},{2},{3},{1,2},{2,3},{1,2,3}} because the union of {1} and {3} is not contained
{{}, {1}, {2,3}, {2}, {4,5,6}, {5,6}, {5}, {2,5,6}, {2,5}, {1,5}, {1,2,3,4,5,6}, {1,2,3}, {1,2}, {1,4,5,6}, {1,5,6}, {1,2,5,6}, {2,3,4,5,6}, {2,3,5,6}, {2,3,5}, {2,4,5,6}, {1,2,5}, {1,2,3,5,6}, {1,2,4,5,6}} because {1,2,3,5} is missing
{{}, {1}, {2}, {1,2,3}, {1,2,3,4,5}, {1,2,3,4,5,6,7}, {1,2,3,4,5,6,7,8,9}} because {1,2} is missing
T
это набор, я думаю, что разумно предположить, что ни одно из подмножеств на входе не повторяется (то{{}, {1,2}, {1,2}}
есть не является допустимым входом). Можете ли вы уточнить, что в вызове, положительно или отрицательно?Ответы:
Python 2 ,
117999791 байтПопробуйте онлайн!
Выход через код выхода
источник
Haskell ,
95 89 7478 байтПопробуйте онлайн!
Объяснение:
источник
[[],[2]]
? Это топология, но не над подразумеваемым («Вы можете предположить, что ...») набором.Mathematica,
87736663 байтаПринимает в
[T, n]
качестве ввода.объяснение
Функция, которая возвращает пересечение и объединение входов
Сопоставьте эту функцию со списком ввода на уровне 1.
Сгладить результат (
Outer
часть возвращает набор вложенныхList
s).Возьмите союз между сплющенным списком и
{{}, S}
. Это удаляет дубликаты и добавляет{}
иS
в результирующий список.Проверьте, совпадает ли список сверху с отсортированной версией ввода.
источник
MATL , 38 байт
Входные данные - это двоичная матрица, в которой каждая строка является набором, каждый столбец является элементом, и каждая запись указывает членство. Например,
{{},{1},{1,2}}
выражается как[0 0;1 0;1 1]
. Используйте связанную программу Octave для конвертации в этот формат.Попробуйте онлайн! Или проверьте все тестовые случаи .
объяснение
источник
Python 2 ,
92 71122 байта&
и|
сокращенные строки для операций над множествами.set()
какi-i
Лямбда, которая принимает список наборов в качестве входных данных и возвращает True / false. Просто проверяет, существует ли пустой набор, и существует ли объединение и пересечение каждого набора (два набора, повторяемые как
i
иj
) в данном списке наборов.Попробуйте онлайн!
источник
input()
кset()
в сноске.set()
сi-i
илиi^i
CJam (23 байта)
Набор онлайн-тестов . Это анонимный блок (функция). Я предполагаю
S = {0,1,...,n}
; блок принимает массив отсортированных массивов и вn+1
качестве параметров и оставляет0
или1
в стеке. В случае,{{}}
если код и тестовая структура предполагают этоn+1 = 0
.источник
Pyth,
2423 байтаТестирование
Эта программа принимает вход как упорядоченный список упорядоченных списков. Внутренние списки должны быть в порядке возрастания, а список заказов должен быть отсортирован по длине, а затем лексикографически. Я подтвердил, что это разрешенный формат ввода. Числа начинаются с 0, а N + 1 также принимается за ввод.
Что касается того, как это работает, мы отфильтровываем все, что не в P (S), затем добавляем S,
[]
пересечение каждой пары и объединение каждой пары, дедуплицируем и проверяем, что результат равен входному.источник
Аксиома, 358 байт
Разгул и результаты:
источник