an element from a set

[Carl Banks]

On May 14, 11:52 pm, Chris Rebert <c... at rebertia.com> wrote:
> On Fri, May 14, 2010 at 11:23 PM, Carl Banks <pavlovevide... at gmail.com> wrote:
> > On May 14, 9:39 am, Terry Reedy <tjre... at udel.edu> wrote:
> >> On 5/14/2010 11:24 AM, gerardob wrote:
> >> > Hello, let S be a python set which is not empty
> >> > (http://docs.python.org/library/sets.html)
>
> >> > i would like to obtain one element (anyone, it doesn't matter which one) and
> >> > assign it to a variable.
>
> >> > How can i do this?
>
> >> Depends on whether or not you want the element removed from the set
>
> >> #3.1
> >>  >>> s=set(range(10))
> >>  >>> s
> >> {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
> >>  >>> x=next(iter(s))
> >>  >>> x
> >> 0
> >>  >>> s
> >> {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} # x not removed
> >>  >>> x = s.pop()
> >>  >>> x
> >> 0
> >>  >>> s
> >> {1, 2, 3, 4, 5, 6, 7, 8, 9} # x has been removed
>
> >> The choice of 0 is an implementation artifact. It could have been any
> >> member.
>
> > Which brings up an interesting question: how do you get a random
> > element from a set?
>
> > random.choice(list(s))
>
> > is the most straightforward way and will work a lot of the time, but
> > how would you avoid creating the list?  I can't think of a way off
> > hand.
>
> def random_set_elem(s):
>     iterator = iter(s)
>     n = random.randint(0, len(s)-1)
>     for i in xrange(n):
>         next(iterator)
>     return next(iterator)
>
> Avoids creating the list, but it's still O(M). If you're gonna pick
> multiple times from the same set, you're better off just converting it
> to a list.

I've never had to do it (at least not in any situations where I had
any reluctance to call list on it), but it seems like a fairly bad
limitation.  Random element from a set is such a natural idea.

Even if we were to modify the set type at the C level to support it, I
can't think of an easy way to get a random element without selection
bias.  For instance, if you start from a random hash code, some
elements are more likely to be selected than others, depending on
distance between entries in the hash table.  You'd probably have to
choose an number in range(len(s)) and count off that many, but then
might as well have just converted it to a list or used an iterator.  A
little disappointing, actually.

Probably the "right" way is to use a binary-tree-based set.


Carl Banks