List Archives >
Maple User Group List Archive >
Archive by date >
This Month By Date >
This Month By Topic
[MUG] Re: sorting alphanumeric lists
| [MUG] Re: sorting alphanumeric lists |
|
Author: Maple User Group
Posted: Fri, 22 Nov 2002 16:39:38 -0500
|
>> From: Maple User Group "maple_gr"
-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-
Date: Wed, 20 Nov 2002 13:46:30 -0800 (PST)
From: Michael Monagan "mmonagan"
To: maple-list "maple-list"
Subject: sorting alphanumeric lists
>I have a problen in sorting object. Maple provides two buildin functions
>sort and lexorder, which are pretty fast. I need to compare two lists, to
>compute the number of transpositions of a permutation (which are needed
>for keelping track of some q-factors in q-deformed symmetric groups).
=======
You need to use Maple trick number 2.
Use the antisymmetric indexing function for a table as follows.
> L := [1,3,2,4];
L := [1, 3, 2, 4]
> T := table(antisymmetric);
T := table(antisymmetric, [])
> T[op(L)];
-T[1, 2, 3, 4]
> L := [1,3,4,2];
L := [1, 3, 4, 2]
> T[op(L)];
T[1, 2, 3, 4]
The result is of type indexed <==> L is an even permutation,
i.e. and even number of transpositions are required.
Michael Monagan
----------------------------------------------------------------
Dr. Michael Monagan,
Department of Mathematics, Tel: (604) 291-4279
Simon Fraser University, Fax: (604) 291-4947
Burnaby, BC, CANADA V5A 1S6 e-mail: "monagan"
-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-
Date: Tue, 19 Nov 2002 16:26:14 -0800 (PST)
From: Robert Israel "israel"
To: maple-list "maple-list"
Subject: sorting alphanumeric lists
I'm somewhat puzzled, and would like to see a concrete example where
lexorder gives a wrong answer on integers turned into names. Are you
sure the problem isn't simply that lexicographic order is different
from numerical order? For example, `10` comes before `9` in lexicographic
order.
Robert Israel "israel"
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia
Vancouver, BC, Canada V6T 1Z2
-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-
From: Joe Riel "joer"
To: "maple-list"
Date: Wed, 20 Nov 2002 11:53:02 -0800
Subject: sorting alphanumeric lists
Maple does have a random permutation generator, combinat[randperm].
It uses the shuffling algorithm of Fisher and Yates discussed
in Knuth [1]. As mentioned there, this method will generate at most
p distinct permutations, where p is the modulus of the linear
congruential generator. For Maple (R8), p = 999999999989.
So, for permutations with more than 13 elements, some permutations
will never arise.
The method that Bertfried uses [to generated a random permutation]
appears to be O(n*log(n)), though for large n I suspect that this
goes to O(n^2) because list building in Maple is O(l), where l
is the length of the list. Combinat[randperm] is O(n).
The perm_num_of_tr function appear to have a few errors.
First, the comparison is being
done between items on the same list (only the lenght of lst1 is used).
Did you mean
perm_num_of_tr:=proc(lst1,lst2)
local i,j;
nops(select(evalb,[seq(seq((lst2[j]>lst1[j]),
j=i+1..nops(lst2)),
i=1..nops(lst1))]))
end proc
Also, the commented out line (not shown above) is definitely wrong;
lexorder(""||lst2[j],""||lst2[i]) should work (aside from the previous
comment). Finally, the algorithm above is definitely flawed.
Swapping the two arguments gives different results.
Do you really need to know the number of transpositions between permutations?
Or is it just the relative parity that interests you?
If the latter, there are fast ways of getting that.
Joe Riel
[1] Donald E. Knuth, "The Art of Computer Programming,"
Vol 2. Seminumerical Algorithms, Third Edition, Addison Wesley.
|
[View Complete Thread]
Previous by date: [MUG] animation problems, Bertfried Fauser
Next by date: [MUG] problems with subs(), Charles James Leonardo Quarra Cappiello
Previous thread: [MUG] ODE with singularity, Jens-Uwe Herrmann
Next thread: [MUG] problems with subs(), Charles James Leonardo Quarra Cappiello
|
(NAG)
