2

我们有这样的层次结构：

- 1 ( identifier = 100 )
  - 1 (101)
  - 2 (102)
  - 3 (103)
    - 1 (1031)
    - 2 (1032)
    - 3 (1033)
  - 4 (104)
    - 1 (1041)
    - 2 (1042)
    - 3 (1043)
  -901 (1001)
- 2 (200)
  - 1 (201)
  - 2 (202)
- 10 (1000)
  - 1 (1001)

要求的特性：

  • 每个节点的标识符应该是唯一的。
  • 标识符应根据元素的级别相应增加
  • 标识符应该是整数类型。
  • 每个元素的计数器在每个新级别/父元素处重置

正如您在元素 1.901 和 10.1 的示例中看到的那样，当前的实现不起作用。我们尝试了下一个解决方案：

  • 将每个级别乘以数字。
  • 仅将第一级乘以一个数字并添加每个子级

如果标识符是字符串，它会变得更加容易，在这种情况下，我们可以使用下一种方式：“level1.level2.level3...”，所以对于 1 -> 1，它将是“1.1”，依此类推。但这是最不需要的步骤。

那么，您能否建议任何可用于此处生成所需标识符的算法？

更新修复了示例。PS我知道这是错误的。

4

3 回答 3

3

你太沉迷于十进制数字了。

  1. 选择一个X代表节点内子节点最大数量的值，或者任何大于您认为方便使用的数字。
  2. 放弃对十进制数字的坚持，并将所有标识符表示为以 base 表示的整数X。
  3. 将标识符编码为基数中的整数，X其中第一个数字表示节点树的顶层，第二个数字表示第二级，依此类推。

所以，如果你很幸运并且合理的值X是 16，你可以使用整数的十六进制表示。如果 36 是一个不错的值，请使用任何字母数字字符作为数字。

编辑

正如 Rafael 所指出的，如果无法定义节点可以拥有的子节点数量的上限，那么这种方法就会失效。根据我的经验，这在实践中不太可能成为一个严重的问题。

如果 的值X很大，863那么我建议明显的实现是设置X = 1000和使用 3 个十进制数字组来表示 base 中的每个数字1000。这样，标识符12.245.1将表示为12245001.

现在我们进入了alestanis的回答已经涵盖的领域

于 2012-10-30T14:12:15.130 回答
1

首先，您的示例是错误的（100 映射到标识符 10000），但这并不意味着它有效。这就是为什么:

- 1 (100)
  -1 (101)
  ...
  -100 (200)
- 2 (200)

您需要一个工作示例确实是将每个级别乘以一个数字 N或者说相同，为每个级别保留 X 个数字。在您的情况下，您选择了N = 100，因此使示例正常工作所需的额外约束是每个级别不能超过N-1children。

如果您强制执行此约束，则元素 1.100 将是非法的，从而消除了重复的标识符。

使用N = 100（或X = 2）可以产生：

- 1 (01)
  - 1 (0101)
    - 1 (010101)
    ...
    - 3 (010103)
  ...
  - 99 (0199)
  - 100 is ILLEGAL
- 2 (02)
- 42 (42)
  - 42 (4242)

那么“问题”将是明智地选择X，以便在不限制用户的情况下最大限度地减少所需数字的数量。例如，如果您知道您永远不会添加超过 450 个孩子，请选择X=3。

于 2012-10-30T13:44:25.367 回答
1

这个问题有一个简单但内存成本高的解决方案：

每个节点位置可以很容易地表示为整数 i(1), i(2), ..., i(n) 的唯一有限序列：

  • 节点 1 = [1]
  • 节点 1.1 = [1, 1]
  • 节点 7.2.42 = [7, 2, 42]

因此，问题可以表示为如何将每个有限的整数序列映射到唯一的整数。这可以使用素数来完成

  • p(1) = 2
  • p(2) = 3
  • p(3) = 5
  • ...

只需乘以素数 p(n) 的 i(n):th 次方。结果整数的唯一性由素数分解的唯一性保证。参见维基百科： http ://en.wikipedia.org/wiki/Integer_factorization

例子：

  • 节点 1：2^ 1 = 2
  • 节点 1.1：2^ 1 * 3^ 1 = 6
  • 节点 7.2.42 : 2^ 7 * 3^ 2 * 5^ 42 = (巨大的数字！)

另一种可能的解决方案

从节点的字符串表示开始（例如“7.2.42”）。使用八进制数进行节点编号。使用“8”（八进制的第一个未使用的数字）来分隔级别而不是“.”。将结果字符串用作十进制整数。

例子：

  • 节点 1：1
  • 节点 1.1：181
  • 节点 1.2：182
  • 节点 1.3：183
  • 节点 7.7.7：78787
  • 节点 8 : 10
  • 节点 8.1：1081
  • 节点 8.2：1082
  • 节点 8.9：10811
  • 节点 8.9.1：1081181
  • 节点 8.9.2：1081182
于 2012-10-30T15:08:59.640 回答