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.

==========

*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

## 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 |