Is Python set ordered or not? [Answered: Not]

Question

Today I encounter a challenge with following question:

What is the output?
a = {3, 2, 1}
b = [1, 2, 3]
print(list(a) == b)
Choices: True or False
Answer: True

BUT, isn't set is unordered?
It is what w3cschools says:
Unordered
Unordered means that the items in a set do not have a defined order.
Set items can appear in a different order every time you use them, and cannot be referred to by index or key.
https://www.w3schools.com/JUMP_LINK__&&__python__&&__JUMP_LINK/python_sets.asp

Even in the official documentation, it also says "A set is an unordered collection with no duplicate elements."
https://docs.python.org/3/tutorial/datastructures.html?highlight=set

If set is unordered, why list(a) == b evaluated to True?

Answer 1

I like this thread, especially how you guys started investigating the documentation, and just adding my 2 cents.

See more background info here:
https://stackoverflow.com/questions/15479928/why-is-the-order-in-dictionaries-and-sets-arbitrary

The internal change in CPython occured in 3.6 related to the listing order of dict keys. Sets are still not affected by this.

We need to distinguish between language specification (Python) and interpreter implementation (CPython). Since the observed automatic sorting of integer values in a set, is never mentioned in the spec, it is an incidental implementation detail that should not be relied upon. Set elements are always listed in "unspecified" order, it is not up to us to understand the details, but from developer's point it should be considered random.

Answer 2

Python sets, like dictionaries, are unordered data structures.
In the more recent Python versions, they are implemented to retain a certain order.

Answer 3

Here is an interesting observation, because it seems that numbers are ordered and automatically sorted in a set, but it doesn't apply to strings and letters.

https://code.sololearn.com/cRR8Ya11IvJv/?ref=app

Answer 4

Wong Hei Ming ,

Then it's my opinion that Ryu made a mistake when creating the challenge by thinking that the repeatable behavior he observed in the particular implementation of Python that Sololearn runs is guaranteed across all implementations, and you are right to question it.

Unless @Lisa does cite something to the contrary, I'm sticking to everything I've read so far, which says sets are unordered.

Now, of course, if you print a set, or copy it to a list, it must at least temporarily have an order, but that order is going to be whatever is convenient for the implementation, and not a reliable property of sets in general, unless they change it in a future Python Enhancement Proposal (PEP).

By the way, you don't need to dump full text copies of the documentation into the thread. A few snippets and a link is good, so people can go check it themselves. A paste without a link is essentially hearsay anyway.

Answer 5

Wong Hei Ming your analogy is more or less correct. The different implementations of Python are for example IronPython, JPython, and PyPy. It does not really depend on the platform (although there can be also minor differences in implementation details between the same python interpreter running on Linux vs Windows... the IDE does not matter here because it is just a powerful text editor).

Answer 6

Rain
It seems not.
I made 3 extra sets to the existing code. First 2 have 20 elements in 20, 1, 19, 2 fashion, both sorted automatically,
When it comes to 33, 11, 22, 55 it behave differently.

Anyway I made a report yesterday.
At least future reader of this post know the sorting behavior is not reailable.

Answer 7

More searching deepen the mystery.

From the official documentation:
Lists may be constructed in several ways:
Using a pair of square brackets to denote the empty list: []
Using square brackets, separating items with commas: [a], [a, b, c]
Using a list comprehension: [x for x in iterable]
Using the type constructor: list() or list(iterable)
The constructor builds a list whose items are the same and in the same order as iterable’s items. iterable may be either a sequence, a container that supports iteration, or an iterator object. If iterable is already a list, a copy is made and returned, similar to iterable[:]. For example, list('abc') returns ['a', 'b', 'c'] and list( (1, 2, 3) ) returns [1, 2, 3]. If no argument is given, the constructor creates a new empty list, [].

The first sentence:
The constructor builds a list whose items are the same and in the same order as iterable’s items.
Plus wording from w3cschools:
Set items can appear in a different order every time you use them, and cannot be referred to by index or key.

list(a) is a constructor method, a is a set.
I ran the code in question with a loop range of 100 and always yield True.

Is it a undocumented feature?

Answer 8

