Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 NthSubset

Source Notebook

Get the subset of a list for a given index

Contributed by: Wolfram Staff (original content by Sriram V. Pemmaraju and Steven S. Skiena)

ResourceFunction["NthSubset"][n,list]

gives the nth subset of list in canonical order.

Examples

Basic Examples (1) 

The first 16 subsets of a list:

In[1]:=
Table[ResourceFunction["NthSubset"][n, {a, b, c, d}], {n, 0, 15}]
Out[1]=

Properties and Relations (3) 

NthSubset does not sort its input, so the ordering of subsets is based on positions in the original list:

In[2]:=
Table[ResourceFunction["NthSubset"][n, Reverse@{a, b, c, d}], {n, 0, 15}]
Out[2]=

The 69,381st subset returned by Subsets:

In[3]:=
Subsets[Range[20], All, {69381}]
Out[3]=

Or by the zero-indexed NthSubset:

In[4]:=
ResourceFunction["NthSubset"][69381 - 1, Range[20]]
Out[4]=

The ordering of subsets is based on length (smaller subsets come first), followed by lexicographic list positions. This is not the fastest ordering for computing subsets:

In[5]:=
Timing[t1 = Table[ResourceFunction["NthSubset"][j, Range[20]], {j, 2^20}];]
Out[5]=

A faster enumeration can be attained if one imposes only lexicographic position ordering:

In[6]:=
kthSubset[k_Integer, ll_List] := Pick[ll, IntegerDigits[k - 1, 2, Length@ll], 1];
In[7]:=
Timing[t2 = Table[kthSubset[j, Range[20]], {j, 2^20}];]
Out[7]=

Check that these have the same subsets:

In[8]:=
Sort[t1] === Sort[t2]
Out[8]=

Version History

  • 1.0.0 – 04 March 2020

License Information