How to write a Python program that gives the same output in every run?

I have the following code

import random

random.seed(42)

mylist = set(["A", "B", "C", "D", "E", "F", "G", "H"]) 
tn = random.sample(mylist, 4)
print(tn)

So far I would have expected this to always print the same result. However, on every consecutive run it returns a different sequence of 4 letters. I later found that it is stable when removing set (which in this minimal example serves no purpose other than to trigger the problem).

Why would someone implement set in a way that it is not deterministic? I can imagine that its implementation may need (pseudo-)random numbers, but even then I'd have hoped that my program is still deterministic, even when using set. I also noticed that this is version-dependent:

Python versions:

• 2.7.12: stable
• 3.5.2: different output
• 3.6.12: different output

How can I use set and still get reproducible output? Sorting mylist with sorted before sampling works, but it's quite unintuitive that you have to sort a list that is sorted again after a (naively) null-operation.