The documentation link I posted is pointing to version 3.12 at the moment, and explained set is an unordered collection.
The next section is about Dictionary and indeed it says:
Performing list(d) on a dictionary returns a list of all the keys used in the dictionary, IN INSERTION ORDRE (if you want it sorted, just use sorted(d) instead). To check whether a single key is in the dictionary, use the in keyword.

So I made a little code to check the Python version in playground and the behavior of dict and set.
It seems set is acting funny… It sorted the initial set but not sequence insertion.
https://code.sololearn.com/c8Ws068jXT12/?ref=app

Answer 9

It is how the document written (direct copy from PC):

Set Types — set, frozenset

A set object is an unordered collection of distinct hashable objects. Common uses include membership testing, removing duplicates from a sequence, and computing mathematical operations such as intersection, union, difference, and symmetric difference. (For other containers see the built-in dict, list, and tuple classes, and the collections module.)

Like other collections, sets support x in set, len(set), and for x in set. Being an unordered collection, sets do not record element position or order of insertion. Accordingly, sets do not support indexing, slicing, or other sequence-like behavior.

There are currently two built-in set types, set and frozenset. The set type is mutable — the contents can be changed using methods like add() and remove(). Since it is mutable, it has no hash value and cannot be used as either a dictionary key or as an element of another set. The frozenset type is immutable and hashable — its contents cannot be altered after it is created; it can therefore be used as a dictionary key or as an element of another set.

Non-empty sets (not frozensets) can be created by placing a comma-separated list of elements within braces, for example: {'jack', 'sjoerd'}, in addition to the set constructor.

Answer 10

Quantum ,

Interesting. The ordering is probably a byproduct of whatever algorithm the implementation uses to ensure that there are no duplicates. Still, just because an order must be chosen by the implementation when printing a set, it doesn't mean the set concept is ordered or that the chosen order is guaranteed across implementations.

Answer 11

Tibor Santa
I'm not sure I'm following correctly. So Python language specification is like a description of a car, it has 4 wheels, can turn left and right, and can move forward and backward. And the interpreter implementation is like a car maker, the maker decide the car is manual or automatic, but ultimately the finished product can do everything as the specification required?
So a sorted integer values in a set when cast into a list is a "by product" (not mentioned in the spec) from CPython (car maker), so we cannot assume it will be sorted too in other interpreter (such as some IDE on mobile?)
As such, the question I encountered is questionable?

Answer 12

Quantum ,

Yes. It's interesting that a set of single-digit int items seems to always get printed in low to high order, while a set of str items doesn't. However, I noticed {11, 22, 33} or {111, 222, 333} don't either.

I didn't mean to imply you thought sets were ordered. Obviously you don't, since your code demonstrates unordered str items. I reiterated that sets are unordered in that message, as here, so no random reader accidentally gets an incomplete picture.

The Python "language specification" says sets are unordered. Python "implementation details" can have arbitrary behavior that make some sets seem to be ordered in some scenarios. Programmers 😇 should rely only on the language specifications. Hackers 👹 might exploit the implementation details.

Answer 13

Wong Hei Ming ,

It's only a single-digit int implementation effect.

Changed to below, it prints False for me. I tried it on Pydroid3 (Android Python IDE), since I can't get to the Sololearn playground while writing a comment.

a = {33, 22, 11}
b = [11, 22, 33]
print(list(a) == b)

I think I read on another discussion that the Community challenges were frozen a while (years?) ago, which unfortunately means mistakes can't be corrected.

Answer 14

I made a little test, and it seems that sets are automatically sorted from lowest to higest when converted to a list.

Answer 15

Quantum, I ran it in a loop for 100 times and the results are all True.
By definition the logical answer is False yet in practice is True, that's why I made a post.

Answer 16

Lisa ,

Can you cite that? I don't see it.

https://docs.python.org/3/library/stdtypes.html#set

Answer 17

Wong Hei Ming ,

What challenge was that? AI hallucinates. Humans make mistakes.

Answer 18

Rain, it was a community code challenge. The question is made by Ryu.

Answer 19

Rain I never said that set was totally ordered, but when it comes to numbers, I just keep getting the same ordered output no matter how many times I print it, but I definitely don't get an ordered output of strings and letters.

Answer 20

Rain Okay, I can see that it only creates a stable sorted order from low to high with single-digits.