如何使树模式适合约束但算法是通用的而不是硬编码的？
How to make tree pattern fit constraints but so algorithm is generic instead of hardcoded?
构建 ，下一个问题是，如何构建一个算法，将 index/integer 作为输入，并输出到树中适当节点的路径。树 可能 的结构示例如下，但我可能是错的。理想情况下会有一个模式，所有这些模式都遵循这样我们就可以有一个等式来将索引映射到路径。
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 级嵌套），同时减少算法的硬编码？你能以这样的方式重组这些树吗？
一些提示：
- 需要分成多少棵树？
- 给定这个数字，如何自动将数组分块到树中？
这将是一条漫长的道路...
因为我也找不到解决这个问题的数学公式，所以我寻求 data-driven 解决方案：查找 table 为我提供每个（可能）嵌套数组的形状个人尺寸（1 到 128 之间）。
一个形状可以用几个数字来定义：
- top-level个数，non-null个值
- 第一个子数组中 non-null 个值的数量（如果有的话）
- 如果有一个
，第二个子数组中non-null个值的数量
- 第三个子数组中non-null个值的个数，如果有的话
- 第四个子数组中non-null个值的个数，如果有的话
可以从这些信息中推断出潜在的 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
]
请注意，达到 2 的幂涉及 null 个值。顶层有（包括最后的 null）32 个元素。前两个内部子数组的总大小为 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];
}
}
}
}
}
}
我承认这段代码并不优雅，有很多代码重复，但它达到了预期目的：它为任何给定的数组大小生成一个形状（上面解释的一组数字）。
用 less 编码形状 space
子数组的数字不能是任意数字。它们必须是 2 的幂，或者少一（当假定一个填充 null 时）或少二（当假定两个 null 值时）。所以可能的数字在这个集合中：
[1, 2, 3, 4, 6, 7, 8, 14, 15, 16, 30, 31, 32]
第一个数字（表示顶层值的计数）也可以在该集合中，但也可以在 27 - 29 范围内。这是因为 [=81 后面的子数组=]和 潜在的null 填充也计算在顶层达到 2 的幂。这意味着形状“编码”的第一个位置恰好有 16 个可能的数字。我们可以通过将这些数字映射到 4 位值（给出 16 种可能性）来压缩此编码。事实证明，所需的子数组永远不会超过 4 个，我们将需要 20 位来编码一个形状。
现在我们应该确定 128 个形状的这些 20 位数字是什么，并将它们收集在一个数组中，该数组可以用作查找 table。
这是将数字编码为 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)));
}
构建
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 级嵌套），同时减少算法的硬编码？你能以这样的方式重组这些树吗？
一些提示：
- 需要分成多少棵树？
- 给定这个数字，如何自动将数组分块到树中？
这将是一条漫长的道路...
因为我也找不到解决这个问题的数学公式，所以我寻求 data-driven 解决方案：查找 table 为我提供每个（可能）嵌套数组的形状个人尺寸（1 到 128 之间）。
一个形状可以用几个数字来定义：
- top-level个数，non-null个值
- 第一个子数组中 non-null 个值的数量（如果有的话）
- 如果有一个 ，第二个子数组中non-null个值的数量
- 第三个子数组中non-null个值的个数，如果有的话
- 第四个子数组中non-null个值的个数，如果有的话
可以从这些信息中推断出潜在的 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
]
请注意，达到 2 的幂涉及 null 个值。顶层有（包括最后的 null）32 个元素。前两个内部子数组的总大小为 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];
}
}
}
}
}
}
我承认这段代码并不优雅，有很多代码重复，但它达到了预期目的：它为任何给定的数组大小生成一个形状（上面解释的一组数字）。
用 less 编码形状 space
子数组的数字不能是任意数字。它们必须是 2 的幂，或者少一（当假定一个填充 null 时）或少二（当假定两个 null 值时）。所以可能的数字在这个集合中：
[1, 2, 3, 4, 6, 7, 8, 14, 15, 16, 30, 31, 32]
第一个数字（表示顶层值的计数）也可以在该集合中，但也可以在 27 - 29 范围内。这是因为 [=81 后面的子数组=]和 潜在的null 填充也计算在顶层达到 2 的幂。这意味着形状“编码”的第一个位置恰好有 16 个可能的数字。我们可以通过将这些数字映射到 4 位值（给出 16 种可能性）来压缩此编码。事实证明，所需的子数组永远不会超过 4 个，我们将需要 20 位来编码一个形状。
现在我们应该确定 128 个形状的这些 20 位数字是什么，并将它们收集在一个数组中，该数组可以用作查找 table。
这是将数字编码为 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)));
}