如何使树型适合约束条件，但算法是通用的，而不是硬编码的？

Question

在this question的基础上，下一个问题是，如何构建一个以索引/整数作为输入的算法，并将路径输出到树中的适当节点。树的结构示例如下，但我可能错了。理想情况下，他们都会遵循这样的模式，这样我们就可以有一个方程来将索引映射到路径。

base-1
  a

base-2
  a
  b

base-3
  a
  b
  c
  null

base-4
  a
  b
  c
  d

base-5
  a
  b
  c
  tree
    d
    e

base-6
  a
  b
  c
  d
  e
  f
  null
  null

base-7
  a
  b
  c
  d
  e
  f
  g
  null

base-8
  a
  b
  c
  d
  e
  f
  g
  h

base-9
  a
  b
  c
  d
  e
  f
  g
  tree
    h
    i

base-10
  a
  b
  c
  d
  e
  f
  g
  tree
    h
    i
    j
    null

base-11
  a
  b
  c
  d
  e
  f
  g
  tree
    h
    i
    j
    k

base-12
  a
  b
  c
  d
  e
  f
  tree
    g
    h
    i
    j
  tree
    k
    l

base-13
  a
  b
  c
  d
  e
  f
  g
  tree
    h
    i
    j
    k
    l
    m
    null
    null

base-14
  a
  b
  c
  d
  e
  f
  g
  tree
    h
    i
    j
    k
    l
    m
    n
    null

base-15
  a
  b
  c
  d
  e
  f
  g
  tree
    h
    i
    j
    k
    l
    m
    n
    o

base-16
  a
  b
  c
  d
  e
  f
  g
  h
  i
  j
  k
  l
  m
  n
  o
  p

base-17
  a
  b
  c
  d
  e
  f
  g
  h
  i
  j
  k
  l
  m
  n
  o
  tree
    p
    q

base-18
  a
  b
  c
  d
  e
  f
  g
  h
  i
  j
  k
  l
  m
  n
  o
  tree
    p
    q
    r
    null

base-19
  a
  b
  c
  d
  e
  f
  g
  h
  i
  j
  k
  l
  m
  n
  o
  tree
    p
    q
    r
    s

base-20
  a
  b
  c
  d
  e
  f
  tree
    g
    h
    i
    j
    k
    l
    m
    n
  tree
    o
    p
    q
    r
    s
    t
    null
    null

base-21
  a
  b
  c
  d
  e
  f
  tree
    g
    h
    i
    j
    k
    l
    m
    n
  tree
    o
    p
    q
    r
    s
    t
    u
    null

base-22
  a
  b
  c
  d
  e
  f
  g
  h
  i
  j
  k
  l
  m
  n
  o
  tree
    p
    q
    r
    s
    t
    u
    v
    null

base-23
  a
  b
  c
  d
  e
  f
  g
  h
  i
  j
  k
  l
  m
  n
  o
  tree
    p
    q
    r
    s
    t
    u
    v
    w

base-24
  a
  b
  c
  d
  e
  f
  g
  h
  i
  j
  k
  l
  m
  n
  tree
    o
    p
    q
    r
    s
    t
    u
    v
  tree
    w
    x

base-25
  a
  b
  c
  d
  e
  f
  g
  h
  i
  j
  k
  l
  m
  n
  tree
    o
    p
    q
    r
    s
    t
    u
    v
  tree
    w
    x
    y
    null

base-26
  a
  b
  c
  d
  e
  f
  g
  h
  i
  j
  k
  l
  m
  n
  tree
    o
    p
    q
    r
    s
    t
    u
    v
  tree
    w
    x
    y
    z

base-27
  a
  b
  c
  d
  e
  f
  g
  h
  i
  j
  k
  l
  m
  tree
    n
    o
    p
    q
    r
    s
    t
    u
  tree
    v
    w
    x
    y
  tree
    z
    aa

base-28
  a
  b
  c
  d
  e
  f
  g
  h
  i
  j
  k
  l
  m
  n
  tree
    o
    p
    q
    r
    s
    t
    u
    v
  tree
    w
    x
    y
    z
    aa
    ab
    null
    null

base-29
  a
  b
  c
  d
  e
  f
  g
  h
  i
  j
  k
  l
  m
  n
  o
  tree
    p
    q
    r
    s
    t
    u
    v
    w
    x
    y
    z
    aa
    ab
    ac
    null
    null

base-30
  a
  b
  c
  d
  e
  f
  g
  h
  i
  j
  k
  l
  m
  n
  o
  p
  q
  r
  s
  t
  u
  v
  w
  x
  y
  z
  aa
  ab
  ac
  ad
  null
  null

