Building off this question, the next question is, how to build an algorithm which will take as input an index/integer, and output the path to the appropriate node in the tree. The examples of how the trees might be structured are as follows, but I might be wrong. Ideally there would be a pattern which all of them follow so we can have an equation to map index to path.
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?
CodePudding user response：
This is going to be a long road...
As I also could not find a mathematical formula to solve this, I went for a data-driven solution: a lookup table that gives me the shape of the (potentially) nested array for each individual size (between 1 and 128).
A shape can be defined by a few numbers:
- The number of top-level, non-null values
- The number of non-null values in the first sub array if there is one
- The number of non-null values in the second sub array if there is one
- The number of non-null values in the third sub array if there is one
- The number of non-null values in the fourth sub array if there is one
The potential null padding can be inferred from this information, as we know that a power of 2 must be reached.
An example:
Size = 102
This can be represented with the following numbers:
28, 30, 30, and 14
This means an array of that size will look like this:
[
0,
1,
2,
3,
...,
27,
[28, 29,..., 57, null, null],
[58, 59,..., 87, null, null],
[88, 89,..., 101, null, null],
null
]
Note that there are null values involved to reach powers of 2. The top level has (including the final null) 32 elements. The first two inner sub arrays have a total size of 32 (including the padding null values), and the third one has 16 elements (also including the padding).
Generating the shapes
To avoid having to determine shapes manually for each of the 128 array sizes, I wrote a brute force function to make a valid shape choice for each of these sizes. This I just used to fix these shapes, and is not part of the final solution:
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];
}
}
}
}
}
}
I admit this code is not elegant, with lots of code repetition, but it serves the intended purpose: it generates a shape (the set of numbers explained above) for any given array size.
Encoding the shapes in less space
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;
}
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 = 1; sub < 6; 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)));
}