# How to remove duplication in this array/tree generating function?

Here we have the following code.

let i = 1
while (i <= 256) {
log(i)
i++
}

function shape(n) {
let p = greatestPowerOf2(n);
if (p >= n) {
// The only cases where there are no subarrays
return [n];
}

// Try with one subarray
for (let sub = 2; sub < n && sub <= 256; sub *= 2) {
let top = n - sub + 1;
p = greatestPowerOf2(top);
if (p >= top) {
return [p - 1, sub];
}
}

// Try with two subarrays
for (let sub1 = 2; sub1 < n && sub1 <= 256; sub1 *= 2) {
for (let sub2 = 2; sub2 <= sub1; sub2 *= 2) {
let top = n - sub1 - sub2 + 2;
if (top < 0) break;
p = greatestPowerOf2(top);
if (p >= top) {
return [p - 2, sub1, sub2];
}
}
}

// Try with three subarrays
for (let sub1 = 2; sub1 < n && sub1 <= 256; sub1 *= 2) {
for (let sub2 = 2; sub2 <= sub1; sub2 *= 2) {
for (let sub3 = 2; sub3 <= sub2; sub3 *= 2) {
let top = n - sub1 - sub2 - sub3 + 3;
if (top < 0) break;
p = greatestPowerOf2(top);
if (p >= top) {
return [p - 3, sub1, sub2, sub3];
}
}
}
}

// Try with four subarrays
for (let sub1 = 2; sub1 < n && sub1 <= 256; sub1 *= 2) {
for (let sub2 = 2; sub2 <= sub1; sub2 *= 2) {
for (let sub3 = 2; sub3 <= sub2; sub3 *= 2) {
for (let sub4 = 2; sub4 <= sub3; sub4 *= 2) {
let top = n - sub1 - sub2 - sub3 - sub4 + 4;
if (top < 0) break;
p = greatestPowerOf2(top);
if (p >= top) {
return [p - 4, sub1, sub2, sub3, sub4];
}
}
}
}
}

// Try with five subarrays
for (let sub1 = 2; sub1 < n && sub1 <= 256; sub1 *= 2) {
for (let sub2 = 2; sub2 <= sub1; sub2 *= 2) {
for (let sub3 = 2; sub3 <= sub2; sub3 *= 2) {
for (let sub4 = 2; sub4 <= sub3; sub4 *= 2) {
for (let sub5 = 2; sub5 <= sub4; sub5 *= 2) {
let top = n - sub1 - sub2 - sub3 - sub4 - sub5 + 5;
if (top < 0) break;
p = greatestPowerOf2(top);
if (p >= top) {
return [p - 5, sub1, sub2, sub3, sub4, sub5];
}
}
}
}
}
}

// Try with 6 subarrays
for (let sub1 = 2; sub1 < n && sub1 <= 256; sub1 *= 2) {
for (let sub2 = 2; sub2 <= sub1; sub2 *= 2) {
for (let sub3 = 2; sub3 <= sub2; sub3 *= 2) {
for (let sub4 = 2; sub4 <= sub3; sub4 *= 2) {
for (let sub5 = 2; sub5 <= sub4; sub5 *= 2) {
for (let sub6 = 2; sub6 <= sub5; sub6 *= 2) {
let top = n - sub1 - sub2 - sub3 - sub4 - sub5 - sub6 + 6;
if (top < 0) break;
p = greatestPowerOf2(top);
if (p >= top) {
return [p - 6, sub1, sub2, sub3, sub4, sub5, sub6];
}
}
}
}
}
}
}

// Try with 7 subarrays
for (let sub1 = 2; sub1 < n && sub1 <= 256; sub1 *= 2) {
for (let sub2 = 2; sub2 <= sub1; sub2 *= 2) {
for (let sub3 = 2; sub3 <= sub2; sub3 *= 2) {
for (let sub4 = 2; sub4 <= sub3; sub4 *= 2) {
for (let sub5 = 2; sub5 <= sub4; sub5 *= 2) {
for (let sub6 = 2; sub6 <= sub5; sub6 *= 2) {
for (let sub7 = 2; sub7 <= sub6; sub7 *= 2) {
let top = n - sub1 - sub2 - sub3 - sub4 - sub5 - sub6 - sub7 + 7;
if (top < 0) break;
p = greatestPowerOf2(top);
if (p >= top) {
return [p - 7, sub1, sub2, sub3, sub4, sub5, sub6, sub7];
}
}
}
}
}
}
}
}

throw new Error(n)
}

function greatestPowerOf2(n) {
return n >= 256 ? 256 : n >= 128 ? 128 : n >= 64 ? 64 : n >= 32 ? 32 : n >= 16 ? 16 : n >= 8 ? 8 : n >= 4 ? 4 : n >= 2 ? 2 : 1;
}

function log(n) {
console.log(${n} =>${JSON.stringify(shape(n))})
}

It consists of a shape function which takes a number from 1 to 256, and outputs an array following this pattern (here is a snippet):

base-1
a

base-2
a
b

base-3
a
tree
b
c

base-4
a
b
c
d

base-5
a
b
c
tree
d
e

base-6
a
b
tree
c
d
tree
e
f

base-7
a
b
tree
c
d
e
f
tree
g


Basically, it says the "shape" of the tree that should be produced. For example, on log(12) it outputs [6,4,2]. That means there should be 6 top-level elements, followed by nested 2 elements (starting from the top), followed by nested 2 elements (starting from the top again). This shape function will always return an array where every level of the array has a power of 2 number of elements (6 + 2 children is 8 a power of 2, 2 is power of 2, and 2 is a power of 2).

The question is, how can you remove the duplication of the shape function, where it has loops for 2, 3, or 4 nested arrays? How can you remove those "cases" and make it into a generic loop of some sort that tries 2, then tries 3, then tries 4, without a switch statement or any sort of duplication?

• en.wikipedia.org/wiki/Recursion Feb 15, 2022 at 9:34
• @Lance Can you explain why 12 => [6,4,2] but not [4,2,2,2,2] I didn't quite catch the idea. But I have a feeling that maybe there is no need for so many cycles, everything can be solved by calculation. Feb 16, 2022 at 18:52
• @DaniilLoban because I think it tries to fill the top-level with as many nodes as it can, to keep the traversal to a minimum. Then it fills the nested nodes with whatever else. It would look like this for example: [a, b, c, d, e, f, [g, h, i, j], [k, l]]. See this question for all the possible shapes (at the bottom). Feb 16, 2022 at 20:12
• @Lance there is an option how to improve this code by almost getting rid of embedded loops, but its performance drops by 2.5 times on average, so I do not know if it is worth publishing, it only has flexibility. Feb 17, 2022 at 15:24