如何将一系列数字转换为单个数字？

Question

我想将一系列数字转换为一个单独的数字，该数字保留各个值以及它们的位置。例如，提供以下序列-

1,6,7,8,9,45,67

例如，如果应用简单的加法即 1+6+7+8+9+45+67，则会生成一个数字。但是从这个数字中，我们无法按其顺序提取每个单独的数字 [即 1,6,7,8,9,...]。

是否有任何方法可以在没有任何歧义的情况下实现此功能[即仅从数字中提取1个唯一的数字集]? 是否有任何数学函数可以帮助我们从该数字中获取各个元素？

- Debadyuti Maiti

---

它们都是正整数吗？ - Paddy3118

@Paddy3118 仅暂时考虑正数。如果您能同时处理正数和负数那就太棒了。 - Debadyuti Maiti

生成的数字有多大？ 可以将任意长度的位流转换为适当的数字（它可以是一个非常长的十进制数字，具有数百万位数字）。 不可能将所有位流转换为有限长度的数字（例如整数数据类型）：例如32位，64位，128位。 如果处理流（而不是整数数据类型），那么结果为什么必须是“数字”呢？ - user166390

Answer 1

你可以将此转换为一个基数为N的数字，其中N比您的输入序列中出现的最大值大一。

更新

根据各种评论，我想提供另一种可能更容易实现的替代方案。您可以将序列视为UTF-8编码的字符串，并使用自定义字典使用哈夫曼编码来实现紧凑表示。

自定义字典允许您使用非常少的位存储非常常见的字符（例如，序列分隔符','和单个字符'0'..'9'可以仅使用3位存储，但您发现也可以使用短的位序列存储其他可能经常出现的数字。例如，如果您发现“42”经常出现，您可以仅使用几位存储“42”。

如果您只为','和'0'到'9'分配特殊代码，则在保留逗号分隔序列成员的同时，您的输入字符串每个字符平均不到4位。找到常见的多字符子字符串并将其添加到字典中只会改善该比率。

使用自定义字典还意味着您不必将字典存储在压缩数据的头部，因为您已经知道它。

我使用SharpZipLib也做了类似的事情。

http://www.icsharpcode.net/opensource/sharpziplib/

http://community.sharpdevelop.net/forums/p/8255/23219.aspx

使用zlib也很容易实现

压缩小数据块

- Eric J.

---

你能举个例子来解释一下吗？可以使用问题中提供的数字序列作为示例吗？ - Debadyuti Maiti

@pst 是的。但是你只考虑数字。[即9、1、4、2] 但我也考虑像45、67这样的数字。那么你会如何对待它们[作为数字]? - Debadyuti Maiti

@DebadyutiMaiti 它们是一样的。唯一的区别是一个从小学开始就被编程了 :) 扩展十六进制数12F的数字：Base-16。再次强调，每个数字都可以根据位置唯一分离：如何？现在想象一种编号系统，其中每个数字的范围可以从(0)（值为0）到(43)（值为43），并且数字的书写方式为：(1)(42)(4)。每个数字都可以根据位置唯一分离：如何？ - user166390

"Sexageisml"仍然用于讨论地理坐标。我认为“数字系统的基数”可能是一个很好的起点.. - user166390

将此转换为基数为N的数字，当您想要反转时，如何检索N？如果有一种保存某些内容以便稍后检索的方法，您可以简单地将数字保存在字符串或数组中，这样更快，但它们将占用更多内存。 - Saeed Amiri

Answer 2

在有限序列中可以在数学上实现它，但实际上不太实用，因为所需的数字变得非常大：从1到67的整数长度为7的序列有67的7次方（约2的42次方）种，更长的序列和更大的整数则更是如此。

举个简单的例子，将序列[1,6,7,8,9,45,67]映射到值2的1次方乘以3的6次方乘以5的7次方乘以7的8次方乘以11的9次方乘以13的45次方乘以17的67次方。底数是质数，指数是序列中的元素。

反向映射是通过除法计算的-你的值可以被2整除的次数是序列的第一个元素，以此类推。值的最大质因数告诉你序列的长度。

如果您想允许序列中有0以及正数，那么在提高质数的幂时将所有元素加1。或者使用2的幂来表示序列的长度，然后从3开始对元素进行编码。

哥德尔在他的不完备性定理证明中使用了这样的编码。

正如肯德尔·弗雷所说，无法定义一个函数，将每个无限的整数序列映射到不同的整数。这是康托尔证明自然数幂集是不可数的后果：您甚至无法将所有从{true，false}中的元素的无限序列映射到整数，更不用说所有从整数中的元素的无限序列了。

对于更实际的方法，请考虑将整数序列编码为字节序列，而不是数字。一系列有限字节可以轻松地被视为二进制值，因此它是一个数字，你只是不会真正将其用作这样。您示例序列的常见表示是字节序列：[1,6,7,8,9,45,67]，例如在JSON中使用。这是一个136位的数字。反转此映射的数学函数涉及模256的算术、减去数字48、乘以10等操作。

