В теории множеств натуральные числа обычно кодируются как чистые множества , то есть множества, которые содержат только пустой набор или другие чистые множества , Однако не все чистые множества представляют собой натуральные числа. Эта задача состоит в том, чтобы решить, представляет ли данный чистый набор кодировку натурального числа или нет.$\mathbb{N} = \{0, 1, 2, 3, ...\}$

Кодирование натуральных чисел работает следующим образом ¹ :

• Ноль - это пустое множество:$Set(0) = \{\}$
• Для числа :$n > 0$$Set(n) = Set(n-1) \cup \{Set(n-1)\}$

Таким образом, кодировки первых нескольких натуральных чисел

• $0 \leadsto \{\}$
• $1 \leadsto \{0\} \leadsto \{\{\}\}$
• $2 \leadsto \{0,1\} \leadsto \{\{\},\{\{\}\}\}$
• $3 \leadsto \{0,1,2\} \leadsto \{\{\},\{\{\}\},\{\{\},\{\{\}\}\}\}$
• $4 \leadsto \{0,1,2,3\} \leadsto \{\{\},\{\{\}\},\{\{\},\{\{\}\}\},\{\{\},\{\{\}\},\{\{\},\{\{\}\}\}\}\}$

Задание

• Учитывая строку, представляющую чистый набор, определите, кодирует ли этот набор натуральное число согласно вышеупомянутой конструкции.
• Однако обратите внимание, что элементы набора не упорядочены, поэтому $\{\{\},\{\{\}\},\{\{\},\{\{\}\}\}\}$ не является единственным допустимым представлением $3$ как, например, $\{\{\{\}\},\{\},\{\{\{\}\},\{\}\}\}$ представляет один и тот же набор.
• Вы можете использовать [], ()или <>вместо {}.
• Вы можете предположить, что наборы даны без ,разделителя.
• Вы можете предположить {{},{}}, что на входе не будет повторяющихся элементов, например, это недопустимый вход, и что вход правильно сформирован, например, нет {{},, {,{}}или похожий.

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

Правда:

{}
{{}}
{{},{{}}}
{{{}},{}}
{{},{{}},{{},{{}}}}
{{{},{{}}},{},{{}}}
{{{{}},{}},{{}},{}}
{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}}}
{{{{{}},{}},{{}},{}},{{}},{},{{},{{}}}}
{{},{{}},{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}}},{{{}},{}},{{},{{}},{{},{{}}}}}
{{{{{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}}

Ложь:

{{{}}}
{{{{}}}}
{{{{}},{}}}
{{},{{}},{{{}}}}
{{{},{{}}},{{}}}
{{{{{}}},{}},{{}},{}}
{{},{{}},{{},{{}}},{{},{{}},{{{}}}}}
{{{{{}},{}},{{{}}},{}},{{}},{},{{},{{}}}}
{{{{{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{{}},{}},{{}},{}},{{{}},{}},{{}}},{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}}

^{Связанный: Естественная конструкция (Выведите заданную кодировку заданного натурального числа.)
1 См. Https://en.wikipedia.org/wiki/Set-theoretic_definition_of_natural_numbers}

JavaScript (Node.js) , 53 48 44 байта

f=a=>(a=eval(a)).every(e=>a[e.length]&&f(e))

Попробуйте онлайн! Тестовые случаи в основном бесстыдно украдены из ответа @ Arnauld's. Объяснение: если набор представляет собой натуральное число, то представляемое им натуральное число должно быть равным размеру набора, и (учитывая, что элементы гарантированно различаются) элементы должны быть представлениями натуральных чисел, меньшими его, и поэтому они должны иметь меньшую длину. Это тривиально верно для пустого набора, конечно. Редактировать: 5 байтов сохранено благодаря @Arnauld. Сохранено 4 байта благодаря @Cowsquack.

Python 3 , 69 58 44 байта

11 байтов благодаря Эрику Аутгольферу.

14 байтов благодаря г-ну Xcoder.

f=lambda s:all(len(e)<len(s)*f(e)for e in s)

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

Wolfram Language (Mathematica) , 60 59 байт

E!=(If[Sort@#===Range[t=Tr[1^#]]-1,t,E]&//@ToExpression@#)&

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

Ядром этого решения является функция

If[Sort@#===Range[t=Tr[1^#]]-1,t,E]&

который преобразует список формы {0,1,2,...,n-1}в любом порядке в выходные данные n(в частности, он преобразуется {}в 0) и преобразует все остальное в действительное число E.

Вызовите эту функцию f. Учитывая ввод, такой как "{{{}},{}}", мы делаем следующее:

1. Преобразуйте строку в выражение Mathematica.
2. Применять fна каждом уровне, получая f[{f[{f[{}]}], f[{}]}].
3. Оценивая все f, мы получим натуральное число для ввода, представляющего его. Например, f[{f[{f[{}]}], f[{}]}]= f[{f[{0}], 0}]= f[{1, 0}]= 2. Все остальное будет производить E.
4. Мы проверяем, является ли результат натуральным числом, проверяя, если это не так E.

Brachylog (v2), 9 байт

↰ᵐo.t~k|Ė

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

Как обычно для решения проблемы , это полная программа. Ввод из стандартного ввода, используя квадратные скобки. Вывод на стандартный вывод как true.против false..

объяснение

Хотя я сказал выше, что это полная программа, на самом деле она более интересна; это и полная программа, и функция. При использовании в качестве полной программы он печатает, является true.ли набор натуральным числом или false.нет. При использовании в качестве функции он «нормализует» натуральное число (то есть нормализует все его элементы и сортирует их по порядку по значению; эта программа использует внутренние списки, а не наборы) или «выдает исключение» (на самом деле это ошибка, так как Пролог), если ввод не является натуральным числом.

Полное поведение программы достаточно просто объяснить: оно чисто неявное в обработке Brachylog полных программ, которые не содержат инструкций ввода / вывода. Рассматриваемое поведение таково: «запустите функцию, взяв ее входные данные из стандартного ввода и убедившись, что ее выходные данные соответствуют описанию, данному первым аргументом командной строки; если утверждение не выполнено или программа выдает исключение, напечатайте false., в противном случае выведите на печать true.» , В этом случае аргумент командной строки отсутствует (т. Е. «Все идет»), поэтому поведение функции исключение / исключение выдает результат.

Что касается поведения функции:

↰ᵐo.t~k|Ė
↰ᵐ          Map a recursive call to this function over the list
  o         Sort the list
   .   |    Assert that the following operation need not change the list:
    t         Take the last (i.e. greatest) element of the list
     ~k       Append an arbitrary element to the resulting list
   .   |    Output the unchanged list
       |    Exception handler: if the above threw an exception,
        Ė     Assert that the input is empty, and output an empty list

Натуральное число определяется как содержащее две части: элементы натурального числа ниже, объединенные с самим числом. Таким образом, все его элементы также являются натуральными числами. Мы можем распознать натуральное число, а) проверив, что все его элементы являются натуральными числами, б) проверив, что самый большой элемент набора идентичен множеству без его самого большого элемента.

Когда мы используем списки, а не наборы (таким образом, квадратные скобки), нам нужно поместить их в согласованный порядок, чтобы сработало сравнение на равенство (в данном случае, отсортированное по «значению»). Порядок сортировки по умолчанию Brachylog будет сортировать префикс списка перед самим списком, что удобно означает, что он будет сортировать натуральные числа по числовому значению. Таким образом, мы можем просто рекурсивно отсортировать все наши числа, чтобы привести их в последовательный порядок. Фактически, с помощью функции, которую мы определяем рекурсивно, мы можем достичь обоих результатов одновременно: рекурсивная сортировка элементов числа и проверка того, что это натуральное число.

Функция, таким образом, состоит из четырех основных частей. ↰ᵐявляется рекурсивным вызовом, гарантирующим, что каждый элемент является натуральным числом, и преобразовывающим его каждый элемент в нормализованную форму. oнормализует само число (его элементы уже нормализованы, поэтому все, что нам нужно сделать, это отсортировать). Затем .t~k|убедитесь, что у нас есть структура, которую мы хотим, проверив, что самый большой элемент и другие элементы одинаковы. Пустой список (то есть 0) не имеет последнего элемента, поэтому получит ошибку подтверждения с помощью t; |Ėобрабатывает этот случай, через давая явный запасной вариант в случае , когда список входов пуст.

K (нгн / к) , 26 24 27 байт

~^{$[#(!#x)^o'x;0N;#x]}@`j@

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

input - строка json, проанализированная `j@(синтаксис, специфичный для ngn / k)

{ }рекурсивная функция с аргументом x. он возвращает натуральное число, представленное множеством x, или null ( 0N), если оно не представляет его.

$[ ; ; ]если-то-еще. 0 фальси, другие целые числа правдивы

!#xцелые числа от 0 (включительно) до длины x(исключая)

^ без

o'xrecursion ( o) для каждого ( ') элементаx

# длина

^ нулевой?

~ не

@выступает в качестве фиктивного последнего глагола , так что ~и ^получить композиции с { }вместо того , чтобы применять к нему

Желе , 10 байт

ẈṢ‘⁼Jȧ@ßƇƑ

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

Japt , 9 байт

Порт Нейла JS решение . Пожалуйста, проголосуйте, если вы голосуете за это.

e@Ê>XÊ©ßX

Попробуйте или запустите все тесты

              :Implicit input of array U
e             :Does every element in U return true
 @            :When passed through the following function as X
  Ê           :Length of U
   >          :Greater than
    XÊ        :Length of X
      ©       :Logical AND with
       ßX     :A recursive call of the programme with X passed as the new value of U

Красный , 81 байт

func[a][p: 1 foreach e to-block a[p: p *(pick[1 0](length? e)< length? a)* f e]p]

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

Похоже на ответ Лаки Нун Python 3

Желе , 8 байт

߀Ṣ
ÇṖƤƑ

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

Попробуйте онлайн! или проверьте все тесты

Как это работает

߀Ṣ   Helper link. Argument: A (array)

߀    Recursively map the helper link over A.
  Ṣ   Sort the result.

Это дает каноническое представление входных данных, состоящих исключительно из отсортированных массивов.

ÇṖƤƑ  Main link. Argument: A (array)

Ç     Call the helper link to canonicalize the array.
   Ƒ  Fixed; call the link to the left and test if it returns its argument unchanged.
 ṖƤ       Pop prefix; for each non-empty prefix of the result, remove its last element.

Желе , 7 байт

Ẉ<La߀Ạ

Это порт ответа Python про Лаки Нун .

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

Попробуйте онлайн! или проверьте все тесты

Как это работает

Ẉ<La߀Ạ  Main link. Argument: A (array)

Ẉ        Width; compute the length of A's elements.
  L      Yield the length of A.
 <       Compare them, yielding an array of Booleans.
    ߀   Recursively map the main link over A.
   a     Take the logical AND of the Booleans and the results of the map.
      Ạ  All; yield 1 if and only if all ANDs yielded 1.

Wolfram Language (Mathematica) , 52 байта

If[Max[#0/@#]<(l=2Length@#),l]&@*ToExpression/*EvenQ

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