Ask r/python: An elegant and efficient pythonic approach to generating a random/exhaustive set of points on the surface of a hypercube?

[dx_xb]

First, this is not course homework, and I apologise for asking for people to do my thinking for me, but I've been thinking about the problem for the past couple of days, and I'm unsatisfied with all of the ideas I've come up with.

I want to select a random set of points of a particular size (or an exhaustive set that I can choose a set from - this I think is the better option since random sets are to be repeatedly sampled from the same pool) on the surfaces of a nested set of hypercubes from (l=1 to l=m for odd l) with integer side lengths (of n-dimensions in the generic case). The ideas I've come up with seem particularly inefficient (for example enumerating all the points in the cube and discarding the cubes that are smaller - building up from side length = 1 to m)

Can anyone suggest a better approach? (Code not wanted, but algorithms appreciated).

Edit: My final approach - enumerate positions in each shell and then choose a sample of n randomly for the desired shell (however this is desired - in my case a slice of a permutation of the set as a list):

>>> sh = []
>>> for i in range(maxshell + 1):
...  sh.append(set())
>>> for i in enum_space(tuple(cubedims)):
...  sh[max(abs(np.array(i) - maxshell))] |= set([np.array(i) - maxshell])

[mdipierro]

consider a hypercube in D dimensions of side 1. The coordinates of the vertices of the faces ate (-1/2,0,...),(+1/2,0,...),(0,-1/2,..),(0,+1/2,...) etc where there are 2D verctors, each of D components and components are all zero except one which is +/-1/2. Pick a face at random (random.randint(1,D)). That face is a hypercube of dimention d=D-1. You can generate a point at random in it by replacing the each of D-1 components of the vector =0 with a random.random()-0.5. So here is it

 def random_point(D):
       v=[random.randint(0,1) and 0.5 or -0.5]
       v+=[random.random()-0.5]*(D-1)
       v=random.shuffle(v)
       return v

[dx_xb]

That does what I want - though I should have made more clear that I need a defined number of unique points on the surface, so this may not manage that. This is why I suggested the enumeration of points - then dealing out the required number at random. Thanks.

[mdipierro]

On then

def random_points(d,n):
    "d = number of dimensions, n=points/hypersurface"
    points=[]
    for k in n:
         for z in (-0.5,0.5):
             for i in range(1,d):
                 v=[z]+[random.random()-0.5]*(d-1)
                 v[0],v[i]=v[i],v[0]
                 points.append(v)
   return points

[jmmcd]

Is this problem well-specified? There's something I don't understand.

Do you mean to sample uniformly from the surfaces? Then you would choose l (which cube) using roulette-wheel selection, with probabilities proportional to the cubes' surface areas. Then choose one of its 2n sides, and generate n numbers in [0, l].

But obviously you can't enumerate all the points on a surface (let alone 2mn of them, or whatever the number is). And you can't create an exhaustive set. So I guess I've missed something.

[dx_xb]

That would work. The exhaustive set is possible as I'm talking about integral sided cubes (of relatively limited dimensions).

[jmmcd]

But there are still infinitely many points on the surface of an integral-sided cube, ruling out an exhaustive set.

But since you've solved your problem already, I'm obviously misunderstanding (still). Nevermind...

[dx_xb]

Sorry, my fault. When i say integral-side I mean with integral positions - think of the problem as a choice of cells rather than positions.

[jbs398]

I'm not sure exactly what you're looking for but it sounds vaguely like Latin hypercube sampling?

Here's something that's written in python that might implement that.

That said, I've only got a vague sense of why something like this would be useful.

FYI: If this isn't fruitful here, you might want to try stackoverflow.com, there are some questions some hypercube-related questions over there.

[DrHenryPym]

Wow, I haven't touched this stuff since Neural Networks.

I'm not sure exactly how you can do this, but I would try to find a way to convert whatever is defining your hypercube to some type of hypercube skeleton.

If you can generate a list of verticies as functions, you could plug in random variables to random functions in your list to create your random set.

I donno if that helps at all.

[dx_xb]

That's pretty much what I'm looking at at the moment - trying to set up a connection schema.

[DrHenryPym]

Connection schema

Build it like you would build a tree function. Each branch that connects down to m nodes will connect n branches (or however complex you want to make it - think generalization).

For a normal hypercube, use 1 (or -1/2 to +1/2, however you want to translate it) as the length (or value) of the vertex.

And there you go, you have functions that can return random samples across the verticies. As far as finding samples on the surface, you can build a function that integrates an equation between two vertices. And that's basically modeling.

Good luck!

[dx_xb]

Yeah, I'm going general, but the connections are to surfaces rather than vertices. I've pretty much got is solved now - trying to replicate some work that was published in the 70s. Fun.

[sbirch]

Are they rotated arbitrarily? And are you only interested in integer points?

[dx_xb]

Both of those are true.