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

This version
History Node

0.1

Download files

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

Filename, size & hash SHA256 hash help File type Python version Upload date
dominosort-0.1-py3-none-any.whl (9.9 kB) Copy SHA256 hash SHA256 Wheel py3

Supported by

Elastic Elastic Search Pingdom Pingdom Monitoring Google Google BigQuery Sentry Sentry Error logging AWS AWS Cloud computing DataDog DataDog Monitoring Fastly Fastly CDN SignalFx SignalFx Supporter DigiCert DigiCert EV certificate StatusPage StatusPage Status page