Ordinal transform

Definition

The ordinal transform of a sequence $a=(a_{0},a_{1},a_{2},...)$ is the sequence ${\rm {ORD}}(a)=(c_{0},c_{1},c_{2},...)$ with

$c_{n}=\#\{\,k\in D_{a}\mid k\leq n\land a_{k}=a_{n}\,\}{\text{ for all }}n\in D_{a}=\{\,0,1,2,...\,\}\ ,$

i.e., the number of times the value $a_{n}$ appears in $(a_{0},...,a_{n})$.

In the above, $D_{a}$ is the domain of the sequence a, i.e., the set of indices: If we consider a sequence $a=(a_{1},a_{2},a_{3},...)$ instead, then $D_{a}=\{\,1,2,3,...\,\}$.

Examples

A004736 = (1, 2,1, 3,2,1, 4,3,2,1, ...) is the ordinal transform of A002260 = (1, 1,2, 1,2,3, 1,2,3,4, ...)

A001511 = (1,2, 1,3, 1,2, 1,4, ...), the ruler function (2-adic valuation of 2n), is the ordinal transform of A003602 = (1, 1, 2, 1, 3, 2, 4, 1, 5, ...): a(n) = k if n = (2k-1)*2^m, or limiting fixed point of T(1) where T(a,b,c,...) = (1,a,2,b,3,c,4...).

Programs

The transform is possible in linear time by incrementing a specific counter for each value.

Maple

(Maple)
ORDINAL := proc(a) local count, x;
             count := table(sparse);       # undefined entries are zero by default
             [seq( ++ count[x], x in a)];  # ++var is an expression, not a statement like var += 1
           end;

(Maple) # From N. J. A. Sloane, Apr 09 2020:
ORDINAL:=proc(a) local b,t1,tlist,clist,n,t,nt;
  if whattype(a) <> list then RETURN([]); fi:
    t1:=nops(a);
    tlist:=[];
    clist:=Array(1..t1,0);
    b:=[]; nt:=0;
    for n from 1 to t1 do t:=a[n];
      if member(t,tlist,'p') then clist[p] := clist[p]+1; b:=[op(b),clist[p]];
      else nt:=nt+1; tlist:=[op(tlist),t]; clist[nt]:=1; b:=[op(b),1]; fi;
    od:
    b; 
  end;

PARI/GP

(PARI)
ORDINAL(a, c=Map())=[mapput(c,x, a=iferr(mapget(c,x),a,)+1)+a | x <- a]}

Remarks:

• mapput() returns an empty result, evaluating to 0, to which the newly computed and stored value a = c[x] is added, in order to use just one single expression. (Alternatively, one could use [a=..., mapput(c,x,a)][1].)
• Instead of iferr(...) which returns 0 in case an error is raised when x isn't yet in the dictionary c, one might also use if(mapisdefined(c, x ,&a), a), but in addition to being bit lengthier it appears also to be slightly slower.
• Once the provided value of a = [a₁, ..., a_n] has been used as domain over which runs the variable x, the same variable name a is used within the "loop" to temporarily store the updated values c[x]. This is just to avoid introduction of another variable.

Python

(Python)
def ORDINAL(a): c={}; return[c.setdefault(x, c.pop(x,0)+1) for x in a]

It may look inefficient to discard the dictionary entry c[x] and to re-create just afterwards, instead of just incrementing its value. However, incrementing a variable is a statement and can't be used as expression for the values of the resulting list. The only way to avoid this is to increment that dictionary's entry in an auxiliary function, as for example:

(Python)
def inc(c,x): t=c.get(x,0)+1; c[x]=t; return t  # using t avoids accessing c[x] 3 times: about 1.25 times faster
def ORDINAL(a): c={}; return[inc(c,x) for x in a]

As we see this also requires accessing the dictionary's entry c[x] at least twice. Unless removing the entry c[x] generates much overhead, the second solution isn't more efficient than the first. For example, for a sequence a of length 1000, the first solution takes about 75% and the second solution takes 80% of the CPU time of the solution using def inc(c,x): c[x]=c.get(x,0)+1; return c[x] (or equivalently using the function c.update(x=...) which returns None).

Cite as

M. F. Hasler, Ordinal transform.— From the On-Line Encyclopedia of Integer Sequences® Wiki (OEIS® Wiki). [https://oeis.org/wiki/Ordinal_transform]. Initial version created on April 9, 2020.