.. DO NOT EDIT.
.. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY.
.. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE:
.. "api/gallery/combinatorics/trees/plot_01_prufer_codes.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_trees_plot_01_prufer_codes.py>`
        to download the full example code.

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

.. _sphx_glr_api_gallery_combinatorics_trees_plot_01_prufer_codes.py:


Cayley's formula via Prüfer codes
=======================================

Encodes labeled trees as Prüfer sequences and decodes every sequence of
length n-2 back to a tree. The correspondence is one-to-one, so there
are n^(n-2) labeled trees on n vertices.

.. GENERATED FROM PYTHON SOURCE LINES 11-18

.. code-block:: Python

    from itertools import product

    import matplotlib.pyplot as plt
    import numpy as np

    from mathematicskit.combinatorics import count_labeled_trees, prufer_decode, prufer_encode








.. GENERATED FROM PYTHON SOURCE LINES 19-21

Encode and decode one tree
-----------------------------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 21-26

.. code-block:: Python


    tree = [(0, 4), (1, 4), (2, 5), (3, 5), (4, 5), (5, 6)]
    code = prufer_encode(tree, 7)
    print(f"tree {tree}\nPrüfer code {code}\ndecoded {prufer_decode(code)}")





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

 .. code-block:: none

    tree [(0, 4), (1, 4), (2, 5), (3, 5), (4, 5), (5, 6)]
    Prüfer code [4, 4, 5, 5, 5]
    decoded [(0, 4), (1, 4), (2, 5), (3, 5), (4, 5), (5, 6)]




.. GENERATED FROM PYTHON SOURCE LINES 27-29

All 16 labeled trees on 4 vertices
-----------------------------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 29-43

.. code-block:: Python


    n = 4
    positions = {v: (np.cos(2 * np.pi * v / n), np.sin(2 * np.pi * v / n)) for v in range(n)}
    sequences = list(product(range(n), repeat=n - 2))
    fig, axes = plt.subplots(4, 4, figsize=(8, 8))
    for ax, seq in zip(axes.flat, sequences):
        for u, v in prufer_decode(seq):
            ax.plot(*zip(positions[u], positions[v]), "k-")
        for v, (x, y) in positions.items():
            ax.text(x, y, str(v), ha="center", va="center", bbox={"boxstyle": "circle", "fc": "w"})
        ax.set_title(str(list(seq)), fontsize=9)
        ax.axis("off")
    fig.suptitle(f"{len(sequences)} codes = {count_labeled_trees(n)} = 4^2 labeled trees")




.. image-sg:: /api/gallery/combinatorics/trees/images/sphx_glr_plot_01_prufer_codes_001.png
   :alt: 16 codes = 16 = 4^2 labeled trees, [0, 0], [0, 1], [0, 2], [0, 3], [1, 0], [1, 1], [1, 2], [1, 3], [2, 0], [2, 1], [2, 2], [2, 3], [3, 0], [3, 1], [3, 2], [3, 3]
   :srcset: /api/gallery/combinatorics/trees/images/sphx_glr_plot_01_prufer_codes_001.png
   :class: sphx-glr-single-img


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

 .. code-block:: none


    Text(0.5, 0.98, '16 codes = 16 = 4^2 labeled trees')



.. GENERATED FROM PYTHON SOURCE LINES 44-46

Counts for small n
-----------------------------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 46-50

.. code-block:: Python


    for n in range(2, 8):
        decoded = {tuple(prufer_decode(s)) for s in product(range(n), repeat=n - 2)}
        print(f"n = {n}: {len(decoded)} distinct trees, n^(n-2) = {count_labeled_trees(n)}")




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

 .. code-block:: none

    n = 2: 1 distinct trees, n^(n-2) = 1
    n = 3: 3 distinct trees, n^(n-2) = 3
    n = 4: 16 distinct trees, n^(n-2) = 16
    n = 5: 125 distinct trees, n^(n-2) = 125
    n = 6: 1296 distinct trees, n^(n-2) = 1296
    n = 7: 16807 distinct trees, n^(n-2) = 16807





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

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


.. _sphx_glr_download_api_gallery_combinatorics_trees_plot_01_prufer_codes.py:

.. only:: html

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

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

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

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

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

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

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


.. only:: html

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

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