Re: veccount

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

* Ruud H.G. van Tol [2022-12-29 13:04]:
> A different case:
> 
> ? binary(92)
> %3 = [1, 0, 1, 1, 1, 0, 0]
> 
> How to effectively transform that to [1,1,3,2] (run-lengths),
> and next to 3 (the number of different run-length values)?

Note that Rosetta Code includes lots of PARI/GP snippets for standard
programming tasks, e.g.,

  https://rosettacode.org/wiki/Run-length_encoding#PARI/GP

> ? {
>   my(D= 1, v= binary(92), c= 1, x= v[1],r= List());
>   if(D,print(v));
>   for(i= 2, #v, if(x == v[i], c++;if(i == #v,listput(r,c)),
> listput(r,c);c=1;x=v[i]));
>   r= Vec(r); if(D,print(r));
>   r= matreduce(r)[,1]~; if(D,print(r));
>   print(#r);
> }
> [1, 0, 1, 1, 1, 0, 0]
> [1, 1, 3, 2]
> [1, 2, 3]
> 3
> 
> Only the last result is relevant to A165413,
> so a condensed way from binary(92) to 3 would already help,

Something like

  /* assume v is a non-empty vector */
  rlev(v) =
  { my(x = v[1], c = 1, L = List());
    for (i = 2, #v, if (v[i] == x, c++, listput(L,c); x = v[i]; c = 1));
    listput(L,c); #Set(L);
  }

  ? rlev(binary(92))
  %2 = 3

  ? setrand(1); v = vector(10^6, i, random(2));
  ? rlev(v)
  time = 894 ms.
  %4 = 20

One can save a log factor by using a counting sort to replace the list L
and final #Set(L):

  /* assume v is a non-empty vector */
  rlev2(v) =
  { my(x = v[1], c = 1, w = vector(#v));
    for (i = 2, #v, if (v[i] == x, c++, w[c] = 1; x = v[i]; c = 1));
    w[c] = 1; hammingweight(w);
  }

  ? rlev2(v)
  time = 437 ms.
  %5 = 20

Cheers,

    K.B.

--
Karim Belabas  /  U. Bordeaux,  vice-président en charge du Numérique
Institut de Mathématiques de Bordeaux UMR 5251 - (+33) 05 40 00 29 77
http://www.math.u-bordeaux.fr/~kbelabas/
`