The underlying data structure for sets doesn't lend itself to an
efficient method of random selection. It is best for the programmer to
explictly convert to a sequence and then make the random selection (that
way the conversion cost isn't hidden).
If you don't mind the inefficiency of an implicit conversion to a list,
you can use "random.sample(s, 1)". If only an arbitrary element is
needed, use "x=next(iter(s))" to non-destructively fetch the first element.
resolution: -> rejected
status: open -> closed
Thanks for the suggestions "random.sample(s, 1)" and
A counterpoint: isn't this a classic example of where polymorphism
enables a more elegant, simple, and clear (dare I say Pythonic)
approach? The complexity of allowing sets as inputs, even with a naive
implementation, is still O(n) even in the worst case vs. O(1) for
arrays. Isn't documenting that distinction good enough?
It's not: it's based on a hash table. It's essentially a dict with keys but no values. An additional complication is that the hash table can be very sparsely filled, in the case of a large set that has had most of its elements deleted---there's no automatic shrinkage of the hash table in that case. So repeated random selection until you find a filled hash table entry would be inefficient in that case.
Python has beautiful data structure semantics, and this is a stain in them.
An implementation based on the current underlying hash table is quite simple, just pick random addresses until an active key is found. Even on sparse tables this is probabilistic O(1). Even with average load factor = 50%, only 1 extra attempt is needed; 2 with LF as low as 33%.
I'm happy to provide a patch if anyone defines the desired API in Include/setobject.h .