algorithm - 将数字编码为单个数字

Question

我对数字及其表示有疑问。

我有一组自然数，其最大可能值为 1 000 000，称它为 NUM。从集合 NUM 中取出 1-50 个数字，其中相同的数字可以包含多次，称为 IN。使用这些条件将集合 IN 转换为单个数字 (OUT):

1. OUT 将唯一标识集合 IN。

2. 将可以使用两个 OUT 编号(<,>,<=,>=)的比较，完全取决于创建 OUT 的时间(一次只能创建一个 OUT)

(3. preferred) 将OUT转化为原始集合IN将成为可能。

---

例子:

NUM={1,2,3,4,5,6,7,8,9,10,......,1000000}

IN1={2,4,6}，创建时间1

IN2={1,3,8}，创建时间2

IN3={4,4,4}，创建时间3

--------------------------------------------

OUT1=function(IN1,time 1)

OUT2=function(IN2,time 2)

OUT3=function(IN3,time 3)

1. OUT1 != OUT2 != OUT3

2. OUT1 < OUT2 < OUT3

3. IN1=reverse_function(OUT1)

---

有没有办法找到这个 function() 或 reverse_function()???

Answer 1

有几种方法。 一种非常常见的方法是将每个不同的数字映射到一个素数，然后编码该数字在指数中出现的频率。

它叫做 Gödel numbering

如果每个数字只能出现一次，您甚至可以摆脱从数字到素数的映射。比您可以将数字本身存储在素数的指数中(每个数字的不同素数) 例如你想存储 {123,47,2} 你可以做到吗 像这样:

result=(2^123)*(3^47)*(5^2)

然后您可以通过进行质因数分解并查看指数来扭转这一局面。