Given a vector of positive integers $A=[a_1, \cdots, a_n]$, where $\sum_{1 \leq i \leq n}a_i = n(n-1)$ and $a_i \geq a_j$ iff $i \geq j$, I am interested in encoding the vector, maintaining the following conditions,

  1. The result of encoding is unique, i.e. the encoding of two different vectors cannot be the same.
  2. The result of encoding has the same order as the dot-product of A with the vector $[1, \cdots, n]$, i.e., $A \cdot [1, \cdots, n] > A' \cdot [1, \cdots, n] \Rightarrow e(A)>e(A')$.

I was wondering if such encoding exists. I tried a couple of options such as $e(A)=A \cdot [2^1, \cdots, 2^n]$, but it did not work. I am not sure if considering an irrational number such as Euler's instead of 2 would work, i.e. $e(A)=A \cdot [e^1, \cdots, e^n]$.

P.S. Of course, one way is using prime numbers, but this way is computationally very expensive and I want to avoid that. So, I prefer a way that does not involve calculating prime numbers and such computationally-intensive values.


Define $[b_1,\dots,b_n]$ by $b_i = a_i - a_{i-1}$ for $i>1$ and $b_1 = a_1-1$. Then $[b_1,\dots,b_n]$ is a sequence of non-negative integers.

Pick any unique encoding of such sequences, call it $e^*$, with the property that the output of $e^*([b_1,\dots,b_n])$ is an integer in the range $0..M-1$ for some $M$.

Finally, define an encoding $e$ as follows:

$$e([a_1,\dots,a_n]) = M \times [a_1,\dots,a_n] \cdot [1,2,\dots,n] + e^*([b_1,\dots,b_n])$$

where $[b_1,\dots,b_n]$ is defined as above. Then the encoding $e$ satisfies both of your conditions. Encodings are unique (this follows from the uniqueness property of $e^*$). Also it satisfies the ordering property (this follows since $0 \le e^*(\cdots) < M$).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.