Ordering python sets

[Duncan Booth]

Peter Otten <__peter__ at web.de> wrote:

> Here's another one:
> 
>>>> set([1,9])
> set([1, 9])
>>>> set([9,1])
> set([9, 1])
> 
> This time I did indeed search systematically...
> 
You missed one with smaller values:
>>> set([8,0])
set([8, 0])
>>> set([0,8])
set([0, 8])

You can work some of it out quite easily instead of searching. The hash 
value for an integer is itself, the initial space allocated for the set is 
8 slots so each value is reduced modulo 8. If the values you insert don't 
clash then the order of insertion doesn't matter. If there are values which 
coincide on the same slot then the second one inserted will go into a 
different slot so the order may vary.

What Tim Chase has missed in his tests:
> s = set(r.randint(1,1000) for _ in range(1000))

is that to get the elements out of order at least one element must be 
larger than the number of allocated slots. Since there are always a lot of 
unused slots that means the range for the integers needs to be 
significantly greater than the number of integers.

e.g.
>>> set([128]+range(84))
set([128, 0, 2, 3, 4, 5, 6, 1, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 
19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 
38, 39, 40, 41, 42, 7, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 
57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 
76, 77, 78, 79, 80, 81, 82, 83, 43])
>>> set([128]+range(85))
set([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 
20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 
39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 
58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 
77, 78, 79, 80, 81, 82, 83, 84, 128])

the 86th element added to the set makes to total size allocated large 
enough that the 128 no longer conflicts with the 0.