Komórki diagramu Venna

12

Biorąc pod uwagę wiele zestawów, na przykład s1={2,3,7}, s2={1,2,4,7,8}i s3={4,7}, A Venna wizualizuje każdego zestawu przez krzywą zamkniętą i zestaw elementów, które wewnątrz lub na zewnątrz obwodu krzywej, w zależności od tego, czy są one element zbioru lub nie. Ponieważ wszystkie elementy zestawu pojawiają się tylko raz w digramie Venna, krzywe reprezentujące każdy zestaw muszą się nakładać, jeśli element występuje w więcej niż jednym zestawie. Nazywamy każdą taką nakładającą się komórkę diagramu Venna.

To wyjaśnienie może być nieco mylące, więc spójrzmy na przykład.

Przykład

Diagram Venna dla zestawów s1, s2a s3może wyglądać następująco:

Komórki tego diagramu Venna są (czytaj od góry do dołu, od lewej do prawej) {1,8}, {2}, {7}, {4}, {3}, {}i {}.

W praktyce często spotyka się tylko diagramy Venna dwóch lub trzech zestawów, ponieważ reprezentacja diagramów Venna czterech lub więcej zestawów nie jest bardzo wyraźna. Jednak istnieją, np. Dla sześciu zestawów:

CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=1472309

Zadanie

Biorąc pod uwagę niepusty zbiór dodatnich liczb całkowitych w dowolnej rozsądnej reprezentacji, zwróć zestaw komórek ze schematu Venna zbiorów wejściowych. W szczególności nie jest wymagana reprezentacja graficzna.

  • Możesz napisać pełny program lub funkcję.
  • Możesz zwrócić tyle pustych zestawów, ile jest pustych komórek (tj. Listę wszystkich komórek) zamiast tylko jednego pustego zestawu (tj. Zestawu komórek).
  • Niektóre rozsądne sposoby wejścia do powyższego przykładu, obejmują, ale nie są ograniczone do {{2,3,7},{1,2,4,7,8},{4,7}}, [[2,3,7],[1,2,4,7,8],[4,7]], "2,3,7;1,2,4,7,8;4,7"lub "2 3 7\n1 2 4 7 8\n4 7". W razie wątpliwości, czy wybrany format wejściowy jest akceptowalny, prosimy o komentarz.
  • Jeśli to możliwe, format wyjściowy powinien odpowiadać formatowi wejściowemu. Pamiętaj, że ta reguła wymaga, aby Twój format mógł jednoznacznie wyświetlać puste zestawy.
  • To jest , więc spróbuj użyć jak najmniej bajtów w wybranym języku. Aby zachęcić do rywalizacji między językami zamiast między językami, nie przyjmuję odpowiedzi.

Przypadki testowe

Oto niektóre dane wejściowe wraz z możliwymi danymi wyjściowymi:

input -> output
{{2,3,7},{1,2,4,7,8},{4,7}} -> {{1,8},{2},{7},{4},{3},{}} (or {{1,8},{2},{7},{4},{3},{},{}})
{{1,2,3},{4,5,6},{7,8,9}} -> {{1,2,3},{4,5,6},{7,8,9},{}}
{{}} -> {{}}
{{1,2,3},{1,2}} -> {{1,2},{3},{}}
{{4,3,8},{1,2,9,3},{14,7,8,5},{6,11,3,8},{10},{9,4,3,7,10}} -> {{6,11},{10},{4},{3},{8},{5,14},{1,2},{9},{7},{}}
{{2,3,4,7},{},{1,3,7,5,6},{2,3,7,5},{7,2,4,3,6},{1,4,5}} -> {{},{4},{2},{7,3},{1},{6},{5}}
{{1,2,3,4},{1,2,5,6},{1,3,5,7}} -> {{4},{3},{2},{1},{6},{5},{7}}
Laikoni
źródło
Zakładam, że jest to prawdą z powodu definicji zestawu, ale czy możemy założyć, że nie będzie duplikatów w jednym z podzbiorów?
HyperNeutrino,
@Hyper Neutrino Tak, możesz założyć, że wszystkie zestawy są wolne od duplikatów.
Laikoni
Być może mógłbyś dodać przypadek testowy, w którym żadna komórka nie jest pusta. Np. {{1,2,3,4}, {1,2,5,6}, {1,3,5,7}}.
Ørjan Johansen
Jak drugi nie daje {{1,2,3},{4,5,6},{7,8,9},{},{},{},{}}?
Leaky Nun
1
@ carusocomputing Po bliższym przyjrzeniu się przekonasz, że nie jest to prawdziwy diagram Venna, ponieważ brakuje niektórych możliwych nakładań.
Laikoni

Odpowiedzi:

8

Haskell , 71 bajtów

Anonimowa funkcja pobierająca listę liczb całkowitych i zwracająca podobną listę.

Użyj jako (foldr(\x r->(x\\(id=<<r)):([intersect x,(\\x)]<*>r))[])[[1,2,3],[1,2]].

import Data.List
foldr(\x r->(x\\(id=<<r)):([intersect x,(\\x)]<*>r))[]

Wypróbuj online!

Jak to działa

  • Wykorzystuje operacje podobne do zestawu \\(różnica) i intersectod Data.List.
  • Składa listę „zestawów” (reprezentowanych jako listy) w listę komórek, zaczynając od pustej listy [].
  • xto bieżący zestaw, który ma zostać dodany do diagramu, i rjest to lista komórek, które zostały już zbudowane.
    • x\\(id=<<r)jest podzbiorem elementów x, których nie ma w żadnej z już zbudowanych komórek.
    • [intersect x,(\\x)]<*>rdzieli każdą komórkę rwedług tego, czy jej elementy są w xśrodku, czy nie.
  • Zdecydowanie nie próbuje scalać pustych komórek, więc jest ich całkiem sporo.
