En los bordes del hipercubo

12

Su trabajo será escribir una función o un programa, que tomará un número entero n>0como entrada y salida de una lista de los bordes del hipercubon tridimensional . En la teoría de grafos, un borde se define como una tupla de 2 vértices (o esquinas, si lo prefiere), que están conectadas.

Ejemplo 1

Un hipercubo unidimensional es una línea y presenta dos vértices, que llamaremos ay b.

ingrese la descripción de la imagen aquí

Por lo tanto, la salida será:

[[a, b]]

Ejemplo 2

El hipercubo de 4 dimensiones (o tesseract) consta de 32 bordes y su gráfico se ve así

ingrese la descripción de la imagen aquí

y la salida podría verse así

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

Reglas

  • Puede nombrar los vértices de la forma que desee, siempre que el nombre sea único.
  • Los bordes no están dirigidos, es decir, [a, b]y [b, a]se consideran el mismo borde.
  • Su salida no debe contener bordes duplicados.
  • La salida puede estar en cualquier formato sensible.
  • Las lagunas estándar están prohibidas.

Puntuación

El código más corto gana.

murphy
fuente
¿Entonces [1,2], [2,3] etc. está bien?
Rɪᴋᴇʀ
@EasterlyIrk Sí.
murphy
Los bordes se pueden generar en cualquier orden, ¿verdad?
Luis Mendo
@DonMuesli Derecha.
murphy

Respuestas:

4

Jalea, 13 bytes

ạ/S’
2ṗœc2ÇÐḟ

Pruébalo aquí. Para la entrada 3, la salida es:

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

Espero que [1, 1, 1]etc. sea un "nombre" correcto.

Explicación

La primera línea es un "predicado" en un par de aristas: [A, B] ạ/S’es igual a sum(abs(A - B)) - 1, que es cero (falso-y) iff Ay Bdifiere exactamente en una coordenada.

La segunda línea es el programa principal:

  • Genere todos los bordes con 2ṗ(poder cartesiano de [1, 2]).
  • Obtenga todos los pares posibles usando œc2(combinaciones de tamaño dos sin reemplazo).
  • Mantenga solo elementos que satisfagan el predicado definido anteriormente ( ÐḟÇ).
Lynn
fuente
1
ạ/S’y 2ṗœc2ÇÐḟguardar un par de bytes.
Dennis
c/P=2, 2ṗṗ2ÇÐffunciona también.
Dennis
¡Esquema inteligente de "nombrar"! Ciertamente dentro de las reglas.
murphy
9

Python 2, 54 56 62 bytes

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

Los bordes duplicados se eliminan haciendo un conjunto de conjuntos, excepto que Python requiere que los elementos del conjunto sean hashables, por lo que se convierten en tuplas. Tenga en cuenta que los conjuntos {a,b}y {b,a}son iguales y convertir a la misma tupla. xsot guardó 2 bytes con n<<n.

Esto se puede reducir a 49 bytes si las cadenas de conjuntos son un formato de salida correcto

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

que da salida como

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]

Primero, veamos una versión anterior de la solución.

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

Cada número en el intervalo [0,2^n)corresponde a un vértice con coordenadas dadas por sus ncadenas binarias de bits. Los vértices son adyacentes si difieren en un solo bit, es decir, si uno se obtiene del otro al multiplicar una potencia de 2.

Esta función anónima genera todos los bordes posibles al voltear cada vértice y cada posición de bit. Para evitar duplicar un borde en ambas direcciones, solo los 1 se cambian a 0.

En la solución más golfizada, kse usa para codificar ambos iy jvía k=n*i+j, de los cuales (i,j)se puede extraer como (k/n,k%n). Esto ahorra un bucle en la comprensión. Los poderes de 2se realizan 1<<para tener la prioridad de operador correcta.

Un enfoque alternativo para generar cada par de vértices y verificar si están un poco volteados parece más largo (70 bytes):

lambda n:[(i,x)for i in range(2**n)for x in range(i)if(i^x)&(i^x)-1<1] 
xnor
fuente
1
n*2**nes solon<<n
xsot
Cambiando a Python 3.5, lambda n:{(*{k//n,k//n^1<<k%n},)for k in range(n<<n)}guarda un byte. (La expresión destacada ahorra tres, pero la sintaxis de división pierde dos). Sin embargo, estoy bastante seguro de que la solución de 49 bytes que tiene está bien.
Lynn
4

Mathematica, 48 24 bytes

EdgeList@*HypercubeGraph

Solo una función anónima que utiliza elementos integrados.

LegionMammal978
fuente
Ah, el incorporado! Como no tiene que nombrar los vértices alfabéticamente, puede omitir el FromLetterNumber. Incluso creo que EdgeList@*HypercubeGraphes una respuesta válida.
murphy
3

JavaScript (SpiderMonkey 30+), 69 64 bytes

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

Esto comenzó como un puerto de la solución Python 2 de @ xnor, pero pude guardar 9 bytes reescribiendo el código para usar un solo bucle. Editar: ahorró otros 5 bytes al dividirse ial revés, según la solución actualizada de @ xnor, que ahora también usa un solo bucle.

Neil
fuente
2

MATL , 20 bytes

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

Esto funciona con la versión actual (14.0.0) del lenguaje / compilador.

Pruébalo en línea!

Explicación

Esto usa más o menos la misma idea que la respuesta de @ 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
Luis Mendo
fuente
2

Pyth, 13 bytes

fq1.aT.c^U2Q2

Salida en la entrada 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]]]

Explicación:

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.
isaacg
fuente
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]
DolphinDream
fuente