Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 NextKSubset

Source Notebook

Get the lexicographic successor of a k-subset of a list

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

ResourceFunction["NextKSubset"][l,s]

gives the k-subset of list l that follows the k-subset s in lexicographic order.

Examples

Basic Examples (1) 

The lexicographic successor of a k-subset of an integer range:

In[1]:=
ResourceFunction["NextKSubset"][{1, 2, 3, 4, 5}, {1, 2, 4}]
Out[1]=

Properties and Relations (2) 

NextKSubset[l,s] gives the successor to s in the list of k-subsets (where k is the length of s):

In[2]:=
list = Range[2, 10, 2]
Out[2]=
In[3]:=
ResourceFunction["NextKSubset"][list, {2, 4, 10}]
Out[3]=
In[4]:=
subs = Subsets[list, {3}]
Out[4]=

The full list of subsets can also be obtained by iteratively applying NextKSubset, beginning at the initial such subset:

In[5]:=
start = {2, 4, 6}; subs2 = NestList[ResourceFunction["NextKSubset"][list, #] &, start, Binomial[Length[list], Length[start]] - 1]
Out[6]=
In[7]:=
subs == subs2
Out[7]=

Version History

  • 1.0.0 – 04 March 2020

License Information