Os dois conjuntos são iguais

9

{}é o conjunto vazio. Você pode usar ()ou []se você escolher.

Não vamos definir rigorosamente "conjunto", mas todos os conjuntos atendem às seguintes propriedades:

Os conjuntos seguem a estrutura matemática usual. Aqui estão alguns pontos importantes:

  • Os conjuntos não são pedidos.
  • Nenhum conjunto contém a si próprio.
  • Os elementos estão em um conjunto ou não, isso é booleano. Portanto, os elementos do conjunto não podem ter multiplicidades (ou seja, um elemento não pode estar em um conjunto várias vezes).
  • Os elementos de um conjunto também são conjuntos e {}são o único elemento primitivo.

Tarefa

Escreva um programa / função que determine se dois conjuntos são iguais.

Entrada

Dois conjuntos válidos via stdin ou argumento de função. O formato de entrada está solto dentro do motivo.

Algumas entradas válidas são:

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

Entradas inválidas:

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

Resultado

Um valor verdadeiro se as entradas forem iguais, caso contrário, falsificar.

Casos de teste

Seu envio deve responder corretamente para todas as entradas válidas, não apenas para os casos de teste. Estes podem ser atualizados a qualquer momento.

Verdade:

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

Falsy:

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

Pontuação

código-golfe

Regras adicionais

Uma regra adicional foi adicionada banindo tipos iteráveis ​​não ordenados por completo. Eles são muito comuns e banalizam demais esse desafio. Sinta-se à vontade para deixar respostas que violem isso. Coloque uma indicação de que foram feitas antes da alteração da regra.

code-golf decision-problem balanced-string Liam
fonte
Um idioma com um tipo de conjunto aninhado pode apenas verificar a igualdade?
Xnor
@xnor Os built-ins devem ser um jogo justo, sim #
Liam
11
@ Dennis, bem, mesmo que esse seja um desafio de "seqüência equilibrada", eu nunca pensei nisso como um desafio de análise. Mas, agora que penso nisso, assumindo que toda a entrada é válida, eu meio que a tornei um desafio de análise. Então eu acho que você está certo. Idiomas suficientes provavelmente têm a ideia de uma lista não ordenada que trivialize isso.
Liam
11
Eu ficarei bem com qualquer decisão que você tomar. Pessoalmente, embora eu ache que o uso de conjuntos de alguma forma ainda possa ser criativo sem banalizar o desafio (como minha resposta Julia, que converte recursivamente uma matriz aninhada em um conjunto aninhado), permitir conjuntos aninhados como entrada torna tudo muito simples ( ==em Julia, 2 bytes; frozenset.__eq__em Python, 16 bytes; etc.).
Dennis
8
See the comments for an explanation. Por favor, não faça isso. Comentários são voláteis e vão embora com muita facilidade, sutff tão importante vai no post corpo
cat

Respostas:

4

Gelatina , 6 bytes

߀Ṣ
ÇE

Experimente online! ou verifique todos os casos de teste .

Como funciona

Ç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.
Dennis
fonte
3

Braquilog , 8 bytes

{p:1a.}.

Isso espera colchetes na entrada e na saída.

Por exemplo: 

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

Explicação

{     }.   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
Fatalizar
fonte
2

Pitão, 9 bytes

LSyMbqyEy

Formato de entrada: use em []vez de {}.

Suíte de teste

Anders Kaseorg
fonte
2

Mathematica, 16 bytes

Equal@@Sort//@#&

Uma função sem nome que espera uma lista contendo os dois conjuntos, por exemplo

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

Usamos //@( MapAll) para classificar os conjuntos em todos os níveis e depois afirmar que os resultados são iguais.

Martin Ender
fonte
2

JavaScript (ES6), 42 bytes

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

Aceita entrada usando []s p f([[],[[]]],[[[]],[]]). Funciona convertendo as matrizes em seqüências de caracteres e classificando-as de dentro para fora. 0e1 são usados ​​porque são mais curtos que '['e ']', por exemplo, g([[[]],[]])é o 001,00111que representa [[],[[]]].

Neil
fonte
Você não usa recursão, então você pode fazer o anonimato
Bálint 15/06
Por que isso está 0+aí?
Bálint
@ Bálint Porque sem o 0+e +1tudo o que eu conseguiria são vírgulas.
Neil
@ Bálint Não sei por que esqueci de remover o arquivo f=, não o incluí na contagem de bytes e estou com preguiça de editar a publicação apenas para isso.
Neil
2