base-31
  a
  b
  c
  d
  e
  f
  g
  h
  i
  j
  k
  l
  m
  n
  o
  p
  q
  r
  s
  t
  u
  v
  w
  x
  y
  z
  aa
  ab
  ac
  ad
  ae
  null

base-32
  a
  b
  c
  d
  e
  f
  g
  h
  i
  j
  k
  l
  m
  n
  o
  p
  q
  r
  s
  t
  u
  v
  w
  x
  y
  z
  aa
  ab
  ac
  ad
  ae
  af

每个级别只能有32个可能的项目，最多有2个级别。每棵树只能有2个元素的幂。在某些情况下，我使用null，因为与添加新树相比，它需要更少的节点或更少的遍历。如果没有一致的模式，您可以创建一个适当的相似模式，如果找不到精确的模式。理想情况下，存在一个模式，因此可以使用一个等式从索引生成路径。

还有一些需要注意的事情：

在列表开始时，

• 总是以最多填充的最高级别开始，最多为8或更多的2空值。

。

我的尝试仍然是硬编码的。

function getPathFromIndex(size, index) {
  if (size < 5) {
    return [index]
  }

  if (size === 5) {
    if (index > 2) {
      return [2, index - 3]
    } else {
      return [index]
    }
  }

  if (size < 9) {
    return [index]
  }

  if (size < 12) {
    if (index > 6) {
      return [6, index - 7]
    } else {
      return [index]
    }
  }

  // continue hardcoding.
}

是否有一种方法可以实现类似的目标(只有2的约束，只有1级嵌套)，但却减少了算法的硬编码？你能以这样的方式重组树木吗？

一些提示：

• 它需要分成多少棵树?给定这个数字的
• ，如何自动地将数组块块到树中？

Answer 1

这将是一条漫长的道路.

由于我也找不到解决这个问题的数学公式，所以我选择了一个数据驱动的解决方案:一个查找表，它为每个大小(1到128之间)提供了(可能的)嵌套数组的形状。

形状可以由几个数字定义：

如果第一个子数组中有一个

• ，那么第二个子数组中的非空值数如果有一个
• ，则第三个子数组中的非空值数如果有一个
• 第四个子数组中的非空值数(如果有一个h 210f 211则为非空值)。

从这些信息可以推断出潜在的null填充，因为我们知道必须达到2的幂。

举个例子：

尺寸= 102

这可以用以下数字表示：

28、30、30和14

这意味着这个大小的数组将如下所示：

[
    0,
    1,
    2,
    3,
    ...,
    27,
    [28, 29,..., 57, null, null],
    [58, 59,..., 87, null, null],
    [88, 89,..., 101, null, null],
    null
]

请注意，需要使用null值来达到2的幂。顶层有32个元素(包括最终的null)。前两个内部子数组的总大小为32 (包括填充的null值)，第三个数组有16个元素(也包括填充)。

生成形状

为了避免手动确定128个数组大小中的每个形状，我编写了一个蛮力函数来对每个大小进行有效的形状选择。我只是用来修复这些形状的，而不是最终解决方案的一部分：

