Aufgabe

Sie erhalten eine positive Ganzzahl und müssen mit so vielen Knoten einen " selbstkomplementären Graphen " ausgeben . Wenn Sie nicht wissen, was eine sich selbst ergänzende Grafik ist, hilft Ihnen der Wikipedia-Artikel nicht viel. Im Folgenden finden Sie zwei Erklärungen, eine technische und eine nicht-technische.

Nicht technisch

Ein Graph ist eine Menge von Knoten, die durch Linien verbunden sind. Jedes Punktepaar kann durch eine oder keine Linie verbunden werden. Das "Komplement" eines Graphen ist das Ergebnis der Aufnahme eines Graphen und der Verbindung aller nicht verbundenen Knoten und der Trennung aller verbundenen Knoten.

Ein selbstkomplementäres Diagramm ist ein Diagramm, dessen Komplement in die Form des Originals geändert werden kann. Nachfolgend finden Sie ein Beispiel für ein sich selbst ergänzendes Diagramm und eine Demonstration dessen, wie.

Hier ist eine Grafik mit 5 Knoten:

Wir werden alle Stellen, an denen Verbindungen möglich sind, mit rot gepunkteten Linien markieren:

Jetzt finden wir die Ergänzung des Graphen, indem wir den roten und den schwarzen Rand vertauschen:

Dies sieht nicht wie das Originaldiagramm aus, aber wenn wir die Knoten wie folgt verschieben (jeder Schritt tauscht zwei Knoten aus):

Wir erhalten das Originaldiagramm! Der Graph und sein Komplement sind der gleiche Graph

Technisch

Ein selbstkomplementärer Graph ist ein Graph, der zu seinem Komplement isomorph ist.

Spezifikationen

Sie erhalten eine positive Ganzzahl nach der für Sie am besten geeigneten Methode. Und Sie werden ein Diagramm in der von Ihnen als angemessen erachteten Methode ausgeben, einschließlich, aber nicht beschränkt auf Adjacency Matrix Form , Adjacency List Form und natürlich Bilder! Das ausgegebene Diagramm muss ein eigenes Komplement sein und so viele Knoten haben wie die Ganzzahleingabe. Wenn keine solche Grafik vorhanden ist, müssen Sie einen falschen Wert ausgeben.

Dies ist Code-Golf und Sie sollten darauf abzielen, Ihre Byteanzahl zu minimieren.

Testfälle

Unten sehen Sie Bilder von möglichen Ausgaben für mehrere n

4

5

9

Haskell , 77 Bytes

f n=[(a,b)|b<-[1..n],a<-[1..b-1],mod n 4<2,mod(a+(last$b:[a|odd n,n==b]))4<2]

Probieren Sie es online!

Dies verwendet ein einfach zu berechnendes explizites Kriterium, um zu entscheiden, ob eine Kante (a,b)in den Graphen gehört. Instanziiert diesen Algorithmus , wobei die Permutation zwischen den Werten modulo 4 wechselt

4*m -> 4*m+1 -> 4*m+2 -> 4*m+3 -> 4*m

Wir fügen Kanten ein, deren zwei Endpunktscheitelpunkte zu 0 oder 1 Modulo 4 addieren. Beachten Sie, dass das Durchlaufen von Scheitelpunkten gemäß dieser Permutation jeweils 2 Modulo 4 zur Scheitelpunktsumme hinzufügt und so Kanten und Nichtkanten vertauscht. Dies ergibt eine Permutation von Eckpunkten, die die Kanten ergänzt.

Wenn der Graph einen zusätzlichen Knoten hat, der ein Vielfaches von 4 übersteigt, wird er alleine in einen Zyklus versetzt. Wir schließen Kanten mit ein, wenn der andere Scheitelpunkt gerade ist. Durch das Permutieren der Scheitelpunkte wird die Parität umgekehrt, sodass der Graph selbstkomplementär bleibt.

Wenn die Anzahl der Eckpunkte nicht 0 oder 1 Modulo 4 ist, ist kein selbstkomplementärer Graph möglich, da der gesamte Graph eine ungerade Anzahl von Kanten enthält

Insgesamt sind hier die Bedingungen:

• Wenn der Eingang n nicht 0 oder 1 Modulo 4 ist, geben Sie eine leere Liste aus
• Wenn andernfalls n gerade ist, schließen Sie alle Kanten (a,b)mit a<bund a+bgleich 0 oder 1 Modulo 4 ein.
• Andernfalls tun Sie dasselbe, wenn n ungerade ist, schließen Sie jedoch stattdessen Kanten des Formulars ein, (a,n)wenn a gerade ist.

