如果能结合3+任意大小的整数，并仍然能够解构回

问题描述 投票：0回答：1

假设你有3个整数：

13105
705016
13

我想知道，如果你能以任何方式将其组合到一个整数，这样你仍然可以回到原来的3个整数。

var startingSet = [ 13105, 705016, 13 ]
var combined = combineIntoOneInteger(startingSet)
// 15158958589285958925895292589 perhaps, I have no idea.
var originalIntegers = deconstructInteger(combined, 3) 
// [ 13105, 705016, 13 ]

function combineIntoOneInteger(integers) {
  // some sort of hashing-like function...
}

function deconstructInteger(integer, arraySize) {
  // perhaps pass it some other parameters 
  // like how many to deconstruct to, or other params.
}

它并不需要在技术上是一个“整数”。这仅仅是只使用整数字元，不过也许我可能要使用十六进制字符，而不是一个字符串。但我在整数方面提出，因为下面我有将被用于构建组合对象有界大小的整数。

其他一些注意事项....

  • 总价值应该是唯一的，所以无论你把什么样的价值观，你总是会得到不同的结果。也就是说，绝对不存在冲突。或者，如果这是不可能的，也许是解释为何以及潜在的解决方法。
  • 数学“集合”包含所有可能的输出可以由不同数量的部件构成。也就是说，你可能有包含[ 100, 200, 300, 400 ]输出/组合集，但输入的设定是这4个数组：[ [ 1, 2, 3 ], [ 5 ], [ 91010, 132 ], [ 500, 600, 700 ] ]。也就是说，输入数组可以是完全不同的长度和完全不同的尺寸的整数。
  • 一种方法更一般地完成，这是只使用一个“分隔符”字，这使得它超级简单。因此，它会像13105:705016:13。但是，这是欺骗，我希望它只是在整组使用的字符（或者也许是六角固定，或一些其他任意设置，但这种情况下，仅仅是整数设置或十六进制）。
  • 为做到这一点的潜在方法另一个想法是做一些散列或置换柔术以某种方式隐藏在那里的分隔，使[ 13105, 705016, 13 ]成为一些整数找东西一样95918155193915183，其中155和5就像插值有一些分离基础上，前面的输入或其他一些技巧。这种更简单的方法就好像说：“任何事以下三个零000像410001414意味着它是一个新的整数。所以基本上000是一个分隔符。但是，这特别是丑陋而脆。也许它会得到更多的技巧和工作，虽然，像”如果值是奇数和随后的自身3的倍数，那么它是一个分隔符”之类的事情，但我可以看到，也有脆弱的边缘情况。

但基本上，给定一组整数n，如何将其转换成一个整数（或单整了表征字符串），然后将其转换回原始整数集n的（整数字符的字符串）。

parsing hash integer
1个回答
1
投票

当然，有很多方法可以做到这一点。

若要开始，它只是需要有一个可逆函数将两个值转换成一个。 （对于它是可逆的，必须有另一个函数，它接受的输出值，并重新创建两个输入值）。

让我们把它结合了两个值combine和反向功能separate功能。然后我们有：

separate(combine(a, b)) == [a, b]

对于任何值a和b。这意味着，combine(a, b) == combine(c, d)只能是真如果两个a == c和b == d;换句话说，每对输入产生不同的输出。

Encoding arbitrary vectors

一旦我们有功能，我们可以编码任意长度的输入向量。最简单的情况是，当我们预先知道向量的长度是什么。例如，我们可以定义：

combine3 = (a, b, c) => combine(combine(a, b), c)
combine4 = (a, b, c, d) => combine(combine(combine(a, b), c), d)

等等。为了扭转这一计算，我们只需要多次拨打separate正确的次数，每次保持第二返回的值。举例来说，如果我们先前的计算：

m = combine4(a, b, c, d)

我们可以得到四个输入值回如下：

c3, d = separate(m)
c2, c = separate(c3)
a, b  = separate(c2)

但是你的问题问的办法值任意数量的结合。为了做到这一点，我们需要做的最后一个combine，其在混合值的数量。这让我们得到原始载体退了出来：第一，我们称之为separate获得价值数退了出来，然后我们调用足够的时间分开来提取每个连续的输入值。

combine_n = v => combine(v.reduce(combine), v.length)
function separate_n(m) {
  let [r, n] = separate(m)
  let a = Array(n)
  for (let i = n - 1; i > 0; --i) [r, a[i]] = separate(r);
  a[0] = r;
  return a;
}

需要注意的是，上述两种功能不要在空载体，它应该在代码为0。对于这种情况下，作为一个练习添加正确的检查工作。还要注意对这个答案的底部，约整数溢出的警告。

A simple combine function: diagonalization

做完这些后，让我们来看看如何实现combine。实际上有许多解决方案，但一个非常简单的一种是使用对角化功能：

 diag(a, b) = (a + b)(a + b + 1)
              ------------------ + a
                        2

