Venn-Diagrammzellen

12

Angesichts mehrere Sätze, beispielsweise s1={2,3,7}, s2={1,2,4,7,8}und s3={4,7}ein Venn - Diagramm visualisiert jedem Satz durch eine geschlossene Kurve und Satz Elemente , die entweder innerhalb oder außerhalb des Umfangs der Kurve, je nachdem , ob es sich um Element des Satzes ist oder nicht. Da alle Set-Elemente im Venn-Digramm nur einmal vorkommen, müssen sich die Kurven für jedes Set überlappen, wenn ein Element in mehr als einem Set vorhanden ist. Wir nennen jede solche Überlappung eine Zelle des Venn-Diagramms.

Diese Erklärung kann etwas verwirrend sein. Schauen wir uns ein Beispiel an.

Beispiel

Ein Venn - Diagramm für Sätze s1, s2und s3könnte wie folgt aussehen:

Die Zellen dieses Venn - Diagramm sind (von oben nach unten gelesen, links nach rechts) {1,8}, {2}, {7}, {4}, {3}, {}und {}.

In der Praxis trifft man üblicherweise nur auf Venn-Diagramme mit zwei oder drei Sätzen, da die Darstellung von Venn-Diagrammen mit vier oder mehr Sätzen nicht sehr klar ist. Sie existieren jedoch, zB für sechs Sets:

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

Die Aufgabe

