Czy dwa zestawy są równe


9

{}jest pustym zestawem. Możesz użyć ()lub []jeśli chcesz.

Nie zamierzamy rygorystycznie definiować „zestawu”, ale wszystkie zestawy spełniają następujące właściwości:

Zestawy mają zwykłą strukturę matematyczną. Oto kilka ważnych punktów:

  • Zestawy nie są zamawiane.
  • Żaden zestaw nie zawiera siebie.
  • Elementy są albo w zestawie, albo nie, to jest wartość logiczna. Dlatego ustawione elementy nie mogą mieć wielokrotności (tzn. Element nie może znajdować się w zestawie wiele razy).
  • Elementy zestawu są również zestawami i {}jest jedynym prymitywnym elementem.

Zadanie

Napisz program / funkcję, która określa, czy dwa zestawy są równe.

Wejście

Dwa prawidłowe zestawy za pomocą argumentu stdin lub funkcji. Format wejściowy jest luźny w granicach rozsądku.

Niektóre prawidłowe dane wejściowe to:

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

Nieprawidłowe dane wejściowe:

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

Wynik

Prawdziwa wartość, jeśli dane wejściowe są równe, w przeciwnym razie fałsz.

Przypadki testowe

Twoje zgłoszenie powinno poprawnie odpowiedzieć na wszystkie prawidłowe dane wejściowe, nie tylko na przypadki testowe. Mogą one być aktualizowane w dowolnym momencie.

Prawda:

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

Falsy:

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

Punktacja

Dodatkowe zasady

Dodano dodatkową regułę całkowicie zakazującą nieuporządkowanych typów iteracyjnych. Są zbyt powszechne i zbyt trywializują to wyzwanie. Możesz zostawić odpowiedzi, które naruszają to miejsce, po prostu zaznacz, że zostały udzielone przed zmianą reguły.


Czy język z typem zestawu do zagnieżdżania może po prostu sprawdzać równość?
xnor

@xnor Wbudowane powinny być uczciwą grą, tak
Liam

1
@ Dennis cóż, mimo że jest to wyzwanie „zrównoważone”, nigdy tak naprawdę nie myślałem o nim jako o parsowaniu. Ale teraz, gdy o tym myślę, zakładając, że wszystkie dane wejściowe są prawidłowe, uczyniłem z tego wyzwanie. Więc myślę, że masz rację. Wystarczająca liczba języków prawdopodobnie ma pomysł na nieporządkowaną listę, która by to trywializowała.
Liam,

1
Będę w porządku z każdą decyzją, którą podejmiesz. Osobiście, chociaż uważam, że używanie zestawów może być w dalszym ciągu kreatywne bez banalizowania wyzwania (jak moja odpowiedź Julii, która rekurencyjnie przekształca zagnieżdżoną tablicę w zestaw zagnieżdżony), ale zezwolenie na zagnieżdżanie zestawów jako danych wejściowych sprawia, że ​​całość jest nieco zbyt prosta ( ==w Julia, 2 bajty; frozenset.__eq__w Pythonie 16 bajtów; itp.).
Dennis

8
See the comments for an explanation. Proszę nie rób tego. Komentarze są niestabilne i odchodzą bardzo łatwo, więc ważny sutff trafia do treści postu
kot

Odpowiedzi:




3

Brachylog , 8 bajtów

{p:1a.}.

To oczekuje nawiasów wejściowych i wyjściowych.

Na przykład:

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

Wyjaśnienie

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


2

Mathematica, 16 bajtów

Equal@@Sort//@#&

Nienazwana funkcja, która oczekuje listy zawierającej oba zestawy, np

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

Używamy //@( MapAll) do sortowania zestawów na każdym poziomie, a następnie stwierdzamy, że wyniki są równe.


2

JavaScript (ES6), 42 bajty

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

Akceptuje wprowadzanie za pomocą []s, np f([[],[[]]],[[[]],[]]). Działa poprzez konwersję tablic na ciągi, a następnie sortowanie ich od wewnątrz. 0i 1są używane, ponieważ są krótsze niż '['i ']', więc na przykład g([[[]],[]])to, 001,00111co reprezentuje [[],[[]]].


Nie używasz rekurencji, więc możesz uczynić ją anonimową
Bálint

Dlaczego to 0+tam jest?
Bálint

@ Bálint Ponieważ bez 0+i +1wszystko, co dostanę, to przecinki.
Neil

