Ihre Aufgabe wird es sein, eine Funktion oder ein Programm zu schreiben, das eine ganze Zahl n>0als Eingabe und Ausgabe einer Liste der Kanten des neindimensionalen Hyperwürfels verwendet . In der Graphentheorie wird eine Kante als ein 2-Tupel von Eckpunkten (oder Ecken, wenn Sie dies bevorzugen) definiert, die verbunden sind.

Beispiel 1

Ein eindimensionaler Hyperwürfel ist eine Linie mit zwei Eckpunkten, die wir als aund bezeichnen b.

Daher lautet die Ausgabe:

[[a, b]]

Beispiel 2

Der 4-dimensionale Hyperwürfel (oder Tesseract) besteht aus 32 Kanten und sein Graph sieht so aus

und die Ausgabe könnte so aussehen

[[a, b], [a, c], [a, e], [a, i], [b, d], [b, f], [b, j], [c, d], [c, g], [c, k], [d, h], [d, l], [e, f], [e, g], [e, m], [f, h], [f, n], [g, h], [g, o], [h, p], [i, j], [i, k], [i, m], [j, l], [j, n], [k, l], [k, o], [l, p], [m, n], [m, o], [n, p], [o, p]]

Regeln

• Sie können die Eckpunkte beliebig benennen, solange der Name eindeutig ist.
• Die Kanten sind ungerichtet, dh [a, b]und [b, a]gelten als dieselbe Kante.
• Ihre Ausgabe darf keine doppelten Kanten enthalten.
• Die Ausgabe kann in jedem vernünftigen Format erfolgen.
• Standardlücken sind verboten.

Wertung

Kürzester Code gewinnt.

Gelee, 13 Bytes

ạ/S’
2ṗœc2ÇÐḟ

Probieren Sie es hier aus. Für die Eingabe 3ist die Ausgabe:

[[[1, 1, 1], [1, 1, 2]],
 [[1, 1, 1], [1, 2, 1]],
 [[1, 1, 1], [2, 1, 1]],
 [[1, 1, 2], [1, 2, 2]],
 [[1, 1, 2], [2, 1, 2]],
 [[1, 2, 1], [1, 2, 2]],
 [[1, 2, 1], [2, 2, 1]],
 [[1, 2, 2], [2, 2, 2]],
 [[2, 1, 1], [2, 1, 2]],
 [[2, 1, 1], [2, 2, 1]],
 [[2, 1, 2], [2, 2, 2]],
 [[2, 2, 1], [2, 2, 2]]]

Ich hoffe, [1, 1, 1]etc. ist ein okay "Name".

Erläuterung

Die erste Zeile ist ein „Prädikat“ für ein Kantenpaar: [A, B] ạ/S’ist gleich sum(abs(A - B)) - 1, ist null (false-y) iff Aund Bunterscheidet sich in genau einer Koordinate.

Die zweite Zeile ist das Hauptprogramm:

• Generiere alle Kanten mit 2ṗ(Kartesische Potenz von [1, 2]).
• Holen Sie sich alle möglichen Paare mit œc2(Kombinationen der Größe zwei ohne Ersatz).
• Behalten Sie nur Elemente bei, die dem zuvor definierten Prädikat ( ÐḟÇ) entsprechen.

Python 2, 54 56 62 Bytes

lambda n:{tuple({k/n,k/n^1<<k%n})for k in range(n<<n)}

Doppelte Kanten werden durch Erstellen einer Menge von Mengen entfernt, mit der Ausnahme, dass Python erfordert, dass Mengenelemente hashbar sind, sodass sie in Tupel konvertiert werden. Beachten Sie, dass die Mengen {a,b}und {b,a}gleich sind und in dasselbe Tupel konvertiert werden. xsot speicherte 2 Bytes mit n<<n.

Dies kann auf 49 Byte reduziert werden, wenn Zeichenfolgen von Sätzen ein OK-Ausgabeformat haben

lambda n:{`{k/n,k/n^1<<k%n}`for k in range(n<<n)}

was gibt Ausgabe wie

set(['set([1, 3])', 'set([2, 3])', 'set([0, 2])', 'set([0, 1])'])

