Function Repository Resource:

IndexedSubset

Source Notebook

Give the index of a subset or return the subset with that index

Contributed by: Ed Pegg Jr

ResourceFunction["IndexedSubset"][choose,index]

returns a subset of length choose with given index.

ResourceFunction["IndexedSubset"][list]

gives the index of subset list.

Details and Options

For any positive integers n and k, n can be uniquely represented as k binomials, , where the aj terms are strictly increasing.

Examples

Basic Examples (2) 

The following 3-subset ordering can be extended to infinity:

In[1]:=
SortBy[Subsets[Range[0, 4], {3}], Reverse]
Out[1]=

The function returns the same subsets in the same order:

In[2]:=
Table[ResourceFunction["IndexedSubset"][3, index], {index, 1, 10}]
Out[2]=

The function can return subsets of a large index:

In[3]:=
sub3 = Table[
  ResourceFunction["IndexedSubset"][3, index], {index, 182000, 182400,
    47}]
Out[3]=

Applying the function to a subset returns the index:

In[4]:=
ResourceFunction["IndexedSubset"] /@ sub3
Out[4]=

Any strictly increasing list of integers can be considered as a subset with a unique index:

In[5]:=
ResourceFunction["IndexedSubset"][%]
Out[5]=

The index above generates a unique 9-subset:

In[6]:=
ResourceFunction["IndexedSubset"][9, %]
Out[6]=

Scope (4) 

Some binomial representations of the number 320:

In[7]:=
Column[Row[
    Riffle[Table[
      TraditionalForm[
       Binomial[(ToString /@ #)[[n]], ToString[n]]], {n, 1, Length[#]}], "+"]] & /@ Table[ResourceFunction["IndexedSubset"][n, 321], {n, 2, 7}], Alignment -> Center]
Out[7]=

Here are some two item subsets with their indices to show their structure:

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

The 2-subset {4,5} has an index of :

In[9]:=
Binomial[4, 1] + Binomial[5, 2] + 1
Out[9]=

Recover the same information using IndexedSubset:

In[10]:=
ResourceFunction["IndexedSubset"][2, 15]
Out[10]=

The structure of 3-subsets in 3D:

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

Neat Examples (2) 

Find the trillionth number with binary weight eight:

In[12]:=
Total[2^ResourceFunction["IndexedSubset"][8, 10^12]]
Out[12]=

Find the index of an eight-term subset:

In[13]:=
ResourceFunction["IndexedSubset"][{31, 37, 38, 47, 71, 95, 112, 122}]
Out[13]=

Version History

  • 1.0.0 – 06 November 2019

License Information