@ Bálint Nie wiem, dlaczego zapomniałem usunąć f=, nie uwzględniłem go w liczbie bajtów i jestem zbyt leniwy, aby edytować post tylko w tym celu.
Neil

2

Python 2, 49 bajtów

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

Na przykład wywołanie funkcji anonimowej g:

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

g([[],[[],[]],[[],[[]]],[[]],[[[]]]], [[[],[]],[[[]],[]],[[]],[[[]]],[]])zwraca False, ale zestawy są równe. Należy to naprawić poprzez mapowanie przed sortowaniem.
Dennis

2

Prolog (SWI) , 37 bajtów

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

Wypróbuj online!

Pobiera dane wejściowe jako listy zagnieżdżone, tj. W nawiasach kwadratowych zamiast nawiasów klamrowych. Początkowo tak było X+Y:-sort(X,M),sort(Y,N),maplist(+,M,N)., ale potem spróbowałem przetłumaczyć odpowiedź Fatach's Brachylog v1 i okazało się, że 3 bajty krócej.

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)

W rzeczywistości może obsługiwać nawiasy klamrowe, dla 23 kolejnych bajtów:

Prolog (SWI) , 60 bajtów

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

Wypróbuj online!

*tutaj konwertuje (niepusty, stąd X=Y;) nawias klamrowy po prawej stronie na listę elementów tego terminu, a następnie sortuje go na lewą stronę.

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

Ponieważ oba argumenty +*już przetwarzane, wstawienie sortin *pozwala zaoszczędzić 7 bajtów przed użyciem permutationin +.

I wreszcie, oto wersja, która obsługuje listy wejściowe, które mogą mieć zduplikowane elementy, co zainspirowało mnie do napisania rozwiązania w Prologu na początek:

Prolog (SWI) , 57 bajtów

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

Wypróbuj 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.

Zasadniczo X/Ydeklaruje, że X jest podzbiorem Y, deklarując, że dla każdego elementu X istnieje równy element Y, więc X/Y,Y/Xdeklaruje, że X i Y są równymi zbiorami.


A teraz potrzebuję snu
niepowiązany ciąg

2

APL (NARS2000), 4 bajty

≡⍦

jest operatorem multisetowym, który modyfikuje funkcje, aby traktować swoje argumenty jako zestawy zamiast list,
jest funkcją równoważności, która zwraca wartość logiczną wskazującą, czy argumenty są całkowicie równoważne pod względem wartości i kształtu

Odnośnie dodatkowej reguły: Zauważ, że ta odpowiedź nie używa żadnego nieuporządkowanego zestawu danych, a jedynie zwykłe listy (które mogą zawierać wiele identycznych elementów). Po prostu traktuje je jak zestawy.

Liczba bajtów wynosi 4, ponieważ NARS2000 używa wyłącznie UCS-2.


1

Julia, 36 35 32 bajty

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

Dane wejściowe to zagnieżdżona tablica albo (nieaktualna) {}składnia, albo Any[].

Wypróbuj online!


1

SETL, 1 bajt

=

Przyjmuje zestawy jako lewy i prawy argument.

Zauważ, że NIE przestrzega to dodanej reguły, która zabrania nieuporządkowanego zestawu danych.


1

Brachylog v2, 3 bajty

p↰ᵐ

Wypróbuj online!

Pobiera jeden zestaw przez zmienną wejściową, a drugi przez zmienną wyjściową. Udaje się, jeśli zestawy są równe, a kończy się niepowodzeniem, jeśli nie są.

Podobnie jak moja główna odpowiedź Prologa, tłumaczenie odpowiedzi Fatach's Brachylog v1 (do której, jak sądzę, można się pograć w golfa 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.


0

Haskell, 77 bajtów

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

Z braku zainteresowania, dlaczego musiałeś tutaj zdefiniować swój własny typ listy? (Są ==i <nie są domyślnie zdefiniowane dla list?)

1
typ danych jest rekurencyjny: definiuję Sjako (zawiniętą L) listę Ses. Haskell nie ma wbudowanego typu, który mógłby reprezentować listy list list…
Lynn

0

Perl 6 , 55 bajtów

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

Przyjmuje dane za pomocą [].

Wypróbuj online!


Niektóre rzeczy: nie potrzebujesz spacji po argumentach bloku kodu, często $^zamiast tego używa się krótszej składni, i nie sądzę, aby []dane wejściowe działały, ponieważ wszystkie [[]],[[[]]],[[[[]]]]itp. Oceniają na[]
Jo King

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.