1
$\begingroup$

Problem

I am a computer programmer looking for a mathematical function (or a more advanced algorithm) able to produce a 32bits integer out of a list of integers with the following constraints:

  • Each item in the input list is a positive integer with a known range ([0-M] with M<10, that range may differ from an element to another).
  • The input list have a fixed number of element (< 10).
  • The order of elements in the list is important ([1, 2, 3] is not the same as [2, 3, 1]).
  • For two set of inputs, the more inputs have been modified the more different the output must be. And by this I also mean that two inputs with only one number changed must produce close outputs, no matter how much that value have changed.
  • Being able to find the original list from the generated number does not matter.
  • Each unique set of inputs must produce a unique output (no duplicate outputs if an input is different).
  • Having not exactly the same output when taking the same input twice could be acceptable, as soon a the difference between outputs is really low (<0.1% difference).
  • The range of the output numbers generated must be known (to be able to map the output values to any other range).
  • The range of the output values is considered cyclic (if output is in range [0-1000] then 0 and 1000 would be very close output values).

Examples

Here are a few examples:

  • Lets say the input [1, 2, 3] produces the output 100 where outputs are in range [0-1000].

  • Then the input [1, 42, 3] should produce 150, an output pretty close to it as only one number changed.

  • But the input [2, 3, 4] should produce 500, an output very far away as all values have changed.

Links

I explored various answers on this website but none of them seems to match my needs:

Calculate unique Integer representing a pair of integers

Unique numerical encodings of lists of integers

"Unique" number from several values

The hash-related answers seemed promising, but sadly all those I could find appear to have huge variability for output numbers, independently of the inputs. Here controlled variability is the center of the problem.

More context

If you are wondering what this would be used for, the idea is to use that function to produce a unique color (by mapping the output to the hue) for an object with multiple attributes, so that objects with a lot of attributes in common will look similar.

Any advice on this topic would be appreciated :)

Also if you think that this kind of behavior is impossible to achieve for some logical reason I completely missed, please feel free to share it!

EDIT:

So I did implement your function @Marcus Müller, with N=7 and Mi=6 for all elements except the first one which is 4, and it came out with a curious output numbers repartition: Output numbers ditribution Few things to notice here:

  • First of all I never get value above 0.73, which means I am missing a bit more more than 1/4 of the spectrum when translating this into hues :/
  • And then I get values concentrated around certain regions, leading to only a few colors appearing, and items with very different inputs still looking very similar in color...

Any clue what could have led to these results? (My implementation might of course be the main culpist here, but any lead on which part to tweak from there would help).

EDIT 2:

The legend of the graph was an inaccurate representation of the values range, and it is in fact reaching up to 0.85. Still investigating where are the missing 15% though :p

$\endgroup$
9
  • $\begingroup$ Well, because your (my) choice of $q_i$ wasn't a good equipartition to begin with, and because we didn't scale anything so that the each element of the sum can contribute the same – It's hard to know what you're aiming for (your graph doesn't convert to a colorful representation in my head), but it might help if you picked your $q_i$ such that they hit a start of a "color range" and then scaled the exponents according to $M_i$; but I doubt you'll come up with a sensible mathematical condition that describes "Flo find this beautiful", so this is nothing anyone can optimize for you. $\endgroup$ Jul 21, 2021 at 18:50
  • $\begingroup$ In other words: I gave you tools. It's your job to make art. $\endgroup$ Jul 21, 2021 at 18:51
  • $\begingroup$ Also, if you're not ever hitting anything above 0.73, you didn't implement my formula – insert the all-0 $\mathbf v$ in my formula and you'll get 1, no doubts there; so, you'll also want to fix your bug! $\endgroup$ Jul 21, 2021 at 18:53
  • $\begingroup$ It is more about ergonomics than aestetics here: ideal repartition is simply "a similar amount of each possible hue" so that a user looking at a grid full of such colors could easily tell which squares are similar and which are different :) $\endgroup$
    – Flo
    Jul 21, 2021 at 18:59
  • $\begingroup$ I did implement all of it, which is why I was so confused about the missing part... So it must be related to the actual values I am using and not the formula itself. $\endgroup$
    – Flo
    Jul 21, 2021 at 18:59

1 Answer 1

2
$\begingroup$

That sounds like a similarity hash function.

A simple one can be drawn from a bit of algebra. But let's start by formalizing what you wrote, because it's kind of "human" and thus a bit ambiguous; clarity is our friend here.

We have $N< 10$ numbers in a vector; each element of that vector is an integer from $I_i = \{0,1, \ldots,M_i\}$, where $i$ are the indices $1,\ldots ,N$. Thus, the overall structure we need to describe is an $N$-dimensional vector

$$\mathbf v \in I_1 \times I_2 \times \cdots \times I_N.$$

We need to map that vector into a 1-dimensional vector space, the hue of colors, so, a real number between 0 and 1; we're looking for a function

$$f(\mathbf v): I_1 \times I_2 \times \cdots \times I_N \mapsto [0;1].$$

Let's do something crazy: let's demand that if all $v_i=0$, then $f(\mathbf v_0)=0$, and that if all $v_i=M_i$, then $f(\mathbf v_{\text{max}}=1)$.

Let $p_i$ be a sequence of integer numbers that aren't multiples of each other; so, let $p_1=8, p_2=9, p_3=10, p_4=11, p_5=13, p_6=14, p_7=15, p_8=17, p_9=19$. This choice is arbitrary.

Because the $p_i$ aren't multiples of each other, so aren't $q_i=\frac1{p_i}$.

Thus, the sum

$$\tilde f(\mathbb v) =\sum\limits_{i=1}^N {q_i}^{v_i}$$

takes a different value for every $\mathbf v$, because no power of a $q_i$ can ever be a power of a different $q_i$.

Now, sadly, the image of this $\tilde f$ isn't $[0,1]$, but for the all-0 $\mathbf 0$ we get $N$ (right, the 0th power of any $q$ is always 1, and we've got $N$ of these), and since all $q_i < 1$, the higher your values, the lower we get; the lowest is actually when all exponents are at their maximum, $M_i$; but we can simply mogrify the function to fit our range of interest:

$$f(\mathbb v) = \frac{\tilde f(\mathbb v)-\sum_{i=1}^N{q_i^{M_i}}}{N-\sum_{i=1}^N{q_i^{M_i}}}$$

Small changes to individual $v_i$ don't "hurt" the result much, but still lead to differing values.

$\endgroup$
3
  • $\begingroup$ This looks like a great approach to the problem, thank you :) I was a bit concerned about the implementation regarding potential limitations of the programming language I will use, but so far every limitation factors I could imagine seems to be okay. So I will try to implement it and let you know if it has the intended result ^^ $\endgroup$
    – Flo
    Jul 21, 2021 at 16:08
  • $\begingroup$ PS: If arbitrary numbers should not be multiple of each other I guess p9 should be 19 and not 18 because of p2=9. $\endgroup$
    – Flo
    Jul 21, 2021 at 16:11
  • $\begingroup$ err yes, indeed. $\endgroup$ Jul 21, 2021 at 16:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .