1 | |
---|
2 | import sage.symbolic.random_tests |
---|
3 | |
---|
4 | |
---|
5 | |
---|
6 | def 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 | |
---|
75 | def 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 | |
---|