задача
Напишите функцию / программу, которая принимает
n
в качестве параметра / ввода и печатает / возвращает количество топологий (как показано ниже) в наборе{1,2,...,n}
.
Определение топологии
Пусть X - любое конечное множество, и предположим, что T, являющееся подмножеством множества степеней X (т. Е. Множества, содержащего подмножества X), удовлетворяет следующим условиям :
X и пустой набор находятся в T.
Если два множества U и V находятся в T, то объединение этих двух множеств находится в T.
Если два множества U и V находятся в T, то пересечение этих двух множеств находится в T.
... тогда T называется топологией на X.
Характеристики
Ваша программа либо:
- функция, которая принимает
n
в качестве параметра - или программа, которая вводит
n
и печатает или возвращает количество (различных) топологий в наборе
{1,2,...,n}
.- функция, которая принимает
n
это любое неотрицательное целое число, которое меньше 11 (конечно, нет проблем, если ваша программа обрабатывает n больше 11), и результат является положительным целым числом.Ваша программа не должна использовать какие-либо библиотечные функции или встроенные функции, которые вычисляют количество топологий напрямую.
Пример ввода (значение n): 7
Пример вывода / возврата: 9535241
Вы можете проверить возвращаемое значение здесь или здесь .
Конечно, выигрывает самый короткий код.
Победитель определен, однако я могу сменить победителя, если появится более короткий код.
источник
Ответы:
Хаскель, 144 персонажа
Практически прямая реализация спецификации, по модулю какая-то магия монад.
Очень медленно для
n > 4
.источник
Питон, 147 символов
Быстрый для N <= 6, медленный для N = 7, маловероятно, что N> = 8 когда-либо завершится.
Отдельные наборы представлены целочисленными битовыми масками, а топологии - наборами битовых масок.
S(i,K)
вычисляет количество различных топологий, которые вы можете сформировать, начиная сK
добавления наборов с помощью битовых масок> =i
.источник
Zsh, 83 знака
Это решение соответствует букве ваших требований (но, конечно, не духу). Существует, несомненно, способ сжать цифры еще больше.
источник
Питон, 131 символ
lambda n:sum(x&(x>>2**n-1)&all((~(x>>i&x>>j)|x>>(i|j)&x>>(i&j))&1 for i in range(2**n)for j in range(2**n))for x in range(2**2**n))
Расширенная версия:
Например, предположим, что n = 3. Возможные подмножества [n]:
где i-й бит указывает, находится ли я в подмножестве. Чтобы кодировать наборы подмножеств, мы замечаем, что каждое из этих подмножеств либо принадлежит, либо не принадлежит к рассматриваемому набору. Так, например,
указывает, что x содержит {}, {2} и {1,2,3}.
источник