How to generate (enumerate) 2**N tuples representing all vertices of unit hypercube in N-dimensional

Discussion in 'Python' started by Dr. Colombes, Jan 4, 2006.

  1. Dr. Colombes

    Dr. Colombes Guest

    I'm looking for a good Python way to generate (enumerate) the 2**N
    tuples representing all vertices of the unit hypercube in N-dimensional
    hyperspace.

    For example, for N=4 the Python code should generate the following 2**N
    = 16 tuples:

    (1,1,1,1), (1,1,1,-1),
    (1,1,-1, 1), (1,1,-1,-1),
    (1,-1,1,1), (1,-1,1,-1),
    (1,-1,-1, 1), (1,-1,-1,-1),
    (-1,1,1,1), (-1,1,1,-1),
    (-1,1,-1, 1), (-1,1,-1,-1),
    (-1,-1,1,1), (-1,-1,1,-1),
    (-1,-1,-1, 1), (-1,-1,-1,-1)

    Maybe converting each integer in the range(2**N) to binary, then
    converting to bit string, then applying the "tuple" function to each
    bit string?

    Thanks for your help.
    Dr. Colombes, Jan 4, 2006
    #1
    1. Advertising

  2. Dr. Colombes

    Paul Rubin Guest

    "Dr. Colombes" <> writes:
    > I'm looking for a good Python way to generate (enumerate) the 2**N
    > tuples representing all vertices of the unit hypercube in N-dimensional
    > hyperspace.
    > For example, for N=4 the Python code should generate the following 2**N
    > = 16 tuples:


    Here's a recursive generator:

    def hypercube(ndims):
    if ndims == 0:
    yield ()
    return
    for h in 1, -1:
    for y in hypercube(ndims-1):
    return (h,)+y


    >>> print list(hypercube(4))


    [(1, 1, 1, 1), (1, 1, 1, -1), (1, 1, -1, 1), (1, 1, -1, -1), (1, -1,
    1, 1), (1, -1, 1, -1), (1, -1, -1, 1), (1, -1, -1, -1), (-1, 1, 1, 1),
    (-1, 1, 1, -1), (-1, 1, -1, 1), (-1, 1, -1, -1), (-1, -1, 1, 1), (-1,
    -1, 1, -1), (-1, -1, -1, 1), (-1, -1, -1, -1)]
    >>>


    > Maybe converting each integer in the range(2**N) to binary, then
    > converting to bit string, then applying the "tuple" function to each
    > bit string?


    Yeah you could do that too.
    Paul Rubin, Jan 4, 2006
    #2
    1. Advertising

  3. Dr. Colombes wrote:
    > Maybe converting each integer in the range(2**N) to binary, then
    > converting to bit string, then applying the "tuple" function to each
    > bit string?


    A direct translation of that:

    def perm(n):
    rv = []
    for i in xrange(2L**n):
    cur = []
    for j in range(n):
    cur.append(1-2*(bool(i & (1<<j))))
    # cur is in reversed order LSB first, but as you seemingly don't
    # care about order of the returned tuples, this is irrelevant.
    rv.append(tuple(cur))
    return rv

    modelnine@phoenix ~ $ python
    Python 2.4.2 (#1, Dec 22 2005, 17:27:39)
    [GCC 4.0.2 (Gentoo 4.0.2-r2, pie-8.7.8)] on linux2
    Type "help", "copyright", "credits" or "license" for more information.
    >>> from test1 import perm
    >>> perm(5)

    [(1, 1, 1, 1, 1), (-1, 1, 1, 1, 1), (1, -1, 1, 1, 1), (-1, -1, 1, 1, 1), (1,
    1, -1, 1, 1), (-1, 1, -1, 1, 1), (1, -1, -1, 1, 1), (-1, -1, -1, 1, 1), (1,
    1, 1, -1, 1), (-1, 1, 1, -1, 1), (1, -1, 1, -1, 1), (-1, -1, 1, -1, 1), (1,
    1, -1, -1, 1), (-1, 1, -1, -1, 1), (1, -1, -1, -1, 1), (-1, -1, -1, -1, 1),
    (1, 1, 1, 1, -1), (-1, 1, 1, 1, -1), (1, -1, 1, 1, -1), (-1, -1, 1, 1, -1),
    (1, 1, -1, 1, -1), (-1, 1, -1, 1, -1), (1, -1, -1, 1, -1), (-1, -1, -1, 1,
    -1), (1, 1, 1, -1, -1), (-1, 1, 1, -1, -1), (1, -1, 1, -1, -1), (-1, -1, 1,
    -1, -1), (1, 1, -1, -1, -1), (-1, 1, -1, -1, -1), (1, -1, -1, -1, -1), (-1,
    -1, -1, -1, -1)]
    >>>

    modelnine@phoenix ~ $

    --- Heiko.
    Heiko Wundram, Jan 4, 2006
    #3
  4. Dr. Colombes

    Paul Rubin Guest

    Heiko Wundram <> writes:
    > def perm(n):
    > rv = []
    > for i in xrange(2L**n):
    > cur = []
    > for j in range(n):
    > cur.append(1-2*(bool(i & (1<<j))))
    > # cur is in reversed order LSB first, but as you seemingly don't
    > # care about order of the returned tuples, this is irrelevant.
    > rv.append(tuple(cur))
    > return rv


    def perm(n):
    return [tuple([(1,-1)[(t>>i)%2] for i in xrange(n)])
    for t in xrange(2L**n)]

    >>> perm(4)

    [(1, 1, 1, 1), (-1, 1, 1, 1), (1, -1, 1, 1), (-1, -1, 1, 1), (1, 1,
    -1, 1), (-1, 1, -1, 1), (1, -1, -1, 1), (-1, -1, -1, 1), (1, 1, 1,
    -1), (-1, 1, 1, -1), (1, -1, 1, -1), (-1, -1, 1, -1), (1, 1, -1, -1),
    (-1, 1, -1, -1), (1, -1, -1, -1), (-1, -1, -1, -1)]
    >>>
    Paul Rubin, Jan 4, 2006
    #4
  5. Paul Rubin wrote:
    > def perm(n):
    > return [tuple([(1,-1)[(t>>i)%2] for i in xrange(n)])
    > for t in xrange(2L**n)]


    or replace that with:

    def perm(n):
    return (tuple(((1,-1)[(t>>i)%2] for i in xrange(n)))
    for t in xrange(2L**n))

    to get a generator like in Paul's first example. Only works with Python 2.4+
    though.

    --- Heiko.
    Heiko Wundram, Jan 4, 2006
    #5
  6. Re: How to generate (enumerate) 2**N tuples representing all verticesof unit hypercube in N-dimensional hyperspace ?

    Heiko Wundram wrote:
    > Paul Rubin wrote:
    >
    >>def perm(n):
    >> return [tuple([(1,-1)[(t>>i)%2] for i in xrange(n)])
    >> for t in xrange(2L**n)]

    >
    >
    > or replace that with:
    >
    > def perm(n):
    > return (tuple(((1,-1)[(t>>i)%2] for i in xrange(n)))
    > for t in xrange(2L**n))
    >
    > to get a generator like in Paul's first example. Only works with Python 2.4+
    > though.
    >
    > --- Heiko.


    Isn't this kind of coding beeing the result of suffering from the
    post-pyContest illness syndrom?

    Or is there another reason behind writing it that way sacrificing
    readability like usage of less CPU time to run the code?

    Or am I alone having trouble to read this kind of code because not
    experienced enough in writing Python scripts?

    Claudio
    Claudio Grondi, Jan 4, 2006
    #6
  7. Dr. Colombes

    Guest

    Dr. Colombes wrote:
    > I'm looking for a good Python way to generate (enumerate) the 2**N
    > tuples representing all vertices of the unit hypercube in N-dimensional
    > hyperspace.
    >
    > For example, for N=4 the Python code should generate the following 2**N
    > = 16 tuples:
    >
    > (1,1,1,1), (1,1,1,-1),
    > (1,1,-1, 1), (1,1,-1,-1),
    > (1,-1,1,1), (1,-1,1,-1),
    > (1,-1,-1, 1), (1,-1,-1,-1),
    > (-1,1,1,1), (-1,1,1,-1),
    > (-1,1,-1, 1), (-1,1,-1,-1),
    > (-1,-1,1,1), (-1,-1,1,-1),
    > (-1,-1,-1, 1), (-1,-1,-1,-1)
    >
    > Maybe converting each integer in the range(2**N) to binary, then
    > converting to bit string, then applying the "tuple" function to each
    > bit string?
    >
    > Thanks for your help.


    Is this just a special case for the list of list combine() function
    posted not long ago ?

    def combine_lol(seq):
    return reduce(lambda x,y: (a+(b,) for a in x for b in y), seq,
    [()])

    list(combine_lol([(1,-1)]*4))
    , Jan 4, 2006
    #7
  8. Claudio Grondi wrote:
    > Heiko Wundram wrote:
    >> def perm(n):
    >> return (tuple(((1,-1)[(t>>i)%2] for i in xrange(n)))
    >> for t in xrange(2L**n))

    >
    > Isn't this kind of coding beeing the result of suffering from the
    > post-pyContest illness syndrom?


    I don't think what Paul Rubin posted is the sign of pyContest illness, as I
    use two-level generator expressions such as this quite often in my code.
    Why I didn't give this as the reponse to the OP was because it seems that
    he's not that familiar with Python to be able to read this efficiently and
    grap the concept behind the implementation immediately, that's why I
    thought an explicit loop was in order.

    But for any sufficiently advanced Python coder, I don't think this is
    unreadable in the least.

    --- Heiko.
    Heiko Wundram, Jan 4, 2006
    #8
  9. Dr. Colombes

    Dr. Colombes Guest

    Paul, Heiko:

    Thank you for the quality, parsimony and promptness of your
    excellent suggestions.

    I wasn't familiar with the Python "yield" function.

    Dr. Colombes
    Dr. Colombes, Jan 4, 2006
    #9
  10. Re: How to generate (enumerate) 2**N tuples representing all verticesof unit hypercube in N-dimensional hyperspace ?

    Heiko Wundram wrote:
    > Claudio Grondi wrote:
    >
    >>Heiko Wundram wrote:
    >>
    >>>def perm(n):
    >>> return (tuple(((1,-1)[(t>>i)%2] for i in xrange(n)))
    >>> for t in xrange(2L**n))

    >>
    >>Isn't this kind of coding beeing the result of suffering from the
    >>post-pyContest illness syndrom?

    >
    >
    > I don't think what Paul Rubin posted is the sign of pyContest illness, as I
    > use two-level generator expressions such as this quite often in my code.
    > Why I didn't give this as the reponse to the OP was because it seems that
    > he's not that familiar with Python to be able to read this efficiently and
    > grap the concept behind the implementation immediately, that's why I
    > thought an explicit loop was in order.
    >
    > But for any sufficiently advanced Python coder, I don't think this is
    > unreadable in the least.
    >
    > --- Heiko.

    List comprehension is a nice thing when standalone.
    I am usually able to read it from the left to the right and understand
    directly.
    But with nested list comprehensions I don't see directly what is going
    on, because there are more than one identifier I don't know about at the
    time of reading the expression and I am forced to read the entire
    nestings with eventually some more code spread over it. The trouble is,
    that there are no visual hints toward understanding of the used
    algorithm like it is the case in the non-list-comprehension version and
    I usually have to re-read the nested list comprehension from the right
    to the the left in order to get the idea. I don't want to be forced to
    read from the right to the left as I am used to read left-right,
    top-down and I expect any text (also source code) to be that way.
    Similar critics comes sometimes up when someone learns the German
    language, because you are forced to read also a very, very long sentence
    up to its end, before it is clear what is the action. I consider it as a
    problem which would be nice to get rid of if possible, but it is much
    easier to try to influence coding style than the usage of a language.

    Can usage of deep (i.e. more than two levels) nested list comprehensions
    be considered bad coding style?

    Claudio
    Claudio Grondi, Jan 4, 2006
    #10
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. George Sakkis
    Replies:
    1
    Views:
    450
    Szabolcs Nagy
    Jan 29, 2007
  2. Replies:
    3
    Views:
    179
    Horst Duchene
    Apr 20, 2005
  3. Replies:
    2
    Views:
    119
    Horst Duchene
    Feb 6, 2006
  4. Replies:
    0
    Views:
    114
  5. Jon Reyes
    Replies:
    18
    Views:
    228
    Mitya Sirenef
    Feb 19, 2013
Loading...

Share This Page