- Steve Jessop

---

是的。如果您将整数从 [0, 1, -1, 2, -2, 3, 3, ..] 映射到 [1, 2, 3, 4, 5, ..] 等等，您可以以完全相同的方式处理负数。 - DSM

确实。一般来说，对于任何可数集合 S，您首先通过某种映射将 S 的元素映射到正整数，然后执行我上面说的操作。您已经为整数证明了一个单射。通过应用您的映射，然后两次使用我的方法，您同样可以编码其元素为整数有限序列的任何有限序列。 - Steve Jessop

Answer 3

假设你的序列名为s，我定义len(n)为数字n的位数。

那么你的结果的第一位是len(s[0])， 接下来的len(s[0])位是数字s[0]； 然后你附加len(s[1])和s[1]，以此类推。

这适用于最多有9位数字的数字。

- bigblind

---

可以通过使用两个数字编码长度（这将使您达到19位数字），或者使用更复杂的长度编码方案来将其扩展为任意长度的数字。例如，您可以将len(len(s[1]))作为单个数字，将len(s[1])放在1到9之间指定的数字位数中，然后再加上s[1]；这适用于长达十亿位数字的非负整数。 - Danica

如果它们都是正数，那么Zig-Zag编码（Protocol Buffer的著名编码方式）可以在位流中高效地对它们进行编码。 - user166390

Answer 4

这是一个基本的PHP实现哥德尔编码，由Steve Jessop在上面描述：

<?php

$sec = array(5,9,8,4);

$n = count($sec);
$max = max($sec);

$enc = encode($sec);
$dec = decode($enc, $n, $max);

echo "Input sequence:  " . implode(",", $sec) . "\n";
echo "Output sequence: " . implode(",", $dec) . "\n";
echo "Godel number:    " . $enc;
echo (PHP_INT_MAX/$enc < 20 ? " - too big to decode.\n" : "\n");

function encode($sec) {
    $primes = array(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53);
    $enc = 1;
    $i = 0;
    foreach ($sec as $v) {
        $enc = $enc * pow($primes[$i], $v+1);
        $i++;
    }
    return $enc;
}

function decode($enc, $n, $max) {
    $primes = array(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53);
    $sec = array();
    for ($i = 0; $i < $n; $i++) {
        for ($v = 2; $v <= $max+1; $v++) {
            if ($enc/pow($primes[$i], $v) != round($enc/pow($primes[$i], $v))) {
                break;
            }
        }
        $sec[] = $v-2;
    }
    return $sec;
}

?>

这个脚本只适用于小数字和小序列。它无法处理非常大的数字，我猜其他实现也一样。把数字连接起来存储甚至更容易更有效率：[01,05,15,17] -> 1051517。

- user2918060

Answer 5

如果您的数字范围是无限的，则无法实现。

自然数的幂集是不可数的。这意味着您无法提供数字集和数字之间的映射。

如果您的数字仅限于32位，那么您可以将数字连接成一个长二进制数字，并将它们作为字节序列存储，也许作为一个BigNum。

- Kendall Frey

---

如果输入序列的成员不是无限的，那么你肯定可以这样做。例如，如果最大的输入数字是9，你可以明确地将1,0,0,9写为1009。 - Eric J.

Answer 6

更新以检查0, 1情况。

用001分隔不同的数字。

为避免在您的数字内出现00时混淆，请每次出现0时将其替换为01。

要解码，请按001拆分。 将所有01替换为0。

- SJuan76

---

啊...我在想填充而不是分割。那么1,900900900，2怎么样？ - Eric J.

1,0 不起作用，因为它与 10,1 具有相同的编码。它不可逆转。 - Sean Owen

这种事情行不通。新想法的更简单的反例是：10013,7。编码是100130017。这也是1,30017的编码。 - Sean Owen

@SeanOwen 不是 10013,7 编码是 10101130017。1,30017 的编码是 1001301017。每当你看到 001，它就是一个断点。 - SJuan76

Answer 7

这里使用了通用编码，例如Elias omega编码（或任何前缀编码--但通用编码是带有一些理想属性的前缀编码）。 前缀编码将一个比特序列（即一个数字）编码为一个前缀，基本上提供了必要的信息来确定其余数字由多少位组成。

1）使用编码表示序列中元素的数量。 2）然后使用编码表示每个元素。

- Topher Cooper

Answer 8

我想到了另一个答案。使用平衡三进制对每个数字进行编码，每个三位数使用两个比特（例如，0=00；+1=01；-1=10）。剩余的比特对（例如，11）是元素结束标记，序列结束时重复。缺点：当预期有大量值时，比前缀代码的空间效率低；优点：1）在大多数小值情况下更节省空间；2）编码/解码更简单；3）直接表示负值。

- Topher Cooper