Function Repository Resource:

GrayCodeSubsetIndex

Source Notebook

Find the index of a subset in Gray code order

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

ResourceFunction["GrayCodeSubsetIndex"][list,s]

gives the zero-based index of the subset s in the Gray code ordering of the subsets of list.

Details and Options

In Gray code order, subsets differ from their neighbors by the insertion or deletion of one element.
The index of the empty set is 0.

Examples

Basic Examples (1) 

The index of a subset in Gray code order:

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

Properties and Relations (2) 

Define a List:

In[2]:=
list = {a, b, c, d};

Use the resource function GrayCodeSubsets to get the subsets of the List in Gray code order:

In[3]:=
subsets = ResourceFunction["GrayCodeSubsets"][list]
Out[3]=

Use GrayCodeSubsetIndex to find the index of each subset:

In[4]:=
ResourceFunction["GrayCodeSubsetIndex"][list, #] & /@ subsets
Out[4]=

Positions are offset by one:

In[5]:=
(FirstPosition[subsets, #, {1}] & /@ subsets) - 1
Out[5]=

Get the subsets in Gray code order sequentially using the resource function NthGrayCodeSubset:

In[6]:=
Table[ResourceFunction["NthGrayCodeSubset"][i, {a, b, c, d}], {i, 0, 15}]
Out[6]=

Their respective indices:

In[7]:=
ResourceFunction["GrayCodeSubsetIndex"][{a, b, c, d}, #] & /@ %
Out[7]=

Version History

  • 1.0.0 – 24 July 2020

Related Resources

License Information