function shape(n) { // Returns number of atomic entries, followed by data-size(s) of subarrays
    const greatestPowerOf2 = (n) => 
        n >= 32 ? 32 : n >= 16 ? 16 : n >= 8 ? 8 : n >= 4 ? 4 : n >= 2 ? 2 : 1;

    let p = greatestPowerOf2(n+2);
    if (p >= n) {
        // The only cases where there are no subarrays
        return [n];
    }
    // Try with one subarray
    for (let sub = 2; sub < n && sub <= 32; sub *= 2) {
        let maxInnerNulls = sub == 2 ? 0 : sub == 4 ? 1 : 2;
        let top = n - sub + 1;
        p = greatestPowerOf2(top+2+maxInnerNulls);
        if (p >= top) {
            let nulls = p - top;
            let innerNulls = Math.min(maxInnerNulls, nulls);
            nulls -= innerNulls;
            return [p - 1 - nulls, sub - innerNulls];
        }
    }
    // Try with two subarrays
    for (let sub1 = 2; sub1 < n && sub1 <= 32; sub1 *= 2) {
        let maxInnerNulls1 = sub1 == 2 ? 0 : sub1 == 4 ? 1 : 2;
        for (let sub2 = 2; sub2 <= sub1; sub2 *= 2) {
            let top = n - sub1 - sub2 + 2;
            if (top < 0) break;
            let maxInnerNulls2 = sub2 == 2 ? 0 : sub2 == 4 ? 1 : 2;
            p = greatestPowerOf2(top+2+maxInnerNulls1+maxInnerNulls2);
            if (p >= top) {
                let nulls = p - top;
                let innerNulls1 = Math.min(maxInnerNulls1, nulls);
                nulls -= innerNulls1;
                let innerNulls2 = Math.min(maxInnerNulls2, nulls);
                nulls -= innerNulls2;
                return [p - 2 - nulls, sub1 - innerNulls1, sub2 - innerNulls2];
            }
        }
    }
    // Try with three subarrays
    for (let sub1 = 2; sub1 < n && sub1 <= 32; sub1 *= 2) {
        let maxInnerNulls1 = sub1 == 2 ? 0 : sub1 == 4 ? 1 : 2;
        for (let sub2 = 2; sub2 <= sub1; sub2 *= 2) {
            let maxInnerNulls2 = sub2 == 2 ? 0 : sub2 == 4 ? 1 : 2;
            for (let sub3 = 2; sub3 <= sub2; sub3 *= 2) {
                let top = n - sub1 - sub2 - sub3 + 3;
                if (top < 0) break;
                let maxInnerNulls3 = sub3 == 2 ? 0 : sub3 == 4 ? 1 : 2;
                p = greatestPowerOf2(top+2+maxInnerNulls1+maxInnerNulls2+maxInnerNulls3);
                if (p >= top) {
                    let nulls = p - top;
                    let innerNulls1 = Math.min(maxInnerNulls1, nulls);
                    nulls -= innerNulls1;
                    let innerNulls2 = Math.min(maxInnerNulls2, nulls);
                    nulls -= innerNulls2;
                    let innerNulls3 = Math.min(maxInnerNulls3, nulls);
                    nulls -= innerNulls3;
                    return [p - 3 - nulls, sub1 - innerNulls1, sub2 - innerNulls2, sub3 - innerNulls3];
                }
            }
        }
    }
    // Try with four subarrays
    for (let sub1 = 2; sub1 < n && sub1 <= 32; sub1 *= 2) {
        let maxInnerNulls1 = sub1 == 2 ? 0 : sub1 == 4 ? 1 : 2;
        for (let sub2 = 2; sub2 <= sub1; sub2 *= 2) {
            let maxInnerNulls2 = sub2 == 2 ? 0 : sub2 == 4 ? 1 : 2;
            for (let sub3 = 2; sub3 <= sub2; sub3 *= 2) {
                let maxInnerNulls3 = sub3 == 2 ? 0 : sub3 == 4 ? 1 : 2;
                for (let sub4 = 2; sub4 <= sub3; sub4 *= 2) {
                    let top = n - sub1 - sub2 - sub3 - sub4 + 4;
                    if (top < 0) break;
                    let maxInnerNulls4 = sub4 == 2 ? 0 : sub4 == 4 ? 1 : 2;
                    p = greatestPowerOf2(top+2+maxInnerNulls1+maxInnerNulls2+maxInnerNulls3+maxInnerNulls4);
                    if (p >= top) {
                        let nulls = p - top;
                        let innerNulls1 = Math.min(maxInnerNulls1, nulls);
                        nulls -= innerNulls1;
                        let innerNulls2 = Math.min(maxInnerNulls2, nulls);
                        nulls -= innerNulls2;
                        let innerNulls3 = Math.min(maxInnerNulls3, nulls);
                        nulls -= innerNulls3;
                        let innerNulls4 = Math.min(maxInnerNulls4, nulls);
                        nulls -= innerNulls4;
                        return [p - 4 - nulls, sub1 - innerNulls1, sub2 - innerNulls2, sub3 - innerNulls3, sub4 - innerNulls4];
                    }
                }
            }
        }
    }
}

我承认这段代码并不优雅，重复了很多代码，但它达到了预期的目的:它为任何给定的数组大小生成一个形状(上面解释的一组数字)。

在较小的空间中编码形状

子数组的数字不能只是任何数字。它们要么是2的幂，要么是少一个(假设一个填充null )，或者是两个少(假设有两个null值)。因此，可能的数字在这组中：

[1, 2, 3, 4, 6, 7, 8, 14, 15, 16, 30, 31, 32]

第一个数字(表示顶级值的计数)也可以在该集合中，但也可以在27-29范围内。这是因为后面的子数组和潜在的null填充也意味着在顶层达到2的幂。这意味着，形状“编码”的第一个位置正好有16个可能的数字。我们可以通过将这些数字映射到4位值(提供16种可能性)来压缩这种编码。事实证明，需要的子数组不超过4个，我们需要20位来编码形状。