lambda n:[(k/n,k/n^1<<k%n)for k in range(n*2**n)if k/n&1<<k%n]

Schauen wir uns zunächst eine ältere Version der Lösung an.

lambda n:[(i,i^2**j)for i in range(2**n)for j in range(n)if i&2**j]

Jede Zahl im Intervall [0,2^n)entspricht einem Scheitelpunkt mit Koordinaten, die durch die n-bit-Binärzeichenfolgen angegeben werden . Scheitelpunkte sind benachbart, wenn sie sich in einem einzelnen Bit unterscheiden, dh wenn eines durch X oder eine Potenz von 2 vom anderen erhalten wird.

Diese anonyme Funktion generiert alle möglichen Kanten, indem jeder Scheitelpunkt und jede Bitposition zum Kippen verwendet wird. Um zu vermeiden, dass eine Kante in beide Richtungen dupliziert wird, werden nur Einsen auf Nullen gekippt.

In der mehr Golf-Lösung kwird verwendet, um sowohl ials auch jüber k=n*i+j, aus denen (i,j)extrahiert werden kann, zu codieren (k/n,k%n). Dies erspart eine Schleife im Verständnis. Die Befugnisse von 2werden so ausgeübt 1<<, dass der richtige Operator Vorrang hat.

Ein alternativer Ansatz zum Generieren jedes Scheitelpunktpaars und zum Überprüfen, ob die Scheitelpunkte ein bisschen auseinander liegen, erscheint länger (70 Byte):

lambda n:[(i,x)for i in range(2**n)for x in range(i)if(i^x)&(i^x)-1<1] 

Mathematica, 48 24 Bytes

EdgeList@*HypercubeGraph

Nur eine anonyme Funktion, die integrierte Funktionen verwendet.

JavaScript (SpiderMonkey 30+), 69 64 Byte

n=>[for(i of Array(n<<n).keys())if(i/n&(j=1<<i%n))[i/n^j,i/n^0]]

Dies begann als Port von @ xnors Python 2-Lösung, aber ich konnte 9 Bytes einsparen, indem ich den Code so umschrieb, dass eine einzelne Schleife verwendet wurde. Bearbeiten: Weitere 5 Byte durch iumgekehrtes Aufteilen gespeichert, wie in der aktualisierten Lösung von @ xnor, die jetzt auch eine einzelne Schleife verwendet.

MATL , 20 Bytes

2i^:qt!Z~Zltk=XR2#fh

Das funktioniert mit aktuellen Version (14.0.0) der Sprache / des Compilers.

Probieren Sie es online!

Erläuterung

Dies entspricht in etwa der Antwort von @ xnor .

2i^    % take input n and compute 2^n
:q     % range [0,1,...,2^n-1] (row vector)
t!     % duplicate, transpose into a column vector
Z~     % bitwise XOR with broadcast
Zl     % binary logarithm
tk     % duplicate and round down
=      % true if equal, i.e. for powers of 2
XR     % upper triangular part, above diagonal
2#f    % row and index columns of nonzero values
h      % concatenate vertically

Pyth, 13 Bytes

fq1.aT.c^U2Q2

Ausgang an Eingang 3 :

[[[0, 0, 0], [0, 0, 1]], [[0, 0, 0], [0, 1, 0]], [[0, 0, 0], [1, 0, 0]], [[0, 0, 1], [0, 1, 1]], [[0, 0, 1], [1, 0, 1]], [[0, 1, 0], [0, 1, 1]], [[0, 1, 0], [1, 1, 0]], [[0, 1, 1], [1, 1, 1]], [[1, 0, 0], [1, 0, 1]], [[1, 0, 0], [1, 1, 0]], [[1, 0, 1], [1, 1, 1]], [[1, 1, 0], [1, 1, 1]]]

Erläuterung:

fq1.aT.c^U2Q2
                  Implicit: input = Q
        ^U2Q      All Q entry lists made from [0, 1].
      .c    2     All 2 element combinations of them.
f                 Filter them on
   .aT            The length of the vector
 q1               Equaling 1.

Python 2: 59 Bytes

lambda n:[(a,a|1<<l)for a in range(2**n)for l in range(n)if~a&1<<l]