Is set.pop() deterministic?

The answer in general is no. The python source that @Christophe and @Marcin (un)helpfully point to shows that elements are popped in the order they appear in the hash table. So, pop order (and presumably iteration order) is deterministic, but only for fixed hash values. That's the case for numbers but not for strings, according to the Note in the documentation of __hash__, which incidentally also touches on your question directly:

Note by default the hash() values of str, bytes and datetime objects are “salted” with an unpredictable random value. Although they remain constant within an individual Python process, they are not predictable between repeated invocations of Python.

[ ... ]

Changing hash values affects the iteration order of dicts, sets and other mappings. Python has never made guarantees about this ordering (and it typically varies between 32-bit and 64-bit builds).

Edit: As @Marcin points out, the link I quoted does not apply to Python 2. Hash randomization became the default with Python 3.3. Python 2.7 does not have intentionally non-deterministic string hashing by default.

In general, this is a problem for any object whose hash is not a repeatable function of its value (e.g., if the hash is based on memory address). But conversely, if you define your own __hash__ method for the objects in your sets, you can expect that they will be returned in a reproducible order. (Provided the set's history and the platform are kept fixed).

The documentation does not specify that it must be deterministic, therefore you should assume that it isn't.

Internally I think the situation is similar to dict. The order is determined by an hash algorithm, which in some situations will yield the same results. But you should not depend on that, since once the number of elements gets large, the set will encounter collisions (that is it's internal hashing), which eventually lead to a different ordering.

In short: No, set.pop() is not deterministic. Don't assume any order, since the API explicitly states, that

a set object is an unordered collection

• Docs: http://docs.python.org/library/stdtypes.html#set-types-set-frozenset
• Source: http://svn.python.org/view/python/trunk/Objects/setobject.c?view=markup

If you want to force determinism, you could try something like

value = min(my_set)
my_set.remove(value)