Hi Someone, > You are right. In my previous posts I used the word "transposition"
I had this misunderstanding a few times (me making the fuss :-\ ) But I see now that you say elementary transpositions. > Ok. But a general transposition can still be composed of > individual elementary ones and we can get the complicated > factor by combining the simple factors, no? Hm, that is a difficult question. In case of a group defined by generators and relations, if you can solve the word problem, then you can decide if two presentations of an element are identical. Note that a Hecke algebra is a generalization of the symmetric group (algebra). If you take elementary transpositions as generators, then things like length, parity etc _can_ be defined (and that is possibly what you want for `sorting'). Eg using q-symmetrizers you get q-Grassmann alegbras etc... > For the merge sort it may be less obvious. But we can get the > correct number of elementary transpositions by incrementing the > count not only by 1 but by a larger amount for each merge operation. I had a similar problem determining the correct sign in the Murnaghan Nakayama rule, and there a different representation of Young diagrams makes the counting much faster. You keep track for general transpositions how many elementary transpositions are needed to do them. > If I did not misunderstand you these sorting algorithms > are perfectly valid even for the generalized cases. Yes, where `general' does mean symmetric group, and alike structures such as Hecke algebras, ... > Maybe you have a simple example ready to try? I had somewhere experimental maple code, but I forgot/deleted it? However, your approach seems to work well anyhow ... Cheers BF. -- quam cito dictur, tam facile non fit! % Dr habil Bertfried Fauser % contact |-> URL : http://www.cs.bham.ac.uk/~fauserb/ % Phone : +44 7508593565 -- You received this message because you are subscribed to the Google Groups "FriCAS - computer algebra system" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/fricas-devel?hl=en.
