Skip to main content

Sort sequences with respect to the similarity of consecutive items.

Project description

dominosort
==========

*Sort sequences with respect to the similarity of consecutive items.*

Definition
----------

Given a sequence of items :math:`(x_i, y_i)`, where each item is represented by two values
:math:`x, y`, the goal is to sort the sequence such that the following loss
is minimal:

.. math::

L = \sum_{i=1}^{N-1} \mu(y_i, x_{i+1})

where :math:`\mu` denotes a suitable metric for the items' values.

Example
-------

Given the items

.. code:: python

>>> items = [
... (0.4, 0.6),
... (0.0, 0.2),
... (0.8, 1.0),
... (0.6, 0.8),
... (0.2, 0.4),
... ]

together with the L1 distance :math:`\mu: (x, y) \rightarrow |x-y|`, the current loss is

.. code:: python

>>> abs(0.6 - 0.0) + abs(0.2 - 0.8) + abs(1.0 - 0.6) + abs(0.8 - 0.2)
2.2

Clearly the optimal sort order which minimizes the loss is

>>> optimal = [
... (0.0, 0.2),
... (0.2, 0.4),
... (0.4, 1.6),
... (0.6, 0.8),
... (0.8, 1.0),
... ]

Related topics
--------------

Note that for the special case where :math:`x_i = y_i` and the :math:`x_i` represent 2d-coordinates
this corresponds to the Travelling Salesman Problem without return to the origin.


Project details


Release history Release notifications | RSS feed

This version

0.1

Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Files for dominosort, version 0.1
Filename, size File type Python version Upload date Hashes
Filename, size dominosort-0.1-py3-none-any.whl (9.9 kB) File type Wheel Python version py3 Upload date Hashes View

Supported by

Pingdom Pingdom Monitoring Google Google Object Storage and Download Analytics Sentry Sentry Error logging AWS AWS Cloud computing DataDog DataDog Monitoring Fastly Fastly CDN DigiCert DigiCert EV certificate StatusPage StatusPage Status page