Der Code kombiniert den zweiten und dritten Fall, indem er die Bedingung mod(a+b)4<2durch mod(a+a)4<2when sowohl odd nals auch ersetzt b==n.

Brachylog 2 , 24 Bytes

{⟦₁⊇Ċ}ᶠpḍ.(\\ᵐcdl?∨?<2)∧

Probieren Sie es online!

Dies ist eine Funktion , die ein Paar aus zwei Adjazenzlisten zurückgibt: eine für das Diagramm, eine für das Komplementdiagramm. (Im Brachylog-Interpreter von TIO können Sie ihn auffordern, eine Funktion anstelle eines vollständigen Programms auszuwerten, indem Sie Zals Befehlszeilenargument angeben.) Die Ausgabe für die Eingabe 5lautet beispielsweise:

[[[1,2],[1,3],[1,5],[3,5],[4,5]],[[2,5],[2,3],[2,4],[3,4],[1,4]]]

So sieht das Bild aus (mit den beiden Diagrammen):

Wie in Prolog-basierten Sprachen üblich, unterstützt die Funktion mehr als ein Aufrufmuster. Insbesondere, wenn Sie versuchen, es als Generator zu verwenden, gibt es alle möglichen selbstkomplementären Graphen mit der angegebenen Anzahl von Eckpunkten aus (obwohl ich keine Anstrengungen unternommen habe, um diesen Fall nutzbar zu machen, und insbesondere gibt es jeden von ihnen aus die Graphen jeweils mehrmals).

Erläuterung

Dies ist im Grunde genommen nur eine Beschreibung des Problems. In der Prolog-Implementierung muss die beste Methode zur Lösung gefunden werden. (Ich bezweifle jedoch, dass in diesem speziellen Fall ein Algorithmus besser als Brute Force verwendet wird, daher ist er wahrscheinlich ziemlich ineffizient. Tests scheinen dies zu bestätigen und zeigen, dass die Leistung mit zunehmender Größe des Diagramms erheblich schlechter wird.)

{⟦₁⊇Ċ}ᶠpḍ.(\\ᵐcdl?∨?<2)∧
 ⟦₁                       The range [1, 2, …, ?], where ? is the input
   ⊇                      A subset of that range…
    Ċ                     …which has exactly two elements
{    }ᶠ                   A list of everything that fits the above description
{⟦₁⊇Ċ}ᶠ                   All edges that could exist in a ?-element graph
       p                  Find a permutation of these…
        ḍ                 …so that splitting it into two equal parts…
          (       ∨   )   …either:
               dl?          produces ? distinct elements
           \                after transposing it
            \ᵐ              and transposing its elements
              c             and flattening one level;
                          or:
                   ?<2      ? was less than 2
         .             ∧  Once you've found it, . specifies what to output

Übrigens musste ich ganze 6 Bytes (¼ des Programms, der Zeichen (∨?<2)) für die Sonderfälle 0 und 1 aufwenden. Frustrierend, aber das ist die Natur von Sonderfällen.

Der \\ᵐcdl?Abschnitt ist etwas schwer zu verstehen, daher hier ein Beispiel. Sie dient dazu, zu überprüfen, ob etwas ein Diagramm und sein Komplement ist, wobei die entsprechenden Kanten im Diagramm und im Komplement in der gleichen Reihenfolge in den Listen aufgeführt sind. Das Graph / Komplement-Paar wird die endgültige Ausgabe des Programms. Hier ist ein Beispielfall:

[[[1,2],[1,3],[1,5],[3,5],[4,5]],[[2,5],[2,3],[2,4],[3,4],[1,4]]]

Wenn Sie dies transponieren, erhalten Sie eine Liste von Paaren entsprechender Kanten zwischen dem Graphen und dem Komplement:

