Re: sorting problems

[Karim Belabas <Karim.Belabas@math.u-psud.fr>]

* John Cremona [2004-09-30 11:01]:
> I'm having trouble searching for an element in a (sorted) vector/list of 
> positive integers in GP.  Using vecsort I can sort the vector and keep 
> the associated permutation;  but the only searching function is 
> setsearch() which requires the list to be a set.  It converts the object 
> being searched for into a string but not the list itself.  If you 
> convert the list into a set then another permutation is applied (since 
> lexicographical order is not the same as numerical order!) but not 
> recorded...
> 
> trivial example:  3<12 but "12"<"3" :
> 
> (09:32) gp > a=[12,3]
> %122 = [12, 3]
> (09:40) gp > ia=vecsort(a,,1)
> %123 = [2, 1]
> (09:40) gp > sa=vecextract(a,ia)
> %125 = [3, 12]
> (09:41) gp > setsearch(sa,12)
> %126 = 0
> (09:41) gp > setsearch(Set(sa),12)
> %127 = 1
> (09:41) gp > Set(sa)
> %128 = ["12", "3"]
> (09:41) gp > setsearch(Set(sa),3)
> %130 = 2
> 
> All I need in the end is:  given a (large) vector [x_1,x_2,...,x_n] of 
> (unsorted) integers, I want to be able to ask of any integer x if x=x_i 
> for some i and of so which....surely a common task!

You may build your list using a combination of setsearch / listinsert:

\\ to insert an object x in list L:
  x = Str(x);
  j = setsearch(L, x, 1);
  if (!j, listinsert(L, x));

Or something like this (untested).

    Karim.
-- 
Karim Belabas                     Tel: (+33) (0)1 69 15 57 48
Dep. de Mathematiques, Bat. 425   Fax: (+33) (0)1 69 15 60 19
Universite Paris-Sud              http://www.math.u-psud.fr/~belabas/
F-91405 Orsay (France)            http://pari.math.u-bordeaux.fr/  [PARI/GP]