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.
223241any 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}->5867the 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]:=
ResourceFunction["StandardOrderIndex"][{1, 2, 2, 1, 3, 2, 1}]
Out[1]=

Index of a larger standard order:

In[2]:=
ResourceFunction[
 "StandardOrderIndex"][{1, 2, 3, 2, 4, 4, 5, 6, 4, 5, 7, 1, 6, 8, 3, 3}]
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]:=
{BellB[12], Total[BellIndexing[12]], ResourceFunction["StandardOrderIndex"][Range[12]]}
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]:=
ran = RandomInteger[5, 14]
Out[5]=

Here is its index:

In[6]:=
ResourceFunction["StandardOrderIndex"][ran]
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]:=
ord = StandardOrderMap[ran]
Out[8]=

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

In[9]:=
ResourceFunction["StandardOrderIndex"][ord]
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]:=
s5 = StandardOrders[5]
Out[11]=

Give the indices of these standard orders:

In[12]:=
ResourceFunction["StandardOrderIndex"] /@ s5
Out[12]=

A particular standard order:

In[13]:=
ResourceFunction["StandardOrderIndex"][{1, 2, 1, 3, 1, 3, 1, 1}]
Out[13]=

Recover that data using the StandardOrders function:

In[14]:=
StandardOrders[8][[1500]]
Out[14]=

Find the index of a standard order:

In[15]:=
ResourceFunction["StandardOrderIndex"][{1, 2, 2, 1, 3, 2, 1, 4, 3}]
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}];

Here is how the function finds the index:

In[17]:=
start = {1, 2, 2, 1, 3, 2, 1, 4, 3};
highs = {1, 2, 0, 0, 3, 0, 0, 4, 0};
mixed = {0, 0, 2, 1, 0, 2, 1, 0, 3} // Select[#, # > 0 &] &;
radix = {0, 0, 2, 2, 0, 3, 3, 0, 4} // Select[#, # > 0 &] &;
binary = FromDigits[Sign[Drop[highs, 1]], 2];
totalBell = Total[Take[BellIndexing[9], binary]];
mixedradix = FromDigits[mixed - 1, MixedRadix[radix]];
totalBell + mixedradix + 1
Out[17]=

Possible Issues (2) 

For length n, 2n indices need to be generated, so this function will start slowing down at length 20:

In[18]:=
2^20
Out[18]=

There are lots of standard orders of length 20:

In[19]:=
BellB[20]
Out[19]=

Version History

  • 1.0.0 – 31 December 2019

Related Resources

License Information