Ordering Products

Bernhard Holzmayer Holzmayer.Bernhard at deadspam.com
Mon Jul 18 03:06:14 EDT 2005

Kay Schluehr wrote:

> Now lets drop the assumption that a and b commute. More general: let be
> M a set of expressions and X a subset of M where each element of X
> commutes with each element of M: how can a product with factors in M be
> evaluated/simplified under the condition of additional information X?
> It would be interesting to examine some sorting algorithms on factor
> lists with constrained item transpositions. Any suggestions?

Hello Kay,

take this into account:
Restrictions like commutativity, associative, distributive and flexibility
laws don't belong neither to operands nor to operators themselves.
Instead these are properties of fields (set of numbers with respect to a
certain operation).
For a famous example for a somewhat "alternative" behaviour look at the
Octonions (discovered in 1843 by Graves and 1845 by Cayley), which are not
associative with respect to addition and/or multiplication.
(http://en.wikipedia.org/wiki/Octonions) or the Quarternions, which are
non-commutative (http://en.wikipedia.org/wiki/Quaternion)

Obviously, it's not correct to say: addition is associative, or, that
multiplication is. With the same right, you could say, multiplication is
not associative.
With the same reasoning, we can show that it's not easy to generalize
sorting, commutation, association or distribution mechanisms.

Maybe it would be a very fascinating goal to solve your algorithmic approach
in such a limited environment like the Quarternions.
A solution for this set of numbers, if achieved in a clean, mathematically
abstract way, should hold for most other numbers/fields too, natural and
real included.

I guess that the approach might be this way:
- define/describe the fields which shall be handled
- define/describe the rules which shall be supported
- find methods to reduce sequences of operations to simple binary or unary
operations (tokens) - this may introduce brackets and stacking mechanisms
- a weighing algorithm might be necessary to distinguish between plain
numbers and place holders (variables)
- application of the distributivity (as far as possible) might help to find
a rather flat representation and a base for reordering according to the
weights of the individual sub-expressions

Nevertheless, there are lots of commercial programs which do such sort of
symbolic mathematics, and which would badly fail when it would come to such
awkward fields like Quarternions/Octonions.


More information about the Python-list mailing list