Function Repository Resource:

SelectPermutations

Source Notebook

Get permutations that satisfy a certain criterion

Contributed by: Sander Huisman

ResourceFunction["SelectPermutations"][list,crit]

generates a list of all possible permutations of the elements in list satisfying crit.

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

gives all permutations containing at most n elements satisfying crit.

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

gives all permutations containing exactly n elements satisfying crit.

ResourceFunction["SelectPermutations"][,crit,m]

gives at most m results.

Details and Options

There are n! permutations of a list of n distinct elements.
Repeated elements are treated as identical.
The object list need not have head List.
ResourceFunction["SelectPermutations"][list,crit] is effectively equivalent to ResourceFunction["SelectPermutations"][list,{Length[list]},crit].
ResourceFunction["SelectPermutations"][list,{nmin,nmax},crit] gives permutations of between nmin and nmax elements.
ResourceFunction["SelectPermutations"][list,{nmin,nmax,dn},crit] gives permutations nmin, nmin+dn, nmin+2dn … and nmax elements.

Examples

Basic Examples (2) 

Select from the list {5,6,7,8,9} those permutations that form a prime when concatenating the digits:

In[1]:=
ResourceFunction["SelectPermutations"][{5, 6, 7, 8, 9}, PrimeQ@*FromDigits]
Out[1]=

Select those permutations having length 3:

In[2]:=
ResourceFunction["SelectPermutations"][{5, 6, 7, 8, 9}, {3}, PrimeQ@*FromDigits]
Out[2]=

Select those permutations having length 3–4:

In[3]:=
ResourceFunction["SelectPermutations"][{5, 6, 7, 8, 9}, {3, 4}, PrimeQ@*FromDigits]
Out[3]=

Select permutations of {1,2,3,4} for which the first two elements and the last elements add up to the same value:

In[4]:=
ResourceFunction["SelectPermutations"][{1, 2, 3, 4}, Total[#[[1 ;; 2]]] == Total[#[[3 ;; 4]]] &]
Out[4]=

Scope (1) 

Select the first 10 permutations of length 4 for which the elements add up to an odd number:

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

Applications (2) 

Select polynomials for which the slope is 1 at x=0:

In[6]:=
out = Total /@ ResourceFunction["SelectPermutations"][{x, 4 x, 1, (x - 2)^2}, 4, ((D[Total[#], x]) /. x -> 0) == 1 &]
Out[6]=

Confirm that the slope is indeed unity at x=0:

In[7]:=
D[#, x] /. x -> 0 & /@ out
Out[7]=

Properties and Relations (3) 

Duplicated items are treated the same:

In[8]:=
ResourceFunction[
 "SelectPermutations"][{6, 7, 7, 7, 8}, {2}, (Total[#] == 14) &]
Out[8]=

The main difference between SelectPermutations[list,crit] and Select[Permutations[list],crit] is the memory usage:

In[9]:=
MaxMemoryUsed[
 result1 = ResourceFunction["SelectPermutations"][Range[3, 13], 6, Total[#] == 24 &];]
Out[9]=

Using Select and Permutations uses 500 times more memory:

In[10]:=
MaxMemoryUsed[
 result2 = Select[Permutations[Range[3, 13], 6], Total[#] == 24 &];]
Out[10]=

Verify that the results are identical:

In[11]:=
result1 == result2
Out[11]=

Head does not have to be List:

In[12]:=
ResourceFunction["SelectPermutations"][
 f[1, 2, 3, 4, 5], {2}, ((Plus @@ #) == 6 &)]
Out[12]=

Possible Issues (2) 

SelectPermutations might take longer as it is written in higher-level code as compared to the implementation of Permutations:

In[13]:=
MaxMemoryUsed[
  time = AbsoluteTiming[
     result1 = ResourceFunction["SelectPermutations"][Range[3, 13], 6, Total[#] == 24 &];][[1]]];
Grid[{{"Time [sec]:", time}, {"Memory usage [bytes]:", %}}]
Out[14]=

Using the built-in functions is faster at the expense of 500× more memory:

In[15]:=
MaxMemoryUsed[
  time = AbsoluteTiming[
     result2 = Select[Permutations[Range[3, 13], 6], Total[#] == 24 &];][[1]]];
Grid[{{"Time [sec]:", time}, {"Memory usage [bytes]:", %}}]
Out[16]=

Publisher

SHuisman

Version History

  • 1.0.0 – 19 September 2019

Related Resources

License Information