1

我对如何将一组序列映射到连续整数感到困惑。

所有的序列都遵循这个规则：

A_0 = 1
A_n >= 1
A_n <= max(A_0 .. A_n-1) + 1

我正在寻找一种解决方案，它能够在给定这样的序列的情况下计算一个整数以查找表并给定表中的索引，生成序列。

示例：对于长度 3，有 5 个有效序列。执行以下地图（最好是双向）的快速功能将是一个很好的解决方案

1,1,1   0
1,1,2   1
1,2,1   2
1,2,2   3
1,2,3   4
  • 练习的重点是获得一个在有效序列和单元格之间具有 1-1 映射的打包表。
  • 集合的大小仅受可能的唯一序列数的限制。
  • 我现在不知道序列的长度是多少，但它会是一个很小的，<12，预先知道的常数。
  • 我迟早会谈到这个，但我会把它扔掉，让社区在此期间获得“乐趣”。

这些是不同的有效序列

1,1,2,3,2,1,4
1,1,2,3,1,2,4
1,2,3,4,5,6,7
1,1,1,1,2,3,2

这些不是

1,2,2,4
2,
1,1,2,3,5

与此相关

4

4 回答 4

1

我认为没有排序的哈希应该是事情。

由于 A0 总是以 0 开头，我认为我们可以将序列视为以 12 为底的数字，并使用其以 10 为底的数字作为查找的键。（仍然不确定这一点）。

于 2008-12-15T19:53:16.800 回答
1

有一个自然的序列索引，但没有那么容易计算。

因为 A_0 = 1，所以让我们寻找 n>0 的 A_n。

索引分两步完成。

第1部分：

按 A_n = max(A_0 .. A_n-1) + 1 的位置对序列进行分组。将这些位置称为步骤。

  • 上的步骤是连续的数字（2,3,4,5,...）。
  • 在非步数的地方，我们可以输入从 1 到索引小于 k 的步数。

每个组可以表示为二进制字符串，其中 1 是步进，0 是非步进。例如 001001010 表示具有 112aa3b4c、a<=2、b<=3、c<=4 的组。因为，组是用二进制数索引的，所以组的自然索引。从 0 到 2^length - 1。让我们调用 group 二进制表示group order的值。

第2部分：

组内的索引序列。由于组定义了步进位置，因此只有非步进位置上的数字是可变的，并且它们在定义的范围内是可变的。这样就可以很容易地在该组内索引给定组的序列，并按字典顺序排列变量位置。

很容易计算一组中的序列数。它是 1^i_1 * 2^i_2 * 3^i_3 * ... 形式的数字。

结合：

这给出了一个 2 部分键：<Steps, Group>然后需要将其映射到整数。为此，我们必须找出组中有多少序列的顺序小于某个值。为此，让我们首先找出给定长度的组中有多少个序列。这可以通过所有组和对序列的数量求和或类似的循环来计算。令 T(l, n) 为长度为 l 的序列数（省略 A_0），其中第一个元素的最大值可以是 n+1。比持有：

T(l,n) = n*T(l-1,n) + T(l-1,n+1)
T(1,n) = n

因为l + n <= sequence length + 1有sequence_length^2/2〜T（l，n）值，可以很容易地计算出来。

接下来是计算顺序小于或等于给定值的组中的序列数。这可以通过对 T(l,n) 值求和来完成。例如，顺序 <= 1001010 二进制的组中的序列数等于

T(7,1) +         # for 1000000
2^2 * T(4,2) +   # for 001000
2^2 * 3 * T(2,3) # for 010

优化：

这将给出一个映射，但最好是直接实现组合关键部分>O(1)。另一方面，Steps键的部分很小，通过计算Groups每个Steps值的范围，查找表可以将其减少到O(1).

我不是 100% 确定上面的公式，但它应该是这样的。

通过这些评论和重复，可以使函数序列 -> 索引和索引 -> 序列。但不是那么微不足道:-)

于 2010-12-07T14:39:17.463 回答
0

这是一个 python 函数，假设您将这些值存储在文件中并将这些行传递给函数，它可以为您完成这项工作

def valid_lines(lines):
    for line in lines:
        line = line.split(",")
        if line[0] == 1 and line[-1] and line[-1] <= max(line)+1:
            yield line

lines = (line for line in open('/tmp/numbers.txt'))
for valid_line in valid_lines(lines):
    print valid_line
于 2008-12-15T19:32:22.770 回答
0

给定序列，我会对它进行排序，然后使用排序序列的哈希作为表的索引。

于 2008-12-15T19:36:57.707 回答