Hypercube sides

Question

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)

Answer 1

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.

Answer 2

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

Answer 3

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

Answer 4

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.

Answer 5

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.