Einführung
Bei einem ungerichteten Graphen G können wir einen Graphen L (G) (als Liniendiagramm oder konjugierter Graph bezeichnet) konstruieren, der die Verbindungen zwischen Kanten in G darstellt. Dazu wird für jede Kante in ein neuer Scheitelpunkt in L (G) erstellt G und Verbinden dieser Eckpunkte, wenn die Kanten, die sie darstellen, einen gemeinsamen Eckpunkt haben.
Hier ist ein Beispiel aus Wikipedia, das den Aufbau eines Liniendiagramms (in grün) zeigt.
Nehmen Sie als weiteres Beispiel diesen Graphen G mit den Eckpunkten A, B, C und D.
A
|
|
B---C---D---E
Wir erstellen einen neuen Scheitelpunkt für jede Kante in G. In diesem Fall wird die Kante zwischen A und C durch einen neuen Scheitelpunkt namens AC dargestellt.
AC
BC CD DE
Und verbinden Sie Scheitelpunkte, wenn die Kanten, die sie darstellen, einen gemeinsamen Scheitelpunkt haben. In diesem Fall haben die Kanten von A nach C und von B nach C den Scheitelpunkt C gemeinsam, sodass die Scheitelpunkte AC und BC verbunden sind.
AC
/ \
BC--CD--DE
Dieses neue Diagramm ist das Liniendiagramm von G!
Weitere Informationen finden Sie in Wikipedia.
Herausforderung
Angesichts der Adjazenzliste für ein Diagramm G sollte Ihr Programm die Adjazenzliste für das Liniendiagramm L (G) drucken oder zurückgeben. Dies ist Code-Golf, also gewinnt die Antwort mit den wenigsten Bytes!
Eingang
Eine Liste von Zeichenfolgenpaaren, die die Kanten von G darstellen. Jedes Paar beschreibt die Eckpunkte, die durch diese Kante verbunden sind.
- Jedes Paar (X, Y) ist garantiert eindeutig, was bedeutet, dass die Liste weder (Y, X) noch eine Sekunde (X, Y) enthält.
Zum Beispiel:
[("1","2"),("1","3"),("1","4"),("2","5"),("3","4"),("4","5")]
[("D","E"),("C","D"),("B","C"),("A","C")]
Ausgabe
Eine Liste von Zeichenfolgenpaaren, die die Kanten von L (G) darstellen. Jedes Paar beschreibt die Eckpunkte, die durch diese Kante verbunden sind.
Jedes Paar (X, Y) muss eindeutig sein, was bedeutet, dass die Liste weder (Y, X) noch eine Sekunde (X, Y) enthält.
Für jede Kante (X, Y) in G muss der Scheitelpunkt, den sie in L (G) erstellt, XY heißen (die Namen werden in derselben Reihenfolge miteinander verknüpft, in der sie in der Eingabe angegeben sind).
Zum Beispiel:
[("12","13"),("12","14"),("12","25"),("13","14"),("13","34"),("14","34"),("14","45"),("25","45"),("34","45")]
[("DE","CD"),("CD","CB"),("CD","CA"),("BC","AB")]
Testfälle
[] -> []
[("0","1")] -> []
[("0","1"),("1","2")] -> [("01","12")]
[("a","b"),("b","c"),("c","a")] -> [("ab","bc"),("bc","ca"),("ca","ab")]
[("1","2"),("1","3"),("1","4"),("2","5"),("3","4"),("4","5")] -> [("12","13"),("12","14"),("12","25"),("13","14"),("13","34"),("14","34"),("14","45"),("25","45"),("34","45")]
quelle
[("1","23"),("23","4"),("12","3"),("3","4")]
, für die die Ausgabe vermutlich sein sollte, ausschließt[("123","234"),("123","34")]
, was nicht richtig interpretiert werden kann. Ich denke, die einzige Möglichkeit, dies zu beheben, besteht darin, zu garantieren, dass die Eingabe niemals solche Mehrdeutigkeiten enthält. Wenn diese Frage jedoch in der Sandbox veröffentlicht worden wäre, hätte ich vorgeschlagen, die Benennung von Scheitelpunkten in der Ausgabe weniger genau zu bestimmen.Antworten:
Ruby, 51 Bytes
Probieren Sie es online aus!
Wenn sie für jede Kombination von zwei Kanten einen gemeinsamen Scheitelpunkt haben (dh wenn das erste Element ihres Schnittpunkts nicht ist
nil
), drucken Sie ein Array mit den beiden Kanten an STDOUT.quelle
JavaScript (Firefox 30-57), 77 Byte
Angenommen, alle Eingaben sind einzelne Buchstaben (also jedes einzelne Zeichen außer
^
und]
).quelle
Brachylog , 13 Bytes
Probieren Sie es online aus!
Mit allen Testfällen
(-1 Byte ersetzt
l₂
mitĊ
, dank @Fatalize.)quelle
Ċ
(Paar) verwenden, anstattl₂
ein Byte zu speichern.K (ngn / k) ,
4539332930 BytesProbieren Sie es online aus!
,:'
Wickeln Sie jede Kante in eine Liste mit 1 Elementen{
}@
Wenden Sie eine Funktion mit implizitem Argument anx
x,/:\:x
Verketten Sie jeden der linkenx
mit jedem der rechtenx
, erhalten Sie eine Ergebnismatrix - alle Kantenpaare,/
Reduzieren Sie die Matrix(
)#
Filter(3=#?,/)#
Filtern Sie nur die Paare, deren Verkettung (,/
) eine Anzahl (#
) von genau 3 eindeutigen (?
) Elementen aufweistDadurch werden Kanten wie
("ab";"ab")
und("ab";"cd")
aus der Liste entfernt.(*>)#
Filtern Sie nur die Paare, deren sortabsteigende Permutation (>
) mit (*
) a 1 beginnt (Nicht-0 ist boolean true).In unserem Fall könnte die sortabsteigende Permutation
0 1
oder sein1 0
.quelle
Gelee , 5 Bytes
Probieren Sie es online aus!
quelle
f
undƇ
in Jelly verwendet? Wenn ich es in den Dokumenten lese, sind beide Filter.f
ist " Filter; entferne die Elemente aus x, die nicht in y sind. " undƇ
ist " Filter (Alias fürÐf
). Behalte alle Elemente, die eine Bedingung erfüllen. ". Werden sie immer zusammen verwendet? Wird dasƇ
zum Schließen des Filters verwendetf
? Wie in, istf...Ƈ
ähnlich wieʒ...}
in 05AB1E? Oder hat das/
(" Reduzieren oder n-weise Reduzieren ") etwas damit zu tun? Ich versuche nur, den Code zu verstehen, und ich bin verwirrt über die zwei verschiedenen Filterbefehle (und wie beide hier verwendet werden). :)f
undƇ
sind zwei völlig getrennte Dinge. Sie können denken,f
als Schnittpunkt (bei zwei Listen, es ihre gemeinsame Elemente zurückgibt) undƇ
ist wieʒ
in 05AB1E. Kurz gesagt:Œc
Gibt alle möglichen Kombinationen von zwei Elementen aus der Liste zurück undƇ
behält dann nur diejenigen bei, die den Link erfüllen (dh Jelly-Funktion)f/
, wodurch der Schnittpunkt der beiden Elemente zurückgegeben wird. Aberf
ist eine Dyade (Zwei-Argument-Funktion) und wir müssen sie stattdessen auf eine Zwei-Elemente-Liste anwenden, also müssen wir verwenden/
, reduzieren.f
in den Dokumenten hat mich, obwohl er korrekt ist, hauptsächlich mit dem tatsächlich verwendeten Filter verwechseltƇ
. Ihre Erklärung von " zwei Listen gegeben, geben Sie ihre gemeinsamen Elemente zurück " machte alles klar. Und ich hatte tatsächlich das Gefühl/
, dass damit Jellys Daten irgendwie konvertiert wurden. Eigentlich sehe ich jetzt den Abschnitt 6.6 Reduzieren im Tutorial im Jelly-Wiki, der erklärt, wie eine Dyade geplatzt und eine reduzierte Monade gepusht wird (im Grunde 2 Argumente gegen eine Liste von Paaren als Argument). Danke, jetzt alles klar!MATL , 13 Bytes
Probieren Sie es online aus!
Nicht so schlecht, wie ich es bei der Eingabe des Zellenarrays erwartet hatte. Grundsätzlich die gleiche Idee wie @ Doorknobs Ruby-Antwort .
quelle
C (gcc) , 173 Bytes
Eingabe
i
und Ausgabeo
sind flache, nullterminierte Arrays. Ausgabenamen können bis zu 998 Zeichen lang sein, lange bevor dies unterbrochen wird.Probieren Sie es online aus!
quelle
*x
anstelle vonx[0]
undint**
anstelle vonchar**
Mathematica 23 Bytes
Beispiel:
g = Graph[{1 <-> 2, 2 <-> 3, 3 <-> 4, 2 <-> 4 }]
(*
{2 1, 3 2, 4 1, 4 2, 4 3}
*)
quelle
Pyth , 7 Bytes
Probieren Sie es hier aus!
Wenn eine Verbindung erforderlich ist, 10 Bytes
Probieren Sie es hier aus!
quelle
Wolfram Language
6453 BytesFindet alle Eingabelisten
Subset
der Länge 2,Select
diejenigen, in denen sich die Knoten eines Paares mit den Knoten eines anderen Paares schneiden (was anzeigt, dass sich die Paare einen Knoten teilen), undStringJoin
die Knoten für alle ausgewählten Paare.Der Code ist besonders schwer zu lesen, da er 4 verschachtelte reine ( auch "anonyme") Funktionen verwendet.
Der Code verwendet Klammern "{}" als Listenbegrenzer, wie es in Wolfram Language üblich ist.
1 Byte dank Mr. Xcoder gespeichert.
Beispiel
quelle
Select[#~Subsets~{2},IntersectingQ@@#&]/.{a_,b_}:>{""<>a,""<>b}&
- Probieren Sie es online aus!Python 2 , 109 Bytes
Probieren Sie es online aus!
Erstellen Sie für jeden Knoten
x
(der durch Erstellen einer Menge aus der abgeflachten Kantenliste ermittelt wird) eine Liste der Paarep
, diex
Mitglied sind.Q
Finden Sie dann für jede dieser Listen die eindeutigen, unterschiedlichen Paarungen innerhalbQ
(Eindeutigkeit / Unterscheidung wird über erzwungenif s<t
).quelle
C # 233 Bytes
Beispiel
quelle