现在，我们应该确定128种形状的这20位数字是什么，并将它们收集到一个可以用作查找表的数组中。

下面是将数字编码成20位编码的函数：

function encode(shapeNumbers) {
    let code = 0;
    for (let i = shapeNumbers.length - 1; i >= 0; i--) {
        code = code*16 + [1,2,3,4,6,7,8,14,15,16,27,28,29,30,31,32].indexOf(shapeNumbers[i]);
    }
    return code;
}

我用这个函数收集代码：

function collectCodes() {
    let codes = [null];
    for (let n = 1; n <= 128; n++) {
        let shapeNumbers = shape(n);
        let code = encode(shapeNumbers);
        codes.push(code);
    }
    return codes;
}

​

function shape(n) { // Returns number of atomic entries, followed by data-size(s) of subarrays
    const greatestPowerOf2 = (n) => 
        n >= 32 ? 32 : n >= 16 ? 16 : n >= 8 ? 8 : n >= 4 ? 4 : n >= 2 ? 2 : 1;

    let p = greatestPowerOf2(n+2);
    if (p >= n) {
        // The only cases where there are no subarrays
        return [n];
    }
    // Try with one subarray
    for (let sub = 2; sub < n && sub <= 32; sub *= 2) {
        let maxInnerNulls = sub == 2 ? 0 : sub == 4 ? 1 : 2;
        let top = n - sub + 1;
        p = greatestPowerOf2(top+2+maxInnerNulls);
        if (p >= top && p <= 32) {
            let nulls = p - top;
            let innerNulls = Math.min(maxInnerNulls, nulls);
            nulls -= innerNulls;
            return [p - 1 - nulls, sub - innerNulls];
        }
    }
    // Try with two subarrays
    for (let sub1 = 2; sub1 < n && sub1 <= 32; sub1 *= 2) {
        let maxInnerNulls1 = sub1 == 2 ? 0 : sub1 == 4 ? 1 : 2;
        for (let sub2 = 2; sub2 <= sub1; sub2 *= 2) {
            let top = n - sub1 - sub2 + 2;
            if (top < 0) break;
            let maxInnerNulls2 = sub2 == 2 ? 0 : sub2 == 4 ? 1 : 2;
            p = greatestPowerOf2(top+2+maxInnerNulls1+maxInnerNulls2);
            if (p >= top && p <= 32) {
                let nulls = p - top;
                let innerNulls1 = Math.min(maxInnerNulls1, nulls);
                nulls -= innerNulls1;
                let innerNulls2 = Math.min(maxInnerNulls2, nulls);
                nulls -= innerNulls2;
                return [p - 2 - nulls, sub1 - innerNulls1, sub2 - innerNulls2];
            }
        }
    }
    // Try with three subarrays
    for (let sub1 = 2; sub1 < n && sub1 <= 32; sub1 *= 2) {
        let maxInnerNulls1 = sub1 == 2 ? 0 : sub1 == 4 ? 1 : 2;
        for (let sub2 = 2; sub2 <= sub1; sub2 *= 2) {
            let maxInnerNulls2 = sub2 == 2 ? 0 : sub2 == 4 ? 1 : 2;
            for (let sub3 = 2; sub3 <= sub2; sub3 *= 2) {
                let top = n - sub1 - sub2 - sub3 + 3;
                if (top < 0) break;
                let maxInnerNulls3 = sub3 == 2 ? 0 : sub3 == 4 ? 1 : 2;
                p = greatestPowerOf2(top+2+maxInnerNulls1+maxInnerNulls2+maxInnerNulls3);
                if (p >= top && p <= 32) {
                    let nulls = p - top;
                    let innerNulls1 = Math.min(maxInnerNulls1, nulls);
                    nulls -= innerNulls1;
                    let innerNulls2 = Math.min(maxInnerNulls2, nulls);
                    nulls -= innerNulls2;
                    let innerNulls3 = Math.min(maxInnerNulls3, nulls);
                    nulls -= innerNulls3;
                    return [p - 3 - nulls, sub1 - innerNulls1, sub2 - innerNulls2, sub3 - innerNulls3];
                }
            }
        }
    }
    // Try with four subarrays
    for (let sub1 = 2; sub1 < n && sub1 <= 32; sub1 *= 2) {
        let maxInnerNulls1 = sub1 == 2 ? 0 : sub1 == 4 ? 1 : 2;
        for (let sub2 = 2; sub2 <= sub1; sub2 *= 2) {
            let maxInnerNulls2 = sub2 == 2 ? 0 : sub2 == 4 ? 1 : 2;
            for (let sub3 = 2; sub3 <= sub2; sub3 *= 2) {
                let maxInnerNulls3 = sub3 == 2 ? 0 : sub3 == 4 ? 1 : 2;
                for (let sub4 = 2; sub4 <= sub3; sub4 *= 2) {
                    let top = n - sub1 - sub2 - sub3 - sub4 + 4;
                    if (top < 0) break;
                    let maxInnerNulls4 = sub4 == 2 ? 0 : sub4 == 4 ? 1 : 2;
                    p = greatestPowerOf2(top+2+maxInnerNulls1+maxInnerNulls2+maxInnerNulls3+maxInnerNulls4);
                    if (p >= top && p <= 32) {
                        let nulls = p - top;
                        let innerNulls1 = Math.min(maxInnerNulls1, nulls);
                        nulls -= innerNulls1;
                        let innerNulls2 = Math.min(maxInnerNulls2, nulls);
                        nulls -= innerNulls2;
                        let innerNulls3 = Math.min(maxInnerNulls3, nulls);
                        nulls -= innerNulls3;
                        let innerNulls4 = Math.min(maxInnerNulls4, nulls);
                        nulls -= innerNulls4;
                        return [p - 4 - nulls, sub1 - innerNulls1, sub2 - innerNulls2, sub3 - innerNulls3, sub4 - innerNulls4];
                    }
                }
            }
        }
    }
}