这基本上通过跟踪连续对角线分配在无限方的位置：

        <-- b -->
    0  1  3  6 10 15 21 ...
 ^  2  4  7 11 16 22 ...
 |  5  8 12 17 23 ...
 a  9 13 18 24 ...
 | 14 19 25 ...
 v 20 26 ...
   27 ...

（在此答案的早期版本，我已经扭转a和b，但这个版本似乎有稍微更直观的输出值。）

需要注意的是最上面一行，其中a == 0，正是triangular numbers，因为已经列举的位置是正方形的左上角的三角形，这并不奇怪。

要反转变换，我们开始通过求解限定三角形号码，m = s(s + 1)/2方程，这是相同的

0 = s² + s - 2m

其solution可以使用标准quadratic formula，导致找到：

s = floor((-1 + sqrt(1 + 8 * m)) / 2)

（这里s是原始a+b;即，对角线的索引）

我要解释的呼叫floor其悄悄在那里。 s只会正是在广场，在那里a为0。但是，当然，a通常不会为0的最上面一行的整数，m通常会比我们要寻找的三角形数量多一点，所以当我们解决s，我们会得到一些分数值。 Floor只是丢弃小数部分，所以结果是对角线指数。

现在，我们只需要恢复a和b，这是直接的：

a = m - combine(0, s)
b = s - a

所以我们现在有combine和separate的定义：

let combine = (a, b) => (a + b) * (a + b + 1) / 2 + a

function separate(m) {
  let s = Math.floor((-1 + Math.sqrt(1 + 8 * m)) / 2);
  let a = m - combine(0, s);
  let b = s - a;
  return [a, b];
}

这个特定的编码之一凉特征是，每一个非负整数对应于不同载体中。许多其他的编码方案没有这个属性; combine_n的可能的返回值是一组非负整数的子集。

Example encodings

作为参考，这里是第一30个编码的值，和所述载体它们代表：

> for (let i = 1; i <= 30; ++i) console.log(i, separate_n(i));
 1 [ 0 ]
 2 [ 1 ]
 3 [ 0, 0 ]
 4 [ 1 ]
 5 [ 2 ]
 6 [ 0, 0, 0 ]
 7 [ 0, 1 ]
 8 [ 2 ]
 9 [ 3 ]
10 [ 0, 0, 0, 0 ]
11 [ 0, 0, 1 ]
12 [ 1, 0 ]
13 [ 3 ]
14 [ 4 ]
15 [ 0, 0, 0, 0, 0 ]
16 [ 0, 0, 0, 1 ]
17 [ 0, 1, 0 ]
18 [ 0, 2 ]
19 [ 4 ]
20 [ 5 ]
21 [ 0, 0, 0, 0, 0, 0 ]
22 [ 0, 0, 0, 0, 1 ]
23 [ 0, 0, 1, 0 ]
24 [ 0, 0, 2 ]
25 [ 1, 1 ]
26 [ 5 ]
27 [ 6 ]
28 [ 0, 0, 0, 0, 0, 0, 0 ]
29 [ 0, 0, 0, 0, 0, 1 ]
30 [ 0, 0, 0, 1, 0 ]

Warning!

注意，所有未编码的值是相当小的。该编码值的大小与所有输入值的串联相似，所以它非常快速增长;你必须要小心不要超过JavaScript的确切上计算整数限制。一旦编码值超过该极限（253），它将不再能够扭转的编码。如果输入向量是长和/或编码值大，你需要找到某种BIGNUM支持才能做到精确的整数计算。

Alternative combine functions

另一种可能的实现combine的是：

let combine = (a, b) => 2**a * 3**b

事实上，使用素数的权力，我们可以与combine_n序列分配，而直接产生的组合：

combine(a, b, c, d, e,...) = 2a 3b 5c 7d 11e ...

（这假设编码值是严格为正;如果他们可能是0，我们就无法知道该序列有多长，因为编码值不向量再用0相同的矢量附加区分的方法，但是。这不是一个大问题，因为如果我们需要对付0，我们将只添加一个到所有使用指数：

combine(a, b, c, d, e,...) = 2a+1 3b+1 5c+1 7d+1 11e+1 ...

这当然是正确的和它的理论意义非常优雅。这是你将在理论CS教科书找到，因为它是很容易证明的独特性和可逆性的解决方案。然而，在现实世界中实在是不实际的。倒车组合取决于找到编码值的主要因素，而编码值是真正巨大的，也很容易出表示数字的范围。

另一种可能性是正是你的问题提了一句：干脆把连续值之间的分隔符。一种简单的方法来做到这一点是重写的值在基座9（或底座15）来编码，然后递增所有数位值，从而使位0不存在于任何编码值。然后，我们可以把编码的值之间的0和读出的结果在基座10（或底座16）。

这些解决方案都具有每个非负整数是一些矢量的编码的属性。 （第二个几乎都有财产，这是一项有益的工作，以找出哪些整数是不可能的编码，然后固定编码算法来避免这个问题。）

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.