Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 DescendingSublists

Source Notebook

Split a list at its left-to-right maxima

Contributed by: George Beck

ResourceFunction["DescendingSublists"][list]

makes sublists of list starting at its left-to-right maxima.

Details and Options

The elements in the sublists are in the same order as the original list.
A left-to-right maximum is greater than any preceding element.
The first element of each sublist is its maximum.
The first elements of the sublists are increasing.

Examples

Basic Examples (2) 

Split a permutation given as a list into sublists starting at its left-to-right maximum:

In[1]:=
ResourceFunction["DescendingSublists"]@{2, 4, 1, 6, 7, 5, 3}
Out[1]=

The input does not have to be a permutation:

In[2]:=
r1 = RandomInteger[{1, 7}, 20]
Out[2]=
In[3]:=
ResourceFunction["DescendingSublists"]@r1
Out[3]=

Flatten to get back the original list:

In[4]:=
r1 == Flatten@%
Out[4]=

Scope (4) 

Here is a larger example:

In[5]:=
p1 = PermutationList@RandomPermutation@50
Out[5]=
In[6]:=
s1 = ResourceFunction["DescendingSublists"]@p1
Out[6]=

Each sublist starts from its maximum:

In[7]:=
Row[ListLinePlot /@ s1]
Out[7]=

The first elements are increasing:

In[8]:=
ListLinePlot[First /@ s1]
Out[8]=

The sublists of s1 an be thought of as cycle notation for the permutation, but with a different canonical form than the Wolfram Language default, where each sublist starts with its minimum:

In[9]:=
Cycles[s1]
Out[9]=

Publisher

George Beck

Version History

  • 1.0.0 – 31 May 2019

Source Metadata

  • Citation:
    • Stanley, R., Enumerative Combinatorics Volume 1, 2nd edition, pg. 23. Cambridge: Cambridge University Press, 2012.
    • Bóna, M., Combinatorics of Permutations, 2nd edition, pg. 109. Boca Raton, FL: CRC Press, 2012.

License Information