1

Given the set $S$ of all possible sequences within bounds $[1, 31]$ with $n$ elements (where $n$ is constant and $ 1 < n < 32$) and a set $L \subset \{0, 1, 2, \dots, 2^{64}\}$ where $|L| = |S|$, does there exist a function $f$, so that the binary relation $R: S \times L$ is injective?

Actual use case (computer science):

I have a non-strict weak ordered list of constant length $1 < n < 32$ with integers in range $[1, 31]$. I want to know if it's possible to unqiuely map each list to a 64 bit integer. The mapping is one-way only, so I don't need to map an integer back to a list.

Andrés E. Caicedo
  • 79,201
Timo
  • 125

2 Answers2

1

If $\mathbf a = (a_0,a_1,\ldots, a_{n-1})$ is a non-decreasing sequence of non-negative integers, we can defined $$f(\mathbf a)=\sum_{i=0}^{n-1}2^{a_i+i}.$$ With this definition, $\mathbf a\ne\mathbf b$ implies $f(\mathbf a)\ne f(\mathbf b)$. Additionally, $$ 2^n-1\le f(\mathbf a)<2^{n+a_n}.$$ With your constraints, this means $f(\mathbf a)<2^{64}$, as desired.

Hagen von Eitzen
  • 374,180
  • Wow that definition just so happens to fit into 64 bits. When you say $a \neq b$ does this also account for non-constant $n$ (i.e. when $|a| \neq |b|$)? – Timo Oct 05 '19 at 12:35
  • Also if you could add some detail on how you got to this definition of $f$ that would be great. I understand what the function does but not how you came up with it. – Timo Oct 05 '19 at 12:43
0

First of all $|S|$ is bigger than you think. If we treat each sequence $(n_1,n_2,\ldots, n_{32})$ as the map $$\{1,2,\ldots,32\} \to \{0,1,\ldots,31\} \qquad i \mapsto n_i$$ between sets of cardinality $32$ then by definition there are $32^{32}$ elements. Now write

$$32^{32} = (2^5)^{32} = 2^{4 \cdot 32} = 2^{160}.$$

So $|S| = 2^{160}$ in fact.

To get a bijection from $S$ to $\{1,2,\ldots, 2^{160}\}$ express each integer in the list in binary and then remove the commas. For example

$(1,2,5,\ldots,8) \mapsto (00001,00010,00101,\ldots,00100) \mapsto 000010001000101 \ldots00100$

Daron
  • 10,300
  • An interesting approach, but unfortunately impractical and it doesn't satisfy the size limit of a 64 bit integer. I think you made a mistake here: $32^{32}$ would the number of elements be if the list wasn't sorted. – Timo Oct 05 '19 at 13:03