.. DO NOT EDIT.
.. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY.
.. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE:
.. "api/gallery/combinatorics/extremal/plot_02_erdos_szekeres.py"
.. LINE NUMBERS ARE GIVEN BELOW.

.. only:: html

    .. note::
        :class: sphx-glr-download-link-note

        :ref:`Go to the end <sphx_glr_download_api_gallery_combinatorics_extremal_plot_02_erdos_szekeres.py>`
        to download the full example code.

.. rst-class:: sphx-glr-example-title

.. _sphx_glr_api_gallery_combinatorics_extremal_plot_02_erdos_szekeres.py:


The Erdős-Szekeres theorem: monotone subsequences
=======================================================

Any sequence of (r-1)(s-1)+1 distinct numbers contains an increasing
subsequence of length r or a decreasing one of length s. This example
finds the longest monotone subsequences of random permutations and shows
that their length grows like 2 sqrt(n).

.. GENERATED FROM PYTHON SOURCE LINES 12-17

.. code-block:: Python

    import matplotlib.pyplot as plt
    import numpy as np

    from mathematicskit.combinatorics import longest_decreasing_subsequence, longest_increasing_subsequence








.. GENERATED FROM PYTHON SOURCE LINES 18-20

Every 10-term sequence has a monotone run of length 4
-----------------------------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 20-27

.. code-block:: Python


    rng = np.random.default_rng(1)
    for _ in range(5):
        seq = rng.permutation(10).tolist()
        up, down = longest_increasing_subsequence(seq), longest_decreasing_subsequence(seq)
        print(f"{seq}: increasing {up}, decreasing {down}")





.. rst-class:: sphx-glr-script-out

 .. code-block:: none

    [8, 4, 7, 0, 1, 2, 5, 9, 6, 3]: increasing [0, 1, 2, 5, 6], decreasing [8, 7, 6, 3]
    [0, 1, 8, 6, 5, 7, 9, 2, 3, 4]: increasing [0, 1, 2, 3, 4], decreasing [8, 6, 5, 4]
    [3, 1, 5, 6, 9, 0, 7, 2, 8, 4]: increasing [1, 5, 6, 7, 8], decreasing [9, 8, 4]
    [0, 7, 9, 3, 2, 6, 4, 8, 5, 1]: increasing [0, 2, 4, 5], decreasing [9, 8, 5, 1]
    [3, 1, 9, 2, 8, 4, 0, 5, 7, 6]: increasing [1, 2, 4, 5, 6], decreasing [9, 8, 7, 6]




.. GENERATED FROM PYTHON SOURCE LINES 28-30

A sequence that meets the bound exactly
-----------------------------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 30-34

.. code-block:: Python


    sharp = [7, 8, 9, 4, 5, 6, 1, 2, 3]
    print(f"\n{sharp}: longest runs {len(longest_increasing_subsequence(sharp))} and {len(longest_decreasing_subsequence(sharp))}")





.. rst-class:: sphx-glr-script-out

 .. code-block:: none


    [7, 8, 9, 4, 5, 6, 1, 2, 3]: longest runs 3 and 3




.. GENERATED FROM PYTHON SOURCE LINES 35-37

Growth for random permutations
-----------------------------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 37-46

.. code-block:: Python


    sizes = [10, 30, 100, 300, 1000, 3000]
    means = [np.mean([len(longest_increasing_subsequence(rng.permutation(n).tolist())) for _ in range(40)]) for n in sizes]
    fig, ax = plt.subplots()
    ax.loglog(sizes, means, "o-", label="mean longest increasing subsequence")
    ax.loglog(sizes, 2 * np.sqrt(sizes), "--", label=r"$2\sqrt{n}$")
    ax.loglog(sizes, np.sqrt(sizes), ":", label=r"Erdős-Szekeres guarantee $\sqrt{n}$")
    ax.set_xlabel("n")
    ax.legend()



.. image-sg:: /api/gallery/combinatorics/extremal/images/sphx_glr_plot_02_erdos_szekeres_001.png
   :alt: plot 02 erdos szekeres
   :srcset: /api/gallery/combinatorics/extremal/images/sphx_glr_plot_02_erdos_szekeres_001.png
   :class: sphx-glr-single-img


.. rst-class:: sphx-glr-script-out

 .. code-block:: none


    <matplotlib.legend.Legend object at 0x1192fb770>




.. rst-class:: sphx-glr-timing

   **Total running time of the script:** (0 minutes 0.055 seconds)


.. _sphx_glr_download_api_gallery_combinatorics_extremal_plot_02_erdos_szekeres.py:

.. only:: html

  .. container:: sphx-glr-footer sphx-glr-footer-example

    .. container:: sphx-glr-download sphx-glr-download-jupyter

      :download:`Download Jupyter notebook: plot_02_erdos_szekeres.ipynb <plot_02_erdos_szekeres.ipynb>`

    .. container:: sphx-glr-download sphx-glr-download-python

      :download:`Download Python source code: plot_02_erdos_szekeres.py <plot_02_erdos_szekeres.py>`

    .. container:: sphx-glr-download sphx-glr-download-zip

      :download:`Download zipped: plot_02_erdos_szekeres.zip <plot_02_erdos_szekeres.zip>`


.. only:: html

 .. rst-class:: sphx-glr-signature

    `Gallery generated by Sphinx-Gallery <https://sphinx-gallery.github.io>`_