12
\$\begingroup\$

Your job will be to write a function or a program, that will take an integer n>0 as input and output a list of the edges of the n-dimensional hypercube. In graph theory an edge is defined as a 2-tuple of vertices (or corners, if you prefer), that are connected.

Example 1

A 1-dimensional hypercube is a line and features two vertices, which we will call a and b.

enter image description here

Therefore, the output will be:

[[a, b]]

Example 2

The 4-dimensional hypercube (or tesseract) consists of 32 edges and its graph looks like this

enter image description here

and the output could look like this

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

Rules

  • You may name the vertices any way you like, as long as the name is unique.
  • The edges are undirected, i.e. [a, b] and [b, a] are considered the same edge.
  • Your output must not contain duplicate edges.
  • The output may be in any sensible format.
  • Standard loopholes are forbidden.

Scoring

Shortest code wins.

\$\endgroup\$
  • \$\begingroup\$ Related. Related. \$\endgroup\$ – Martin Ender Mar 16 '16 at 22:28
  • \$\begingroup\$ So [1,2], [2,3] etc. is okay? \$\endgroup\$ – Rɪᴋᴇʀ Mar 16 '16 at 22:36
  • \$\begingroup\$ @EasterlyIrk Yep. \$\endgroup\$ – murphy Mar 16 '16 at 22:38
  • \$\begingroup\$ Edges can be output in any order, right? \$\endgroup\$ – Luis Mendo Mar 16 '16 at 22:56
  • \$\begingroup\$ @DonMuesli Right. \$\endgroup\$ – murphy Mar 16 '16 at 23:01
4
\$\begingroup\$

Jelly, 13 bytes

ạ/S’
2ṗœc2ÇÐḟ

Try it here. For input 3, the output is:

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

I hope [1, 1, 1] etc. is an okay “name”.

Explanation

The first line is a “predicate” on a pair of edges: [A, B] ạ/S’ is equal to sum(abs(A - B)) - 1, which is zero (false-y) iff A and B differ in exactly one coordinate.

The second line is the main program:

  • Generate all edges with 2ṗ (Cartesian power of [1, 2]).
  • Get all possible pairs using œc2 (combinations of size two without replacement).
  • Keep only elements satisfying the predicate defined earlier (ÐḟÇ).
\$\endgroup\$
  • 1
    \$\begingroup\$ ạ/S’ and 2ṗœc2ÇÐḟ save a couple of bytes. \$\endgroup\$ – Dennis Mar 17 '16 at 2:42
  • \$\begingroup\$ c/P=2, 2ṗṗ2ÇÐf works too. \$\endgroup\$ – Dennis Mar 17 '16 at 3:30
  • \$\begingroup\$ Smart "naming" scheme! Certainly within the rules. \$\endgroup\$ – murphy Mar 18 '16 at 17:40
9
\$\begingroup\$

Python 2, 54 56 62 bytes

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

Duplicate edges are removed by making a set of sets, except Python requires that set elements are hashable, so they are converted to a tuples. Note that the sets {a,b} and {b,a} are equal and convert to the same tuple. xsot saved 2 bytes with n<<n.

This can be cut down to 49 bytes if strings of sets are an OK output format

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

which gives output like

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]

First, let's look at an older version of the solution.

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

Each a number in the interval [0,2^n) corresponds to a vertex with coordinates given by its n-bit binary strings. To vertices are adjacent if they differ in a single bit, i.e. if one is obtained from the other by xor-ing a power of 2.

This anonymous function generates all possible edges by taking every vertex and every bit position to flip. To avoid duplicating an edge in both directions, only 1's are flipped to 0's.

In the more golfed solution, k is used to encode both i and j via k=n*i+j, from which (i,j) can be extracted as (k/n,k%n). This saves a loop in the comprehension. The powers of 2 are done as 1<< to have the right operator precedence.

An alternative approach of generating each pair of vertices and checking if they are a bit flip apart seems longer (70 bytes):

lambda n:[(i,x)for i in range(2**n)for x in range(i)if(i^x)&(i^x)-1<1] 
\$\endgroup\$
  • 1
    \$\begingroup\$ n*2**n is just n<<n \$\endgroup\$ – xsot Mar 17 '16 at 3:20
  • \$\begingroup\$ Switching to Python 3.5, lambda n:{(*{k//n,k//n^1<<k%n},)for k in range(n<<n)} saves a byte. (The starred expression saves three, but the division syntax loses two.) However, I'm pretty sure the 49-byte solution you have is fine. \$\endgroup\$ – Lynn Mar 17 '16 at 17:51
4
\$\begingroup\$

Mathematica, 48 24 bytes

EdgeList@*HypercubeGraph

Just an anonymous function that uses built-ins.

\$\endgroup\$
  • \$\begingroup\$ Ah, the built-in! As you don't have to name the vertices alphabetically, you can omit the FromLetterNumber. I even think EdgeList@*HypercubeGraph is a valid answer. \$\endgroup\$ – murphy Mar 18 '16 at 17:45
3
\$\begingroup\$

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

This started out as a port of @xnor's Python 2 solution but I was able to save 9 bytes by rewriting the code to use a single loop. Edit: Saved a further 5 bytes by splitting i up the other way around, as per @xnor's updated solution, which now also uses a single loop.

\$\endgroup\$
2
\$\begingroup\$

MATL, 20 bytes

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

This works with current version (14.0.0) of the language/compiler.

Try it online!

Explanation

This uses more or less the same idea as @xnor's answer.

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
\$\endgroup\$
2
\$\begingroup\$

Pyth, 13 bytes

fq1.aT.c^U2Q2

Output on input 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]]]

Explanation:

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.
\$\endgroup\$
1
\$\begingroup\$

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]
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.