[[[1,2],[2,5]],[[1,3],[2,3]],[[1,5],[2,4]],[[3,5],[3,4]],[[4,5],[1,4]]

Als nächstes transponieren wir innerhalb der Listenelemente und reduzieren eine Ebene; das gibt uns eine Liste von Paaren entsprechender Elemente zwischen dem Graphen und dem Komplement:

[[1,2],[2,5],[1,2],[3,3],[1,2],[5,4],[3,3],[5,4],[4,1],[5,4]]

Es ist klar, dass hier nicht mehr als 1 Paar von jedem Element ausgehen soll (was beweist, dass die Elemente des Graphen und des Komplements in einer 1-zu-1-Entsprechung stehen). Wir können dies fast überprüfen, indem wir lediglich angeben, dass die Liste genau ?unterschiedliche Elemente enthält (dh eine Anzahl unterschiedlicher Elemente, die der Anzahl der Scheitelpunkte entspricht). In diesem Fall ist der Test erfolgreich. Die einzelnen Elemente sind:

[[1,2],[2,5],[3,3],[5,4],[4,1]]

Dies lässt jedoch Raum für ein potenzielles Problem; Wenn ein Scheitelpunkt im Originaldiagramm vollständig getrennt ist, wird seine Entsprechung nicht erwähnt, sodass Platz für eine doppelte Entsprechung von einem anderen Scheitelpunkt bleibt. Wenn dies der Fall ist, muss der Komplementgraph eine Kante zwischen dem Scheitelpunkt haben (ohne Beschränkung der Allgemeinheit, lassen Sie uns sagen , es ist 1), und jede andere Scheitel, und so die Liste der Korrespondenzen enthalten [1,2], [1,3]..., [1, ?]. Wenn ?es groß ist, führt dies zu mehr Korrespondenzen als sonst, sodass es kein Problem gibt. Das einzige Problem tritt auf, wenn ?3 oder niedriger ist. In diesem Fall wird nur eine zusätzliche Korrespondenz hinzugefügt (während eine aus entfernt wird1erscheint nicht in der Eingabe); Dies ist jedoch in der Praxis kein Problem, da es 3 mögliche Kanten in einem 3-Element-Diagramm gibt, bei denen es sich um eine ungerade Zahl handelt (ebenso ist 1 mögliche Kante in einem 2-Element-Diagramm eine ungerade Zahl) Der Test schlägt bei diesem \Schritt fehl (Sie können keine zerlumpte Liste transponieren, dh solche, deren Elemente unterschiedlich lang sind).

BBC BASIC, 161 Bytes

Tokenized Dateigröße 140 Bytes

Laden Sie den Interpreter unter http://www.bbcbasic.co.uk/bbcwin/bbcwin.html herunter

I.m:IF2ANDm ORm<4P.0:END
r=400n=-2A.m:t=2*PI/n:F.i=1TOn*n:a=i DIVn:b=i MODn:c=b:IFa+b A.2a*=t:b*=t:L.r+r*SINa,r+r*COSa,r+r*SINb,r+r*COSb:IF 1A.m A.c DRAWr*3,0
N.

Ungolfed Code

  INPUTm                           :REM get input
  IF2ANDm ORm<4PRINT0:END          :REM if m=4x+2 or 4x+3 or less than 4, print 0 and exit
  r=400                            :REM radius of diagram
  n=-2ANDm                         :REM n = m truncated to an even number
  t=2*PI/n                         :REM t = 1/n turns
  FORi=1TOn*n                      :REM for each combination of vertices
    a=i DIVn                       :REM extract a and b
    b=i MODn                       :REM make a copy of c
    c=b                            :REM if a+b MOD 4 = 2 or 3, convert a and b to angles and draw edge.
    IFa+b AND2 a*=t:b*=t:LINEr+r*SINa,r+r*COSa,r+r*SINb,r+r*COSb:IF 1ANDm ANDc DRAWr*3,0
  NEXT                             :REM if m is odd and c is odd, draw a line to the additional vertex for m=4x+1 input.

Erläuterung

Dies verwendet den gleichen Algorithmus wie Xnor, erzeugt jedoch eine grafische Ausgabe.

Wo nist die Form 4x+2oder 4x+3gibt es keine Lösung, da die Anzahl der Kanten ungerade ist.

Wenn ndie Form 4x ist, ordnen wir alle Eckpunkte in einem Kreis an und zeichnen die Kanten, bei denen (a+b) mod 42 oder 3 ist (aus Golfgründen nicht 0 oder 1 wie bei Xnor. Dies ist daher die Ergänzung der von Xnor gegebenen Lösung.)

Um dies in einem bildhafteren Sinne zu sehen, nehmen wir jeden zweiten Eckpunkt und zeichnen die Kanten zu den Eckpunkten 1 und 2, die entgegen dem Uhrzeigersinn entfernt sind. Dies definiert nparallele Richtungen, die Hälfte der Gesamtmenge. Dann fügen wir alle anderen Kanten parallel zu diesen hinzu.

Das Komplement kann durch Addition von 1 zu a und b in jeder Kantenspezifikation oder bildlich durch Drehen des Diagramms um eine 1/nUmdrehung ermittelt werden.

Wenn ndie Form 4x + 1 ist, fügen wir einen weiteren Scheitelpunkt hinzu, der mit jedem zweiten Scheitelpunkt des 4x-Diagramms verknüpft ist. Wenn es in der Mitte platziert wird, bleibt die Symmetrie des Diagramms erhalten, aber ich habe es aus Gründen der Klarheit außerhalb des Hauptpunktkreises platziert.

Ausgabe

Das Folgende sind die ersten Fälle für 4x + 1. Die 4x-Fälle können durch Löschen des Scheitelpunkts unten rechts und der zugehörigen Kanten angezeigt werden.

JavaScript (ES6), 191 Byte

f=(n,a=[],v=n*~-n/4)=>v%1?0:eval(n>5?f(n-=4,a)&&'for(i=0;i<n;)a.push([i,n+1],[i++,n+2]);a.push([n,++n],[n,++n],[n,++n])-v':'for(l=x=0;x<n;x++)for(y=x;y<n;y++)l<v&y>>x&1?l=a.push([x,y]):a')||a

Diese Funktion gibt eine Adjazenzliste zurück. Es verwendet zwei Algorithmen und unterscheidet zwischen leeren komplementären Diagrammen und Nichtausgaben, indem es zurückgibt, 0anstatt []wenn keine vorhanden sind. Der erste Algorithmus basiert auf Rado-Graphen, die unter Verwendung des BIT-Prädikats erstellt wurden , und erstellt gültige komplementäre Graphen der Ordnung 0, 1, 4 und 5. Der andere Algorithmus, den unsere Freunde in der Mathematik gefunden haben , erstellt einen gültigen V + 4-Vertex-Komplementärgraphen, indem ein gültiger V-Vertex-Komplementärgraph um 4 Pfade ergänzt wird.

Zunächst wird die Eingabe validiert, um das Vorhandensein eines gültigen komplementären Diagramms zu bestätigen (mithilfe von n*~-n/4%1), und wenn dies fehlschlägt, wird zurückgegeben 0. Es prüft dann , ob n>5und rekursiv auf den n-4Fall eine gültige niedrigere Ordnung Lösung zu konstruieren, gilt dann die 4-Addition an die zurück Adjazenzliste auf dem Weg zurück nach oben der Rekursion Kette. Wenn dies n>5nicht der Fall ist, iteriert es von 0bis n-1für xund yund prüft, ob dies der (y>>x)&1Fall ist. Wenn ja, werden diese Knoten gepaart.

Hier ist ein besser lesbares Format der Funktion mit ternären Operatoren, die zu if-else-Anweisungen und eval()s-Inline -Anweisungen erweitert wurden:

// precalculate amount of required vertices in v
f = (n, a = [], v = n*~-n / 4) => {
  // if amount is non-integer
  if (v % 1) {
    // no valid complementary graph
    return 0;
  } else {
    if (n > 5) {
      // generate valid (n-4)-order complementary graph
      f(n -= 4, a);
      // apply 4-path addition
      for (i = 0; i < n;)
        a.push([i, n+1],[i++, n+2]);
      a.push([n, ++n], [n, ++n], [n, ++n]);
    } else {
      // construct Rado graph using BIT predicate
      for(l = x = 0; x < n; x++)
        for(y = x; y < n; y++)
          // if amount of pairs is less than required and xth bit of y is high
          if (l < v && (y>>x & 1))
            // vertices x and y should be paired
            a.push([x,y]);
    }
    return a;
  }
};

Demo

f=(n,a=[],v=n*~-n/4)=>v%1?0:eval(n>5?f(n-=4,a)&&'for(i=0;i<n;)a.push([i,n+1],[i++,n+2]);a.push([n,++n],[n,++n],[n,++n])-v':'for(l=x=0;x<n;x++)for(y=x;y<n;y++)l<v&y>>x&1?l=a.push([x,y]):a')||a

<input type="number" onchange="o.textContent=JSON.stringify(f(this.value))"><pre id="o"></pre>