Function Repository Resource:

OrderedTupleIndex

Source Notebook

Give the index of an ordered tuple

Contributed by: Ed Pegg Jr

ResourceFunction["OrderedTupleIndex"][tuple]

gives the index of the ordered tuple.

Details and Options

Ordered tuples are considered to be lists {a1,a2,,ak} such that the ai are non-negative and non-decreasing.
For any ordered tuple, a unique index n can be defined via .
For example, subset {1, 2, 2} has index .

Examples

Basic Examples (2) 

The following ordered 3-tuple sequence can be extended to infinity:

In[1]:=
ordered = SortBy[Union[Sort /@ Tuples[{0, 1, 2}, {3}]], Reverse]
Out[1]=

The function returns indices of one to ten for these ordered tuples:

In[2]:=
ResourceFunction["OrderedTupleIndex"] /@ ordered
Out[2]=

Any nondecreasing list of nonnegative integers can be considered as an ordered tuple with a unique index:

In[3]:=
ResourceFunction[
 "OrderedTupleIndex"] /@ {{101, 101, 101}, {6, 12, 27, 44}, {5, 5, 8, 9, 12, 20}, {0, 0, 102}, {6, 6, 20, 21, 27}, {1, 1, 102}, {2, 2, 102}, {12, 12, 27, 44}}
Out[3]=

The result above is an ordered tuple with a unique index:

In[4]:=
ResourceFunction["OrderedTupleIndex"][%]
Out[4]=

Scope (3) 

Here are some ordered 2-tuples with their indices to show their structure:

In[5]:=
doubles = # - {0, 1} & /@ SortBy[Subsets[Range[0, 5], {2}], Reverse];
Graphics[{Text[
     Style[Column[{StringJoin[ToString /@ #], ResourceFunction["OrderedTupleIndex"][#]},
       Alignment -> Center], 20], #] & /@ doubles, Blue, Line[doubles]}]
Out[5]=

The ordered 2-tuple {4,4} has an index of :

In[6]:=
Binomial[4 + 0, 1] + Binomial[4 + 1, 2] + 1
Out[6]=

OrderedTupleIndex returns the same thing:

In[7]:=
ResourceFunction["OrderedTupleIndex"][{4, 4}]
Out[7]=

The structure of ordered 3-tuples in 3D:

In[8]:=
triples = # - {0, 1, 2} & /@ SortBy[Subsets[Range[0, 5], {3}], Reverse];
Graphics3D[{Text[
     Style[Column[{StringJoin[ToString /@ #], ResourceFunction["OrderedTupleIndex"][#]},
       Alignment -> Center], 20], #] & /@ triples, Blue, Line[triples]}]
Out[8]=

Properties and Relations (3) 

Use Tuples to produce ordered 3-tuples:

In[9]:=
sortbyreverse = SortBy[Union[Sort /@ Tuples[Range[0, 2], {3}]], Reverse]
Out[9]=

The same sequence of ordered 3-tuples can be obtained from ordered Subsets:

In[10]:=
# - {0, 1, 2} & /@ SortBy[Subsets[Range[0, 4], {3}], Reverse]
Out[10]=

Indices of this sequence:

In[11]:=
ResourceFunction["OrderedTupleIndex"] /@ sortbyreverse
Out[11]=

Version History

  • 1.0.0 – 06 December 2019

Related Resources

License Information