# Hypercube sides

Your goal is to output all the "sides" (corners, edges, faces, etc.) of an N-dimensional unit hypercube, where N is non-negative. A "side" is defined as any (N-M)-dimension surface embedded in N-dimensional space, where 1 <= M <= N.

The hypercube spans the space [0, 1] in each dimension. For example, for N=2 the square is bounded by the corner points (0, 0) and (1, 1).

# Input

Your function/program should take a single non-negative integer N. You may assume N <= 10.

# Outputs

The output may be to any convenient format desired: return a list, print to stdio/file, output parameters, etc.

The output must contain the min/max bounds of all unique sides. Order does not matter.

Example sides formats

A 0D side (a.k.a. a point) in 3D space could be bounded by:

# in [(min0, max0),...] format, this is the point 0,1,0
[(0, 0), (1, 1), (0, 0)]


A 1D side (a.k.a. an edge) in 2D space could be bounded by:

# in [(min0, min1,...), (max0, max1,...)] format, this is the line from point (0,0) to (1,0)
[(0, 0), (1, 0)]


Note that it is ok to flatten the output any way you want ([min0, max0, min1, max1, ...] or [min0, min1, min2, ..., max0, max1, max2, ...], etc.)

Wikipedia has a list of the number of sides to expect for various hypercubes. In total, there should be 3N-1 results.

Full sample outputs

This uses the convention [min0, max0, min1, max1, ...]

N = 0

empty list (or no output)


N = 1

[0, 0]
[1, 1]


N = 2

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


N = 3

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


# Scoring

This is code golf; shortest code wins. Standard loop-holes apply. You may use built-in functions like "permute a sequence" so long as it wasn't designed specifically for this problem.

Your code should run in a reasonable amount of time for N <= 6 (say, 10 minutes or less)

• Please, someone make something visual. That's what hypercubes are for Jan 19, 2016 at 12:25
• you said but you may use. Did you mean you may use or you may not use?
– Blue
Jan 19, 2016 at 12:26
• functions like permute/cartesian product are allowed. Jan 19, 2016 at 21:39

## Pyth, 10 chars

P^cj49J2JQ


Try it here. Output is a list of sides each in the format. [[min0, max0],[min1, max1],...].

P             All but the last element of
^       Q     the nth cartesian power of
j49J2        the number 49 as a binary list [1,1,0,0,0,1]
c     J         split into chunks of 2 [[1,1],[0,0],[0,1]]


In our output, we want all lists of n elements from [[1,1],[0,0],[0,1]], except the one with only [0,1]'s. This is just the nth cartesian power of [[1,1],[0,0],[0,1]] with the last element removed.

The list [[1,1],[0,0],[0,1]] is created by converting 49 into binary and breaking into chunks of 2. One can do .CU2 2 to get [[0,0],[0,1],[1,1] as all sorted sublists of 2 elements from [0,1], but we need [0,1] at the start or end to remove the list with only it from the product.

## CJam (13 bytes)

49Yb2/rim*);


Online demo

Output format is as a list of list of ranges: e.g. for input 1 (where the two sides are the points (0, 0) and (1, 1)) the output is [[[1 1]] [[0 0]]].

### Dissection

49Yb2/   e# Generate the list of ranges: [[1 1] [0 0] [0 1]]
rim*     e# Take the nth Cartesian power
);       e# Remove the last one, which is the full hypercube
e# Format for output


# Ruby, 66 63

Returns an array of strings, each one containing 2n 0s and 1s without separators.

->n{(0..3**n-2).map{|i|s=""
n.times{s+="0011"[-i%3,2];i/=3}
s}}


In a similar way to at at least one other answer it generates all possibilities of ["00","11","01"] repeated n times, except "0101....0101", by iterating through all the n-digit base 3 numbers 00..00 to 22..21 (deliberately missing 22..22) and then substituting. Initially I had the string "011101" ("01" had to be at the end) but then I realised if I fed -i instead of i to the %3 operation, I could swap the 2 and 1. I was then able to reduce the string to "0011", overlapping the three possible 2-character strings I required.

Ungolfed in test program

f=->n{
(0..3**n-2).map{|i|            #iterate through all n-digit base 3 numbers 00..00 to 22..21
s=""
n.times{                     #for each base 3 digit in i append the following to s
s+="0011"[-i%3,2]          #0 --> 0 -->"00";   -1 --> 2 --> "11";   -2 --> 1 --> "01"
i/=3                       #divide by 3 to remove the last base 3 digit from i
}
s                            #add s to the array being built by map.
}
}

puts f[gets.to_i]


Output n=2

0000
1100
0100
0011
1111
0111
0001
1101


## CJam, 24 bytes

2ri2*m*{2/__:$=\2,a-*},p  Uses the same interleaved [min0 max0 min1 max1 ...] format as the test cases in the challenge. It solves N = 10 in a couple of minutes. Test it here. ### Explanation 2 e# Push a 2. ri e# Read input and convert to integer N. 2* e# Multiply by 2. m* e# Get all 2N-tuples consisting of 0 and 1 as potential sides. A tuple is a valid e# side if a) all of its min/max pairs are sorted and b) not all of them are [0 1], e# because that corresponds to the entire N-dimensional hypercube. { e# Filter the tuples... 2/ e# Split the tuple into min/max pairs. __ e# Make two copies. :$   e#   Sort each pair in the second copy.
=    e#   Check for equality with the first copy.
\    e#   Swap with the original list of pairs.
2,a- e#   Remove all [0 1].
*    e#   Repeat this array 0 or 1 times depending on the first result. This effectively
e#   computes the logical AND of two truthy/falsy values.
},
p      e# Pretty-print the list of sides.


## ES7, 88 bytes

n=>[...Array(3**n-1)].map((_,i)=>[...(3**n+i).toString(3).slice(1)].map(x=>[x%2,+!!x]))


Turns out I ended up porting the Ruby solution, except I return a list of an array of a pair of bounds for each dimension, since that makes for the shortest code.