Hi, sorting generators (of a group or algebra) may be more tricky than you think. In case of the symmetric group, the `sign' is `-1' for a transposition, but a transposition can be elementary or not (changing adjacent or distant generators [sic: indices]). If you work in a slight generalization, say a Hecke algebra then you need to be more careful, as the `sign' in this case is `q`, and an elementary (!) transposition picks up a factor of 'q', while a general transposition can have a more elaborate factor (in general q-polynomials).
Hence it is worth writing code which does count elementary transpositions, as it will yield in the case q=-1 the correct symmetric group (q=1, just sorting) signs for transpositions used to form antisymmetrizers. In teh q-case you get q-symmetrizers as were used by Woronowicz in his definition of matrix pseudo (quantum) groups. Cheers BF. On Thu, Oct 25, 2012 at 12:31 AM, someone <[email protected]> wrote: >> > I'd like to propose a simple extension of the common >> > bubble sort algorithm. Sometimes it is necessary to >> > know how many exchanges took place during the sorting. >> > This is the case for example when working with skew-symmetric >> > expressions. Hence I would want to implement the following >> > function (names are up for discussion): >> > >> > countingBubbleSort : (A, (S, S) -> Boolean) -> Record(sorted:A, >> > exchanges:NNI) >> > >> > I know there is such a code in the Clifford Domain, >> > in the file "clifford.spad.pamphlet" at line 933ff. >> >> Hmm, I wonder about mathematical definition of your operation. >> 'CliffordAlgebra' and skew-symmetic operations use sign (parity), >> which is well defined. > > Yes. But the only essential thing I need to know > about is the number of transpositions and use this. > >> Counting exchanges gives length >> of some string of transpositions which mutiplied give >> sequence treated as a permutation. > > Yes. And I need to bring this specific permutation > back to the identity permutation. > >> There are some uses >> of length, but one has to be careful to compute it >> correctly, because using different string of transpositions >> can give different length. > >> It is not clear for me if bubble sort computes useful length or not. > > It does, because I need to adapt the overall sign of an > expression depending on the numbers of interchanges done > while putting it into canonical form. The transformation > has not to be unique but just well defined as long as > the result is unique. > > Another nice example would be creation and annihilation operators > in quantum mechanics. When we try to put a string of operators > into normal form, then the expression picks up a sign change > for each transposition done. > >> Concerning sign, we already have function to compute sign >> of a permutation. > > Could you maybe make an example of how to use this? > Is is possible to use this for general Lists with > arbitrary Elements and possibly a user specified > Order relation? > >> Computing sign and sorting together may be convenient >> for user and may serve as an optimization. > > It really is, although I admit the user case is special. > >> However, sign can be computed in linear time, sorting is >> n*log(n) while bubble sort is quadratic. > > Yes, in theory this is of course true. However this feature > is supposed to be used only for relatively short lists. > >> So using >> counting bubble sort for such optimization make sense only >> for very small n, which is the case for CliffordAlgebra >> but not for general case. > > Right. Despite this limitation I consider the feature > to be very useful. > > -- > 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. > -- 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.
