Seu trabalho será escrever uma função ou um programa que aceitará um número inteiro n>0como entrada e produzirá uma lista das bordas do hipercubon dimensional . Na teoria dos grafos, uma aresta é definida como duas tuplas de vértices (ou cantos, se você preferir), que estão conectados.

Exemplo 1

Um hipercubo unidimensional é uma linha e apresenta dois vértices, que chamaremos de ae b.

Portanto, a saída será:

[[a, b]]

Exemplo 2

O hipercubo 4-dimensional (ou tesseract) consiste em 32 arestas e seu gráfico se parece com este

e a saída pode ficar assim

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

Regras

• Você pode nomear os vértices da maneira que quiser, desde que o nome seja exclusivo.
• As arestas são não dirigida, ou seja, [a, b]e [b, a]são consideradas a mesma vantagem.
• Sua saída não deve conter arestas duplicadas.
• A saída pode estar em qualquer formato sensível.
• As brechas padrão são proibidas.

Pontuação

O menor código vence.

Gelatina, 13 bytes

ạ/S’
2ṗœc2ÇÐḟ

Experimente aqui. Para entrada 3, a saída é:

[[[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. seja um bom "nome".

Explicação

A primeira linha é um "predicado" em um par de arestas: [A, B] ạ/S’é igual a sum(abs(A - B)) - 1, que é zero (falso-y) se Ae Bdifere exatamente em uma coordenada.

A segunda linha é o programa principal:

• Gere todas as arestas com 2ṗ(potência cartesiana de [1, 2]).
• Obtenha todos os pares possíveis usando œc2(combinações de tamanho dois sem substituição).
• Mantenha apenas elementos que satisfaçam o predicado definido anteriormente ( ÐḟÇ).

Python 2, 54 56 62 bytes

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

As arestas duplicadas são removidas através da criação de um conjunto de conjuntos, exceto que o Python exige que os elementos do conjunto sejam laváveis, para que sejam convertidos em tuplas. Observe que os conjuntos {a,b}e {b,a}são iguais e convertem na mesma tupla. O xsot salvou 2 bytes com n<<n.

Isso pode ser reduzido para 49 bytes se as sequências de conjuntos forem um formato de saída OK

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

o que dá saída 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]

Primeiro, vejamos uma versão mais antiga da solução.

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

Cada número no intervalo [0,2^n)corresponde a um vértice com coordenadas dadas por suas ncadeias binárias de bits. Os vértices são adjacentes se diferirem em um único bit, ou seja, se um é obtido do outro xorando uma potência de 2.

Essa função anônima gera todas as arestas possíveis, usando todos os vértices e todas as posições de bits para inverter. Para evitar duplicar uma aresta nas duas direções, apenas 1 é invertido para 0.

Na solução mais golfe, ké usado para codificar tanto ie jvia k=n*i+j, a partir do qual (i,j)pode ser extraído como (k/n,k%n). Isso economiza um loop na compreensão. Os poderes de 2são feitos 1<<para ter a precedência correta do operador.

Uma abordagem alternativa de gerar cada par de vértices e verificar se estão um pouco afastados parece mais longa (70 bytes):

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

Apenas uma função anônima que usa built-ins.

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

Isso começou como uma porta da solução Python 2 do @ xnor, mas consegui salvar 9 bytes reescrevendo o código para usar um único loop. Editar: salvou mais 5 bytes dividindo io contrário, conforme a solução atualizada do @ xnor, que agora também usa um único loop.

MATL , 20 bytes

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

Isso funciona com a versão atual (14.0.0) do idioma / compilador.

Experimente online!

Explicação

Isso usa mais ou menos a mesma idéia que a resposta do @ 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

Pitão, 13 bytes

fq1.aT.c^U2Q2

Saída na 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]]]

Explicação:

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]