{}это пустой набор. Вы можете использовать ()или, []если хотите.

Мы не собираемся строго определять «набор», но наборы все удовлетворяют следующим свойствам:

Наборы следуют обычной математической структуре. Вот несколько важных моментов:

• Наборы не заказаны.
• Нет набора содержит себя.
• Элементы либо в наборе, либо нет, это логическое значение. Поэтому элементы набора не могут иметь кратности (то есть элемент не может быть в наборе несколько раз).
• Элементы набора также являются множествами и {}являются единственным примитивным элементом.

задача

Напишите программу / функцию, которая определяет, равны ли два набора.

вход

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

Некоторые действительные входные данные:

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

Неверные данные:

{{} {}              Brackets will always be balanced.
{{},{}} {}          Set contains the same element twice

Вывод

Истинное значение, если входы равны, иначе ложно.

Контрольные примеры

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

Truthy:

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

Falsy:

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

счет

Код-гольф

Дополнительные правила

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

CJam, 11 байт

q']/"]$"*~=

Попробуй это здесь.

CJam, 13 байтов

q~L{{j}%$}j:=

Попробуй это здесь.

Желе , 6 байт

߀Ṣ
ÇE

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

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

ÇE   Main link. Argument: [s, t] (pair of set arrays)

Ç    Apply the helper link to [s, t].
 E   Check if the elements of the resulting pair are equal.


߀Ṣ  Helper link. Argument: u (set array)

߀   Recursively map this link over u.
  Ṣ  Sort the result.

Брахилог , 8 байт

{p:1a.}.

Это предполагает скобки на входе и выходе.

Например:

?- run_from_atom('{p:1a.}.', [[]:[[]]], [[[]]:[]]).
true .

объяснение

{     }.   True if the predicate inside brackets is true with input Input and output Output

 p          Unify an implicit variable with a permutation of Input
  :1a       Apply this same predicate to each element of that implicit variable
     .      True if Output can be unified with the resulting list

Pyth, 9 байт

LSyMbqyEy

Формат ввода: используйте []вместо {}.

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

Mathematica, 16 байт

Equal@@Sort//@#&

Неименованная функция, которая ожидает список, содержащий оба набора, например

Equal@@Sort//@#& @ {{{}, {{}}}, {{{}}, {}}}

Мы используем //@( MapAll) для сортировки наборов на каждом уровне, а затем утверждаем, что результаты равны.

JavaScript (ES6), 42 байта

f=(a,b,g=a=>0+a.map(g).sort()+1)=>g(a)==g(b)

Принимает ввод, используя []s например f([[],[[]]],[[[]],[]]). Работает путем преобразования массивов в строки, а затем сортирует их изнутри. 0и 1используются, потому что они короче, чем '['и ']', например g([[[]],[]]), 001,00111который представляет [[],[[]]].

Python 2, 49 байт

f=lambda x:sorted(map(f,x))
lambda a,b:f(a)==f(b)

Например, вызов анонимной функции g:

>>> g( [[],[[]]] , [[[]],[]] )
True

Пролог (SWI) , 37 байт

X+Y:-permutation(X,Z),maplist(+,Z,Y).

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

Вводит в виде вложенных списков, то есть в квадратных скобках вместо фигурных скобок. Первоначально это было X+Y:-sort(X,M),sort(Y,N),maplist(+,M,N)., но затем я попытался перевести ответ Fatalize's Brachylog v1, и оказалось, что он на 3 байта короче.

X+Y :-                    X+Y succeeds when
    permutation(X, Z),    for some permutation Z of X
    maplist(+, Z, Y).     + succeeds for every pair in Z zipped with Y.
                          (where maplist will succeed without the recursive call to + for
                          two empty lists, and fail if the lists have different lengths)

Вместо этого он может обрабатывать фигурные скобки для еще 23 байтов:

Пролог (SWI) , 60 байт

{A}*C:-A=..[,|B],sort(B,C).
X+Y:-X=Y;X*M,Y*N,maplist(+,M,N).

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

*здесь преобразует (непустой, следовательно, X=Y;) фигурный член с правой стороны в список элементов термина, а затем сортирует его с левой стороны.

{A}*C :-            X*C succeeds when X is the brace term containing A
    A =.. [,|B],    where A is a comma-tuple and B is a list of its elements,
    sort(B, C).     and C is B sorted.

Так как оба аргумента +уже проходят *, добавление sortв in *экономит 7 байтов по сравнению с использованием permutationin +.

И, наконец, вот версия, которая обрабатывает входные списки, возможно, имеющие дубликаты элементов, и именно это вдохновило меня написать решение в Прологе для начала:

Пролог (SWI) , 57 байт

X+Y:-X/Y,Y/X.
X/Y:-maplist(-(Y),X).
Y-E:-member(F,Y),E+F.

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

X+Y :-                   X+Y succeeds when
    X/Y, Y/X.            X/Y and Y/X succeed.
X/Y :-                   X/Y succeeds when
    maplist(-(Y), X).    for every element E of X, Y-E succeeds
                         (or when X is empty).
Y-E :-                   Y-E succeeds when
    member(F, Y),        there exists some element F of Y
    E+F.                 such that E+F succeeds.

По сути, X/Yобъявляет, что X является подмножеством Y, объявляя, что для каждого элемента X есть равный элемент Y, поэтому X/Y,Y/Xобъявляет, что X и Y являются равными наборами.

APL (NARS2000), 4 байта

≡⍦

⍦является оператором мультимножества, который изменяет функции для обработки их аргументов как наборов, а не списков;
≡это функция эквивалентности, которая возвращает логическое значение, указывающее, являются ли аргументы полностью эквивалентными по значению и форме

Что касается дополнительного правила: обратите внимание, что в этом ответе не используется какой-либо неупорядоченный тип данных набора, а только обычные списки (которые могут содержать несколько идентичных элементов). Он просто рассматривает их как наборы.

Число байтов равно 4, потому что NARS2000 использует исключительно UCS-2.

Юлия, 36 35 32 байта

u*v=(sort(u.*v)...)
s%t=s*s==t*t

Входные данные - это вложенный массив либо (устаревший) {}синтаксис, либо Any[].

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

SETL, 1 байт

=

Принимает наборы в качестве левого и правого аргументов.

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

Brachylog v2, 3 байта

p↰ᵐ

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

Принимает один набор через входную переменную, а другой набор через выходную переменную. Успешно, если наборы равны и терпит неудачу, если они не.

Как и мой основной ответ на Пролог, перевод ответа Fatalize's Brachylog v1 (который, я думаю, может быть в гольфе p:0a?).

       The input
p      can be re-ordered so that
 ↰     when this predicate is applied again to
  ᵐ    all of its elements,
       it is the output.

𝔼𝕊𝕄𝕚𝕟, 7 символов / 9 байтов

ѨƾꞨî,Ꞩí

Try it here (ES6 browsers only).

объяснение

         // implicit: î=input1,í=input2
  Ꞩî,Ꞩí // apply the Set method to both inputs
Ѩƾ      // check if the Sets are equal
        // implicit output

Haskell, 77 байт

import Data.List
data S=L[S]deriving(Eq,Ord)
f(L x)=L$sort$f<$>x
a!b=f a==f b

Perl 6 , 55 байт

my&f=->\a,\b {a==b&&all map {f(|$_)},(a.sort Z,b.sort)}

Принимает участие с [].

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

Wolfram Language (Mathematica) , 20 байтов

Sort//@#==Sort//@#2&

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

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