Ticket #9880: strict_weak_order.py

File strict_weak_order.py, 3.6 KB (added by vbraun, 10 years ago)

Randomized testing of orders

Line 
1
2import sage.symbolic.random_tests 
3
4
5
6def assert_strict_weak_order(a,b,c, cmp_func):
7    r"""
8    Checks that ``cmp_func`` is a strict weak order.
9
10    A strict weak order is a binary relation ``<`` such that
11
12    * For all `x`, it is not the case that `x < x` (irreflexivity).
13
14    * For all `x\not=y`, if `x < y` then it is not the case that `y <
15      x` (asymmetric).
16
17    * For all `x`, `y`, and `z`, if `x < y` and `y < z` then `x < z`
18      (transitivity).
19
20    * For all `x`, `y`, and `z`, if x is incomparable with `y`, and
21      `y` is incomparable with `z`, then `x` is incomparable with `z`
22      (transitivity of equivalence).
23
24    INPUT:
25   
26    - ``a``, ``b``, ``c`` -- anything that can be compared by ``cmp_func``.
27
28    - ``cmp_func`` -- function of two arguments that returns their
29      comparison (i.e. either ``True`` or ``False``).
30
31    OUTPUT:
32
33    Does not return anything. Raises a ``ValueError`` if ``cmp_func``
34    is not a strict weak order on the three given elements.
35
36    REFERENCES:
37
38    http://en.wikipedia.org/wiki/Strict_weak_ordering
39   
40    EXAMPLES::
41
42        sage: a, b, c = [ randint(-10,10) for i in range(0,3) ]
43        sage: assert_strict_weak_order(a,b,c, lambda x,y: x<y)
44    """
45    x = (a,b,c)
46    cmp = matrix(3,3)
47    indices = list(CartesianProduct(range(0,3),range(0,3)))
48    for i,j in indices:
49        cmp[i,j] = (cmp_func(x[i], x[j]) == 1)   # or -1, doesn't matter
50    msg = 'The binary relation failed to be a strict weak order on the elements\n'
51    msg += ' a = '+str(a)+'\n'
52    msg += ' b = '+str(b)+'\n'
53    msg += ' c = '+str(c)+'\n'
54    msg += str(cmp)
55
56    for i in range(0,3):   # irreflexivity
57        if cmp[i,i]: raise ValueError, msg
58       
59    for i,j in indices:    # asymmetric
60        if i==j: continue
61        #if x[i] == x[j]: continue
62        if cmp[i,j] and cmp[j,i]: raise ValueError, msg
63           
64    for i,j,k in Permutations([0,1,2]):   # transitivity
65        if cmp[i,j] and cmp[j,k] and not cmp[i,k]: raise ValueError, msg
66
67    def incomparable(i,j):
68        return (not cmp[i,j]) and (not cmp[j,i])
69    for i,j,k in Permutations([0,1,2]):   # transitivity of equivalence
70        if incomparable(i,j) and incomparable(j,k) and not incomparable(i,k): raise ValueError, msg
71
72
73
74
75def test_symbolic_expression_order(repetitions=100):
76    r"""
77
78    Tests whether the comparison of random symbolic expressions
79    satisfies the strict weak order axioms.
80
81    This is important becasue the C++ extension class uses
82    ``std::sort()`` which requires a strict weak order. See also
83   
84    http://trac.sagemath.org/sage_trac/ticket/9880
85   
86    EXAMPLES:
87     
88        sage: test_symbolic_expression_order(200)
89        sage: test_symbolic_expression_order(10000)  # long time
90    """
91    rnd_length = 50
92    nvars = 10
93    ncoeffs = 10
94    var_frac = 0.5
95    nullary_frac = 0.05
96
97    def coeff_generator():
98        return randint(-100,100)/randint(1,100)
99
100    def make_random_expr():
101        while True:
102            try:
103                return sage.symbolic.random_tests.random_expr(
104                    rnd_length, nvars=nvars, ncoeffs=ncoeffs, var_frac=var_frac, 
105                    nullary_frac=nullary_frac, coeff_generator=coeff_generator,
106                    internal=sage.symbolic.random_tests.fast_nodes)
107            except (ZeroDivisionError, ValueError):
108                pass
109   
110    for rep in range(0, repetitions):
111        a = make_random_expr()
112        b = make_random_expr()
113        c = make_random_expr()
114        assert_strict_weak_order(a, b, c, lambda x,y: x._cmp_(y))
115        assert_strict_weak_order(a, b, c, lambda x,y: x._cmp_add(y))
116        assert_strict_weak_order(a, b, c, lambda x,y: x._cmp_mul(y))
117
118
119
120
121
122
123