How to sort a list of tuples?

332 Views Asked by At

I am neither a mathematician, nor a computer scientist, but I have the following problem, which I cannot solve myself.

I have $k$ $i$-tuples $(x_1, x_2, …, x_i)$, where $x ∈ [0,1]$.

I need to order them so two most similar tuples are placed next to each other. The problem is I don’t really know how to define “similar” and what algorithm to use to order the tuples. This “similarity” of two tuples might be calculated (at least I believe so) by some kind of a function of the position of an element in a tuple and its value.

Below is an example of something I would like to have in the end, assuming that there are $10$ $6$-tuples $(x_A,x_B,x_C,x_D,x_E,x_F)$.

  1. $(0.96,0,0,0,0,0.53)$
  2. $(0.78,0.81,0.67,0,0,0)$
  3. $(0,0.83,0.84,0.57,0,0)$
  4. $(0,0.74,1,0,0,0)$
  5. $(0,0,0.75,0.62,0.56,0,0)$
  6. $(0,0,0.66,0.84,0.6,0,0)$
  7. $(0.57,0,0,0.72,0.87,0.79)$
  8. $(0,0.52,0,0,0.99,0.62)$
  9. $(0.51,0.55,0,0.54,0.56,0)$
  10. $(0.58,1,0,0.75,0,0.98)$

[Fig. 1A. Approximate visualization of a sorted list of $10$ $6$-tuples.]

Fig. 1B. Approximate visualization of a sorted list of $k$ $i$-tuples

enter image description here

Tuples #$9$ and #$10$ cannot be grouped/clustered, so they should be either discarded or moved to the end of a list.

As you can see, there should be a certain diagonal pattern, some sort of a main peak of density that moves. I would really appreciate if someone could at least point me in the right direction, I am completely clueless at the moment even about how to describe what I want in scientific terms.

Thank you very much. I really hope that someone would be able to help me.

P.S. I don’t know if it easier, but at the very least I can just transform all tuples in a way that all values in arrange $[0.51, 1]$ will be represented by $1$, and all values in a range $[0,0.5]$ will be represented by $0$.

Then I will need to sort the tuples so they formed the pattern below. Again, I don’t know what is the term for what I want. I expect to see some kind of a roughly diagonal pattern.

  1. $(1,0,0,0,0,1)$
  2. $(1,1,1,0,0,0)$
  3. $(0,1,1,1,0,0)$
  4. $(0,1,1,0,0,0)$
  5. $(0,0,1,1,1,0)$
  6. $(0,0,1,1,1,0)$
  7. $(1,0,1,1,1,1)$
  8. $(0,1,0,0,1,0)$
  9. $(1,1,0,1,1,0)$
  10. $(1,1,0,1,0,1)$

Fig. 2. Approximate visualisation of a sorted list of $10$ simplified $6$-tuples

enter image description here