Function Repository Resource:

StandardOrderIndex

Source Notebook

Get the index of a list of integers in standard order

Contributed by: Ed Pegg Jr

ResourceFunction["StandardOrderIndex"][list]

gives the index of a list of integers in standard order.

Details and Options

Integers >0 in standard order start with 1, then can never be more than 1 higher than all previous integers.

The index is acquired by first noting the positions of the highest numbers to make a binary number.

The table below illustrates the process for determining an index for a standard order:

{1,2,2,1,3,2,1,4,3}

integers >0 in standard order start with 1, then can never be more than 1 higher than all previous integers.

{1,2,0,0,3,0,0,4,0}

some of the digits are new highest digits.

{0,0,2,1,0,2,1,0,3}

other digits acquire a mixed radix based on the previous highest digit.

{1,0,0,1,0,0,1,0}

without the initial 1, the sequence of highest digits mapped to 1 values makes a binary number B.

2²3²4¹

any binary number with 1's→{2,…,n} and sequential zeros acting as powers gives a Bell index.

BellB[n]

equals the sum of Bell indices of length n-1 binary numbers.

{146, 86}->5867

the total of the first B Bell indices plus the mixed radix value gives the index.

The input follows the "standard order" described in the OEIS.

Examples

Basic Examples (2)

Find the index of a standard order:

In[1]:=

Out[1]=

Index of a larger standard order:

In[2]:=

Out[2]=

Scope (4)

Define a Bell indexing function:

In[3]:=

$BellIndexing[ n_] := (Times @@ MapIndexed[#2[[1]]^(#1 - 1) & , Differences[Flatten[{1, Position[#1, 1] + 1, n + 1}]]] & ) /@ Table[IntegerDigits[k, 2, n - 1], {k, 0, 2^(n - 1) - 1}]$

The total number of standard orders of length n is given by BellB[n] or the total of the Bell indices with the last standard order being Range[n]:

In[4]:=

Out[4]=

If a list isn’t in standard order it will be put into standard order before the indexing. Here is a random list:

In[5]:=

Out[5]=

Here is its index:

In[6]:=

Out[6]=

Define a standard ordering function:

In[7]:=

$StandardOrderMap[list_List] := Module[{alphabet}, alphabet = DeleteDuplicates[Flatten[list]]; list /. Thread[alphabet -> Range[Length[alphabet]]]]$

Order the random list:

In[8]:=

Out[8]=

Compare the index of the unordered version with that of the ordered one:

In[9]:=

Out[9]=

Some auxiliary functions:

In[10]:=

$GrowStandardOrder[order_, s_] := Module[{max}, max = Min[Max[order] + 1, s]; Append[order, #] & /@ Range[max]]; StandardOrders[len_] := SortBy[Nest[Flatten[GrowStandardOrder[#, len] & /@ #, 1] &, {{1}}, len - 1], FromDigits[ Sign[Table[ If[#[[n]] > Max[Take[#, n - 1]], #[[n]], 0], {n, 2, Length[#]}]], 2] &];$

Here are the 52 standard orders of length 5:

In[11]:=

Out[11]=

Give the indices of these standard orders:

In[12]:=

Out[12]=

A particular standard order:

In[13]:=

Out[13]=

Recover that data using the StandardOrders function:

In[14]:=

Out[14]=

Find the index of a standard order:

In[15]:=

Out[15]=

Define a Bell indexing function:

In[16]:=

$BellIndexing[n_] := Times @@ MapIndexed[#2[[1]]^(#1 - 1) &, Differences[Flatten[{1, Position[#, 1] + 1, n + 1}]]] & /@ Table[IntegerDigits[k, 2, n - 1], {k, 0, 2^(n - 1) - 1}];$