# Ticket #9880: strict_weak_order.py

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

Line | |
---|---|

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 |