function encode(shapeNumbers) {
    let code = 0;
    for (let i = shapeNumbers.length - 1; i >= 0; i--) {
        code = code*16 + [1,2,3,4,6,7,8,14,15,16,27,28,29,30,31,32].indexOf(shapeNumbers[i]);
    }
    return code;
}

function collectCodes() {
    let codes = [null];
    for (let n = 1; n <= 128; n++) {
        let shapeNumbers = shape(n);
        let code = encode(shapeNumbers);
        codes.push(code);
    }
    return codes;
}

console.log(JSON.stringify(collectCodes()));

​

这产生了这样的结果：

[null,0,1,2,3,18,4,5,6,21,37,53,68,69,7,8,9,24,40,56,71,72,88,104,359,855,871,111,119,120,13,14,15,30,46,62,77,78,94,110,365,861,877,124,125,126,142,158,413,909,925,1405,1661,1677,1693,5788,1915,1916,1917,220,221,222,238,254,509,1005,1021,1501,1757,1773,1789,30588,2011,2012,2013,2269,2525,2541,2557,6652,14828,14844,26844,27100,27116,27132,30683,30684,3547,3548,3549,3805,4061,4077,4093,8188,16364,16380,28380,28636,28652,28668,32219,32220,36316,40412,40668,40924,40940,40956,106491,237547,237563,433883,434139,434155,434171,56794,56795,56796,60892,64988,65244,65500,65516,65532,131067,262123,262139]

解决方案代码

既然我们有了这些功能，就可以丢弃上面的JavaScript函数了。这个数组具有复制形状或将索引转换为路径所需的信息。

​

const codes = [null,0,1,2,3,18,4,5,6,21,37,53,68,69,7,8,9,24,40,56,71,72,88,104,359,855,871,111,119,120,13,14,15,30,46,62,77,78,94,110,365,861,877,124,125,126,142,158,413,909,925,1405,1661,1677,1693,5788,1915,1916,1917,220,221,222,238,254,509,1005,1021,1501,1757,1773,1789,30588,2011,2012,2013,2269,2525,2541,2557,6652,14828,14844,26844,27100,27116,27132,30683,30684,3547,3548,3549,3805,4061,4077,4093,8188,16364,16380,28380,28636,28652,28668,32219,32220,36316,40412,40668,40924,40940,40956,106491,237547,237563,433883,434139,434155,434171,56794,56795,56796,60892,64988,65244,65500,65516,65532,131067,262123,262139];

const codeMap = [1,2,3,4,6,7,8,14,15,16,27,28,29,30,31,32];

function getPath(size, i) {
    let code = codes[size];
    let limit = codeMap[code % 16];
    if (i < limit) return [i];
    for (let sub = limit; code; sub++) {
        i -= limit;
        code >>= 4;
        limit = codeMap[code % 16];
        if (i < limit) return [sub, i];
    }
}

// Demo with size 28
let size = 28;
for (let i = 0; i < size; i++) {
    console.log(i, JSON.stringify(getPath(size, i)));
}

​