Python 2, 49 bytes

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

Por exemplo, chamando a função anônima g:

>>> g( [[],[[]]] , [[[]],[]] )
True
Lynn
fonte
g([[],[[],[]],[[],[[]]],[[]],[[[]]]], [[[],[]],[[[]],[]],[[]],[[[]]],[]])retorna False, mas os conjuntos são iguais. Isso deve ser corrigido pelo mapeamento antes da classificação.
Dennis
2

Prolog (SWI) , 37 bytes

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

Experimente online!

Recebe entradas como listas aninhadas, ou seja, com colchetes em vez de chaves. Originalmente era X+Y:-sort(X,M),sort(Y,N),maplist(+,M,N)., mas tentei traduzir a resposta Brachylog v1 do Fatalize e ele ficou 3 bytes mais curto.

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)

Na verdade, ele pode lidar com chaves, por mais 23 bytes:

Prolog (SWI) , 60 bytes

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

Experimente online!

*aqui converte um X=Y;termo (não vazio, portanto o ) entre parênteses no lado direito em uma lista dos elementos do termo e os classifica para o lado esquerdo.

{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.

Desde ambos os argumentos para +está passando *já, colocando um sortem *conserva 7 bytes sobre o uso permutationem+ .

E, finalmente, aqui está uma versão que lida com as listas de entrada, possivelmente com elementos duplicados, e foi isso que me inspirou a escrever uma solução no Prolog para começar:

Prolog (SWI) , 57 bytes

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

Experimente online!

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.

Essencialmente, X/Ydeclara que X é um subconjunto de Y, declarando que, para cada elemento de X, existe um elemento igual de Y, portanto X/Y,Y/Xdeclara que X e Y são conjuntos iguais.

String não relacionada
fonte
E agora eu preciso dormir
String não relacionada
2

APL (NARS2000), 4 bytes

≡⍦

⍦é o operador multiset, que modifica funções para tratar seus argumentos como conjuntos em vez de listas.
≡É a função de equivalência, que retorna um Booleano indicando se os argumentos são completamente equivalentes em valor e forma

Em relação à regra adicional: Observe que esta resposta não usa nenhum tipo de dados definido não ordenado, mas apenas listas normais (que podem conter vários elementos idênticos). Apenas os trata como conjuntos.

A contagem de bytes é 4 porque o NARS2000 usa exclusivamente o UCS-2.

Adão
fonte
1

Julia, 36 35 32 bytes

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

A entrada é uma matriz aninhada, seja a {}sintaxe (obsoleta) ou Any[].

Experimente online!

Dennis
fonte
1

SETL, 1 byte

=

Toma conjuntos como argumentos à esquerda e à direita.

Observe que isso NÃO adere à regra adicionada que proíbe tipos de dados definidos não ordenados.

Adão
fonte
1

Brachylog v2, 3 bytes

p↰ᵐ

Experimente online!

Leva um conjunto através da variável de entrada e o outro conjunto através da variável de saída. É bem-sucedido se os conjuntos forem iguais e falhar se não forem.

Como a minha resposta principal do Prolog, uma tradução da resposta Brachylog v1 da Fatalize (que eu acho que poderia ser aplicada 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.
String não relacionada
fonte
0

, 7 caracteres / 9 bytes

ѨƾꞨî,Ꞩí

Try it here (ES6 browsers only).

Explicação

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

Haskell, 77 bytes

import Data.List
data S=L[S]deriving(Eq,Ord)
f(L x)=L$sort$f<$>x
a!b=f a==f b
Lynn
fonte
Por falta de interesse, por que você precisou definir seu próprio tipo de lista aqui? (Você ==e <não definido por padrão para listas?)
11
o tipo de dados é recursivo: eu defino Scomo uma Llista de Ses. Haskell não tem um tipo interno que possa representar listas de listas de listas de…
Lynn
0

Perl 6 , 55 bytes

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

Recebe entrada com [].

Experimente online!

bb94
fonte
Algumas coisas: você não precisa do espaço após os argumentos para o bloco de código, geralmente é mais curto usar a $^sintaxe, e eu não acho que a []entrada funcione, já que todos os outros são [[]],[[[]]],[[[[]]]]avaliados como[]
Jo King