| 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 | |
|---|
