Function Repository Resource:

NthGrayCodeSubset

Source Notebook

Get the n-th Gray code subset of a list

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

ResourceFunction["NthGrayCodeSubset"][n,list]

gives the nth subset of list, listed in Gray code order.

Details and Options

In Gray code order, subsets differ from its neighbors by the insertion or deletion of one element.
In ResourceFunction["NthGrayCodeSubset"][], the empty set is indexed as set 0.
ResourceFunction["NthGrayCodeSubset"] extracts parts cyclically from a List of all possible subsets.

Examples

Basic Examples (1) 

Fifth subset of a List in Gray code order:

In[1]:=
ResourceFunction["NthGrayCodeSubset"][5, {a, b, c, d}]
Out[1]=

Properties and Relations (2) 

In Gray code order, subsets differ from their neighbors by by the insertion or deletion of exactly one element:

In[2]:=
ResourceFunction["GrayCodeSubsets"][{a, b, c, d}]
Out[2]=

Sequentially reconstruct the subset list with NthGrayCodeSubset:

In[3]:=
Table[ResourceFunction["NthGrayCodeSubset"][i, {a, b, c, d}], {i, 0, Length[%] - 1}]
Out[3]=
In[4]:=
% === %%
Out[4]=

The resource function GrayCodeSubsetIndex gives back the index n of the subset constructed with NthGrayCodeSubset:

In[5]:=
list = {a, b, c, d};
In[6]:=
n = 5;
In[7]:=
ResourceFunction["NthGrayCodeSubset"][n, list]
Out[7]=
In[8]:=
ResourceFunction["GrayCodeSubsetIndex"][list, %]
Out[8]=

Version History

  • 1.0.0 – 24 July 2020

Related Resources

License Information