在這個問題的基礎上，下一個問題是，如何構建一個將索引/整數作為輸入的演算法，并將路徑輸出到樹中的適當節點。樹的結構示例如下，但我可能錯了。理想情況下，它們都會遵循一種模式，因此我們可以有一個方程式將索引映射到路徑。
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
There can only be 32 possible items in each level, and max 2 levels. Each tree can only have power-of-2 number of elements. In some cases I put null because it requires less nodes or less traversal than adding a new tree. If there is not a consistent pattern to it, you can create an appropriate similar pattern if no precise pattern is found. Ideally there is a pattern so an equation can be used to generate the path from an index.
Some other things to note:
- Always start the list with the top-most levels filled out as much as possible.
- Allow up to 2 null values on 8 or more.
My attempt is pretty hardcoded still.
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.
}
Is there a way of accomplishing a similar goal (with the power of 2 constraint, and only 1 level of nesting), yet make the algorithm less hardcoded? Can you restructure the trees in such a way to make that possible?
Some hints:
- How many trees does it need to be divided into?
- Given that number, how to automatically chunk the array into the tree?
uj5u.com熱心網友回復：
這將是一條漫長的道路……
由于我也找不到一個數學公式來解決這個問題，我選擇了一個資料驅動的解決方案：一個查找表，它為我提供了每個單獨大小（1 到 128 之間）的（可能）嵌套陣列的形狀。
一個形狀可以由幾個數字定義：
- 頂級非空值的數量
- 第一個子陣列中非空值的數量（如果有一個）
- 第二個子陣列中非空值的數量（如果有）
- 第三個子陣列中非空值的個數（如果有）
- 第四個子陣列中非空值的個數（如果有的話）
可以從該資訊中推斷出潛在的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 的冪涉及到一些值。頂層有（包括最終的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];
}
}
}
}
}
}
我承認這段代碼并不優雅，有很多代碼重復，但它達到了預期的目的：它為任何給定的陣列大小生成一個形狀（上面解釋的一組數字）。
在更小的空間中編碼形狀
The numbers for the sub arrays cannot be just any number. They must be either a power of 2, or one less (when one padding null is assumed) or two less (when two null values are assumed). So the possible numbers are in this set:
[1, 2, 3, 4, 6, 7, 8, 14, 15, 16, 30, 31, 32]
The first number (which represents the count of values at the top level), can also be in that set, but can also be in the range 27 - 29. This is because the sub arrays that follow and potential null padding also count for reaching the power of 2 at the top level. This means that there are exactly 16 possible numbers in the first position of the shape "encoding". We could compress this encoding by mapping these numbers to 4-bit values (giving 16 possibilities). As it turned out there are never more than 4 subarrays needed, we will need 20 bits for encoding a shape.
Now we should determine what these 20-bit numbers are for 128 shapes and collect them in an array that can serve as lookup table.
Here is the function to encode numbers into that 20-bit encoding:
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;
}
I collected the codes with this function:
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;
}
Show code snippet
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()));This gave this result:
[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]
The solution code
Now that we have this, we can throw away the above JavaScript functions. This array has the info we need to reproduce a shape or to translate an index into a path.
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)));
}轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/424337.html