Geben Sie bei einer nicht leeren Menge positiver Ganzzahlen in einer angemessenen Darstellung die Menge der Zellen des Venn-Diagramms der Eingabesätze zurück. Insbesondere ist keine grafische Darstellung erforderlich.

  • Sie können ein vollständiges Programm oder eine Funktion schreiben.
  • Sie können so viele leere Mengen zurückgeben, wie leere Zellen vorhanden sind (dh eine Liste aller Zellen), anstatt nur eine leere Menge (dh die Menge der Zellen).
  • Einige vernünftigen Möglichkeiten der Eingabe für das obige Beispiel beinhalten , sind aber nicht beschränkt auf {{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"oder "2 3 7\n1 2 4 7 8\n4 7". Wenn Sie Zweifel haben, ob das von Ihnen gewählte Eingabeformat akzeptabel ist, können Sie einen Kommentar abgeben.
  • Ihr Ausgabeformat sollte nach Möglichkeit mit Ihrem Eingabeformat übereinstimmen. Beachten Sie, dass diese Regel erfordert, dass Ihr Format leere Sätze eindeutig anzeigen kann.
  • Das ist , also versuchen Sie, so wenig Bytes wie möglich in der Sprache Ihrer Wahl zu verwenden. Um den Wettbewerb pro Sprache anstatt zwischen den Sprachen zu fördern, akzeptiere ich keine Antwort.

Testfälle

Hier sind einige Eingaben zusammen mit möglichen Ausgaben:

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
quelle
Ich gehe davon aus, dass dies aufgrund der Definition einer Menge zutrifft, aber können wir davon ausgehen, dass in einer der Teilmengen keine Duplikate vorhanden sind?
HyperNeutrino
@Hyper Neutrino Ja, Sie können davon ausgehen, dass alle Sätze doppelt vorhanden sind.
Laikoni
Vielleicht könnten Sie einen Testfall hinzufügen, in dem keine der Zellen leer ist. ZB {{1,2,3,4}, {1,2,5,6}, {1,3,5,7}}.
Ørjan Johansen
Wie gibt der zweite nicht {{1,2,3},{4,5,6},{7,8,9},{},{},{},{}}?
Undichte Nonne
1
@carusocomputing Bei näherer Betrachtung werden Sie feststellen, dass dies kein echtes Venn-Diagramm ist, da einige mögliche Überlappungen fehlen.
Laikoni

Antworten:

8

Haskell , 71 Bytes

Eine anonyme Funktion, die eine Liste mit ganzen Zahlen erstellt und eine ähnliche Liste zurückgibt.

Verwenden Sie als (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))[]

Probieren Sie es online!

Wie es funktioniert

  • Verwendet die satzartigen Operationen \\(Differenz) und intersectvon Data.List.
  • Faltet die Liste der "Mengen" (als Listen dargestellt) in eine Liste von Zellen, beginnend mit der leeren Liste [].
  • xist die aktuelle Menge, die dem Diagramm hinzugefügt werden soll, und rist die Liste der bereits erstellten Zellen.
    • x\\(id=<<r)ist die Teilmenge von Elementen x, die sich in keiner der bereits konstruierten Zellen befinden.
    • [intersect x,(\\x)]<*>rTeilt jede Zelle rdanach auf, ob ihre Elemente enthalten sind xoder nicht.
  • Es wird definitiv nicht versucht, leere Zellen zusammenzuführen, daher sind einige davon in der Ausgabe enthalten.
Ørjan Johansen
quelle
Die gleiche Idee wie meine Implementierung, aber zwei Bytes kürzer. Gut gemacht!
Laikoni
4

Jelly , 14 17 Bytes

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

Probieren Sie es online!

Funktionsübermittlung (da das Format, in dem Jelly Listen druckt, standardmäßig kein Roundtrip ist - es kann kein eigenes Ausgabeformat lesen -, sondern eine Funktion, die im gleichen Format ein- und ausgegeben wird). Der TIO-Link enthält eine Fußzeile, in der die Funktion ausgeführt und die Ausgabe im gleichen Format wie die Eingabe gedruckt wird.

Erläuterung

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

Die Anforderung, dass wir mindestens eine leere Menge ausgeben, wenn nicht alle Venn-Diagrammabschnitte verwendet werden, nimmt hier mehr als die Hälfte des Programms ein (es ist dafür verantwortlich , dass wir mindestens eine Gruppe für nicht übereinstimmende Elemente haben, was uns erlaubt um zu verfolgen, wie viele Sätze es ursprünglich gab, plus die letzten neun Bytes des Quellcodes mit Ausnahme von Ġ). Die grundlegende Art und Weise, wie wir es implementieren, besteht darin, sicherzustellen, dass alle 2 ^ n Venn-Diagramm-Teilmengen mindestens einen Eintrag haben, indem ein Dummy-Eintrag hinzugefügt wird, der den Abschnitt "In keinen Sätzen" und (später) jeweils einen Dummy-Eintrag ausfüllt In einem anderen Abschnitt wird dann Ġfür jede Teilmenge eine Gruppe ausgegeben, die wir mit entfernen können ṖṖ€.


quelle
Ähm, es gibt keine Beschränkung auf höchstens 7 Sätze, und einer der Testfälle enthält mehr.
Ørjan Johansen
Ich nahm an, dass der ursprüngliche Satz die Länge 3 hatte, denn so funktionieren Venn-Diagramme, aber anscheinend nicht? In diesem Fall brauche ich möglicherweise eine andere Methode, um das leere Set nur dann hinzuzufügen, wenn nicht alle Abschnitte des Venn-Diagramms ausgefüllt sind. Das ist ein böser Makel, was sonst eine ziemlich elegante Frage ist.
Nun, Sie könnten 7 durch 2 ^ n-1 ersetzen, nehme ich an.
Ørjan Johansen
Ich habe einen Weg gefunden, um zu dem 2 ^ n-1-Wert zu gelangen, der der Spezifikation entspricht, aber es ist schmerzhaft lang. Hoffentlich gibt es einen kürzeren Weg, aber trotzdem ist diese Frage frustrierend.
4

Perl 5, 79 Bytes

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

Übernimmt Eingaben als Liste anonymer Arrays wie ([2,3,7], [1,2,4,7,8], [4,7]). Gibt einen Hash aus, bei dem die Schlüssel Bezeichnungen und die Werte anonyme Arrays sind, die den Ausgabesätzen entsprechen.

Im Rahmen eines vollständigen Programms:

*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;

Erläuterung:

Gibt jedem Set eine Ganzzahl als Beschriftung $.. Erstellt einen Hash, der für jedes eindeutige Element eine Ganzzahl speichert $_. Fügt 2**$.für jeden Satz, der in $_angezeigt wird, eine binäre Zuordnung hinzu, die anzeigt, in welchen Sätzen jedes Element angezeigt wird. Zum Schluss wird für jede Zelle des Venn-Diagramms ein anonymes Array erstellt und die in den entsprechenden Sätzen angezeigten Elemente in das Array verschoben. Jedes Element jedes Arrays existiert also in denselben Mengen und damit in derselben Zelle des Venn-Diagramms.

Chris
quelle
3

Pyth , 11 Bytes

m-@Fds-Qdty

Testsuite.

Wie es funktioniert

Jeder Bereich des Venn-Diagramms repräsentiert Elemente, die sich in [bestimmten Kombinationen der Mengen] befinden, jedoch nicht in [den anderen Mengen].

Wir generieren also alle möglichen Kombinationen (und entfernen die leeren Kombinationen), indem wir die Potenzmenge des Eingangs ermitteln.

Für jede generierte Kombination ermitteln wir den Schnittpunkt der Mengen in der Kombination und filtern die Elemente heraus, die in den anderen Mengen enthalten sind.

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)
Undichte Nonne
quelle
2

JavaScript (ES6), 123 Byte

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
quelle