Issue #29371: merge with 3.5

1 files changed, 21 insertions, 1 deletions

diff --git a/Lib/test/test_set.py b/Lib/test/test_set.py
index 7594303132..0202981d67 100644
--- a/Lib/test/test_set.py
+++ b/Lib/test/test_set.py
@@ -6,10 +6,11 @@ import operator
 import copy
 import pickle
 from random import randrange, shuffle
-import sys
 import warnings
 import collections
 import collections.abc
+import itertools
+import string
 
 class PassThru(Exception):
     pass
@@ -729,6 +730,25 @@ class TestFrozenSet(TestJointOps, unittest.TestCase):
             addhashvalue(hash(frozenset([e for e, m in elemmasks if m&i])))
         self.assertEqual(len(hashvalues), 2**n)
 
+        def zf_range(n):
+            # https://en.wikipedia.org/wiki/Set-theoretic_definition_of_natural_numbers
+            nums = [frozenset()]
+            for i in range(n-1):
+                num = frozenset(nums)
+                nums.append(num)
+            return nums[:n]
+
+        def powerset(s):
+            for i in range(len(s)+1):
+                yield from map(frozenset, itertools.combinations(s, i))
+
+        for n in range(18):
+            t = 2 ** n
+            mask = t - 1
+            for nums in (range, zf_range):
+                u = len({h & mask for h in map(hash, powerset(nums(n)))})
+                self.assertGreater(4*u, t)
+
 class FrozenSetSubclass(frozenset):
     pass