Ørjan Johansen
źródło
Ten sam pomysł, co moja implementacja, ale dwa bajty krótsze. Dobra robota!
Laikoni
4

Galaretka , 14 17 bajtów

FṀ‘³iþ¬Ḅµ;ṀḶ$ĠṖṖ€

Wypróbuj online!

Przesyłanie funkcji (ponieważ format Jelly domyślnie wypisuje listy w obie strony - nie może odczytać własnego formatu wyjściowego - ale dane wejściowe i wyjściowe funkcji w tym samym formacie). Łącze TIO zawiera stopkę, która uruchamia funkcję i drukuje dane wyjściowe w tym samym formacie, w którym analizowane jest wejście.

Wyjaśnienie

FṀ‘³iþ¬Ḅµ;ṀḶ$ĠṖṖ€
FṀ‘               Find the largest number that appears in any of the input sets, + 1
   ³ þ            For each number from 1 to that number, and each of the input sets
    i ¬             find whether the number is missing from the set
       Ḅ          Convert the list of missing sets into a single number using binary
         ;        Append
        µ ṀḶ$     all numbers from 0 to the maximum value minus 1
             Ġ    Group indexes by values
              ṖṖ€ Delete the last group and last element of other groups

Wymaganie, abyśmy wypisali co najmniej jeden pusty zestaw, jeśli nie wszystkie sekcje diagramu Venna są wykorzystane, zajmuje tutaj ponad połowę programu (odpowiada za to , że upewniamy się, że mamy co najmniej jedną grupę dla niepasujących elementów, co pozwala nam aby śledzić, ile oryginalnie zestawów zawierało plus dziewięć ostatnich bajtów kodu źródłowego z wyjątkiem Ġ). Podstawowym sposobem, w którym jego realizacji ma zapewnić, że wszystkie 2 ^ n Venna podzbiory ma co najmniej jedną pozycję dodając wpis manekin, który wypełni sekcji „w nie określa” i (później) wpisu obojętne każdemu inna sekcja, następnie Ġwyświetli grupę dla każdego podzbioru, którą możemy usunąć za pomocą ṖṖ€.


źródło
Nie ma ograniczeń co najwyżej 7 zestawów, a jeden z przypadków testowych ma więcej.
Ørjan Johansen
Zakładałem, że oryginalny zestaw miał długość 3, ponieważ tak działają diagramy Venna, ale najwyraźniej nie? W takim przypadku być może potrzebuję innego sposobu na dodanie pustego zestawu tylko wtedy, gdy nie wszystkie sekcje diagramu Venna są wypełnione. To coś w rodzaju nieprzyjemnej skazy na to, co poza tym jest dość eleganckim pytaniem.
Zakładam, że możesz zastąpić 7 przez 2 ^ n-1.
Ørjan Johansen
Znalazłem sposób na uzyskanie wartości 2 ^ n-1, która odpowiada specyfikacji, ale jest boleśnie długa. Mamy nadzieję, że jest krótsza droga, ale mimo to pytanie jest frustrujące.
4

Perl 5, 79 bajtów

sub{for$.(0..@_){$x{$_}+=2**$.for@{$_[$.]}};push@{$h{$x{$_}}},$_ for keys%x;%h}

Pobiera dane wejściowe jako listę anonimowych tablic, takich jak ([2,3,7], [1,2,4,7,8], [4,7]). Wysyła skrót, w którym klucze są etykietami, a wartości są anonimowymi tablicami odpowiadającymi zestawom wyjściowym.

W ramach pełnego programu:

*x=
sub{for$.(0..@_){$x{$_}+=2**$.for@{$_[$.]}};push@{$h{$x{$_}}},$_ for keys%x;%h};
%x=x([2,3,7],[1,2,4,7,8],[4,7]);
print"Set $_:@{$x{$_}}\n"for keys%x;

Wyjaśnienie:

Daje każdy zestaw liczbę całkowitą jako etykiety $.. Tworzy skrót, który przechowuje liczbę całkowitą dla każdego unikalnego elementu $_. Dodaje 2**$.dla każdego zestawu, który się $_pojawia, skutecznie tworząc mapę binarną pokazującą, w których zestawach pojawia się każdy element. Na koniec tworzy anonimową tablicę dla każdej komórki diagramu Venna i wypycha elementy pojawiające się w odpowiednich zestawach do tablicy. Zatem każdy element każdej tablicy istnieje w tych samych zestawach, a zatem w tej samej komórce diagramu Venna.

Chris
źródło
3

Pyth , 11 bajtów

m-@Fds-Qdty

Zestaw testowy.

Jak to działa

Każdy region diagramu Venna reprezentuje elementy, które są w [pewnych kombinacjach zestawów], ale nie w [innych zestawach].

Tak więc generujemy wszystkie możliwe kombinacje (i usuwamy puste kombinacje) poprzez znalezienie zestawu mocy wejścia.

Dla każdej wygenerowanej kombinacji znajdujemy przecięcie zbiorów w kombinacji i odfiltrowujemy elementy znajdujące się w innych zestawach.

m-@Fds-Qdty  input as Q
          y  power set
         t   remove the first one (empty combination)
m            for each combination d:
  @Fd            find the intersection of all the sets in d
 -               filter out those who are in
     s               the union of
      -Qd            the sets not in the combination
                     (input minus combination)
Leaky Nun
źródło
2

JavaScript (ES6), 123 bajty

a=>a.map((b,i)=>b.map(e=>m[e]|=1<<i),m=[])&&[...Array(1<<a.length)].map((_,i)=>m.map((e,j)=>e==i&&j).filter(j=>j)).slice(1)
Neil
źródło