Function Repository Resource:

SelectSubsets

Source Notebook

Generate subsets that satisfy a certain criterion

Contributed by: Sander Huisman

ResourceFunction["SelectSubsets"][list,crit]

gives a list of all possible subsets of list that satisfy the criterion crit.

ResourceFunction["SelectSubsets"][list,n,crit]

gives all subsets containing at most n elements that satisfy crit.

ResourceFunction["SelectSubsets"][list,{n},crit]

gives all subsets containing exactly n elements that satisfy crit.

ResourceFunction["SelectSubsets"][list,{nmin,nmax},crit]

gives all subsets containing between nmin and nmax elements that satisfy crit.

ResourceFunction["SelectSubsets"][list,nspec,crit,s]

limits the results to the first s subsets.

Details and Options

ResourceFunction["SelectSubsets"] orders subsets in the same way as Subsets. If the elements of list are in the order returned by Sort, then the complete result from ResourceFunction["SelectSubsets"][list,crit] will also be in this order.
The setting All for nspec gives the subsets for the lengths 0 to Length[list].
ResourceFunction["SelectSubsets"][list,{nmin,nmax,dn},crit] gives subsets containing nmin, nmin+dn, … elements.

Examples

Basic Examples (2) 

Select subsets from {1,2,3,4,5} that add up to 10:

In[1]:=
ResourceFunction["SelectSubsets"][{1, 2, 3, 4, 5}, EqualTo[10]@*Total]
Out[1]=

Select subsets of length 2 to 4 that sum up to a prime:

In[2]:=
ResourceFunction["SelectSubsets"][{1, 2, 3, 4, 5}, {2, 4}, PrimeQ@*Total]
Out[2]=

Scope (4) 

Select all subsets of length 2 that add up to 6:

In[3]:=
ResourceFunction["SelectSubsets"][{1, 2, 3, 4, 5}, {2}, EqualTo[6]@*Total]
Out[3]=

Select all subsets that add up to 0:

In[4]:=
ResourceFunction["SelectSubsets"][{-3, -2, -1, 0, 1, 2, 3}, All, EqualTo[0]@*Total]
Out[4]=

Select all subsets of odd length that add up to a prime:

In[5]:=
ResourceFunction["SelectSubsets"][{-3, -2, -1, 0, 1, 2, 3}, {1, 7, 2},
  PrimeQ@*Total]
Out[5]=

Select the first eight subsets that add up to a prime:

In[6]:=
ResourceFunction["SelectSubsets"][{1, 2, 3, 4, 5}, All, PrimeQ@*Total,
  8]
Out[6]=

Applications (1) 

Find subsets that add up to 25:

In[7]:=
ResourceFunction["SelectSubsets"][Range[6, 13], All, EqualTo[25]@*Total]
Out[7]=

Properties and Relations (2) 

The main difference between Select and Subsets, and SelectSubsets is the amount of memory used:

In[8]:=
MaxMemoryUsed[
 res1 = ResourceFunction["SelectSubsets"][Range[6, 24], EqualTo[25]@*Total]]
Out[8]=

Compared to naive implementation, which requires roughly a 1000 times more memory:

In[9]:=
MaxMemoryUsed[
 res2 = Select[Subsets[Range[6, 24]], EqualTo[25]@*Total]]
Out[9]=

Verify the result is the same:

In[10]:=
res1 === res2
Out[10]=

With a criterion that is a tautology, SelectSubsets and Subsets give the same results:

In[11]:=
ResourceFunction["SelectSubsets"][Range[5], True &] == Subsets[Range[5]]
Out[11]=

Possible Issues (1) 

SelectSubsets might not be able to return the number of elements that are requested:

In[12]:=
ResourceFunction["SelectSubsets"][Range[5], All, EqualTo[8]@*Total, 5]
Out[12]=

Neat Examples (2) 

Find subsets that add up to 0:

In[13]:=
sets = ResourceFunction["SelectSubsets"][Range[-7, 7], All, EqualTo[0]@*Total];
Short[sets]
Out[14]=

Visualize the lengths of the lists:

In[15]:=
ListPlot[Length /@ sets, Joined -> True]
Out[15]=

Publisher

SHuisman

Version History

  • 1.0.0 – 22 August 2019

Related Resources

License Information