Twoim zadaniem będzie napisanie funkcji lub programu, który weźmie liczbę całkowitą n>0jako dane wejściowe i wyprowadza listę krawędzi nhiperwymiarowego hipersześcianu . W teorii grafów krawędź jest zdefiniowana jako 2-krotna liczba wierzchołków (lub narożników, jeśli wolisz), które są połączone.

Przykład 1

Hipersześcian 1-wymiarowy jest linią i ma dwa wierzchołki, które nazwiemy ai b.

Dlatego wynik będzie:

[[a, b]]

Przykład 2

4-wymiarowy hipersześcian (lub tesseract) składa się z 32 krawędzi, a jego wykres wygląda następująco

i wynik może wyglądać tak

[[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]]

Zasady

• Możesz nazwać wierzchołki w dowolny sposób, pod warunkiem, że nazwa jest unikalna.
• Krawędzie nieukierunkowane, IE [a, b]i [b, a]są uznane za samej krawędzi.
• Twoje dane wyjściowe nie mogą zawierać zduplikowanych krawędzi.
• Dane wyjściowe mogą mieć dowolny rozsądny format.
• Standardowe luki są zabronione.

Punktacja

Najkrótszy kod wygrywa.

Galaretka, 13 bajtów

ạ/S’
2ṗœc2ÇÐḟ

Wypróbuj tutaj. Dane wejściowe 3to:

[[[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]]]

Mam nadzieję, że [1, 1, 1]itd. To dobre „imię”.

Wyjaśnienie

Pierwszy wiersz jest „predykatem” na parze krawędzi: [A, B] ạ/S’jest równy sum(abs(A - B)) - 1, co oznacza zero (false-y) iff Ai Bróżni się dokładnie jedną współrzędną.

Druga linia to program główny:

• Wygeneruj wszystkie krawędzie za pomocą 2ṗ(potęgi kartezjańskiej [1, 2]).
• Uzyskaj wszystkie możliwe pary przy użyciu œc2(kombinacje rozmiaru drugiego bez wymiany).
• Zachowaj tylko elementy spełniające predykat zdefiniowany wcześniej ( ÐḟÇ).

Python 2, 54 56 62 bajtów

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

Zduplikowane krawędzie są usuwane przez utworzenie zestawu zestawów, z wyjątkiem tego, że Python wymaga, aby elementy zestawu były haszowalne, więc są konwertowane na krotki. Zauważ, że zestawy {a,b}i {b,a}są równe i konwertowane na tę samą krotkę. xsot zapisał 2 bajty za pomocą n<<n.

Można to zmniejszyć do 49 bajtów, jeśli ciągi zestawów są w formacie wyjściowym OK

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

co daje wynik jak

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]

Najpierw spójrzmy na starszą wersję rozwiązania.

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

Każda liczba w przedziale [0,2^n)odpowiada wierzchołkowi o współrzędnych podanych przez n-bitowe ciągi binarne. Do wierzchołków przylegają, jeśli różnią się one jednym bitem, tj. Jeśli jeden jest uzyskiwany od drugiego przez moc x 2.

Ta anonimowa funkcja generuje wszystkie możliwe krawędzie, przejmując każdy wierzchołek i każdą pozycję bitową. Aby uniknąć powielania krawędzi w obu kierunkach, tylko 1 są odwracane do 0.

W bardziej golfowym rozwiązaniu ksłuży do kodowania zarówno poprzez , jak ii jpoprzez k=n*i+j, z którego (i,j)można wyodrębnić jako (k/n,k%n). To zapisuje pętlę w zrozumieniu. Uprawnienia 2są wykonywane tak, 1<<aby mieć właściwy priorytet operatora.

Alternatywne podejście do generowania każdej pary wierzchołków i sprawdzania, czy są one nieco rozłożone, wydaje się dłuższe (70 bajtów):

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 bajtów

EdgeList@*HypercubeGraph

Tylko anonimowa funkcja korzystająca z wbudowanych funkcji.

JavaScript (SpiderMonkey 30+), 69 64 bajtów

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

Zaczęło się to jako port rozwiązania Python 2 dla @ xnor, ale udało mi się zaoszczędzić 9 bajtów, przepisując kod w celu użycia pojedynczej pętli. Edycja: Zapisano kolejne 5 bajtów, dzieląc ina odwrót, zgodnie ze zaktualizowanym rozwiązaniem @ xnor, które teraz używa również pojedynczej pętli.

MATL , 20 bajtów

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

Działa to z bieżącą wersją języka / kompilatora (14.0.0) .

Wypróbuj online!

Wyjaśnienie

Wykorzystuje to mniej więcej ten sam pomysł, co odpowiedź @ 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 bajtów

fq1.aT.c^U2Q2

Dane wyjściowe na wejściu 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]]]

Wyjaśnienie:

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 bajtów

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