I want to recursively produce the vertices (points) of a unit n-hypercube (for the sake of clarity, just a cube here). The idea is to specify the points of the cube by recursively going through the x, y, and z components. Why not just use nested for-loops? Recursion is intrinsically swag. This is my function:
var points = [];
function makeCube(d, point) {
console.log(d,point);
if(d == 0) {
points.push(point);
} else {
extension1 = [...point];
extension1.push(0);
extension2 = [...point];
extension2.push(1);
makeCube(d - 1, extension1);
makeCube(d - 1, extension2);
}
}
I call makeCube(3, [])
. The console reads this:
[Log] 3 – [] (0) (sketch.js, line 57)
[Log] 2 – [0] (1) (sketch.js, line 57)
[Log] 1 – [0, 0] (2) (sketch.js, line 57)
[Log] 0 – [0, 0, 0] (3) (sketch.js, line 57)
[Log] 0 – [0, 0, 1] (3) (sketch.js, line 57)
[Log] 1 – [0, 0, 1] (3) (sketch.js, line 57)
[Log] 0 – [0, 0, 1, …] (4) (sketch.js, line 57)
etc...
When d is 1, there should only be 2 entries in the array, not 3! When d is 0, there should be 3, not 4. The second array in the lowest level is being carried up a level somehow. I made a point of copying the extension arrays rather than setting them equal to the old one, so I don't understand what's going on.
Expected console output:
[]
[0]
[0,0]
[0,0,0]
[0,0,1]
[0,1]
[0,1,0]
[0,1,1]
[1]
[1,0]
[1,0,0]
[1,0,1]
[1,1]
[1,1,0]
[1,1,1]
CodePudding user response:
I think I solved the problem:
var points = [];
function makeCube(d, point) {
console.log(d, JSON.stringify(point));
if(d == 0) {
points.push([...point]);
} else {
let extension1 = [...point];
extension1.push(0);
let extension2 = [...point];
extension2.push(1);
makeCube(d - 1, extension1);
makeCube(d - 1, extension2);
}
}
makeCube(3, [])
3 []
2 [0]
1 [0,0]
0 [0,0,0]
0 [0,0,1]
1 [0,1]
0 [0,1,0]
0 [0,1,1]
2 [1]
1 [1,0]
0 [1,0,0]
0 [1,0,1]
1 [1,1]
0 [1,1,0]
0 [1,1,1]
I just added let
twice (and changed what I logged).
The original script creates global extension1
and extension2
variables in the window. Apparently, the global scope caused some problems.
CodePudding user response:
You can use a generator to move the side effect, console.log
, outside of the function. This also makes it easy to skip the global points
variable. Use a for..of
loop to iterate through all the points -
function* makeCube(d, point = []) {
yield point
if(d == 0) return
yield *makeCube(d - 1, [...point, 0])
yield *makeCube(d - 1, [...point, 1])
}
for (const point of makeCube(3))
console.log(`(${point.join(",")})`) // caller decides effect
()
(0)
(0,0)
(0,0,0)
(0,0,1)
(0,1)
(0,1,0)
(0,1,1)
(1)
(1,0)
(1,0,0)
(1,0,1)
(1,1)
(1,1,0)
(1,1,1)
Or use Array.from
to collect all of the points into an array
const points = Array.from(makeCube(3))
console.log(points)
[
[],
[0],
[0,0],
[0,0,0],
[0,0,1],
[0,1],
[0,1,0],
[0,1,1],
[1],
[1,0],
[1,0,0],
[1,0,1],
[1,1],
[1,1,0],
[1,1,1],
]
If you want to compute the product
, I would suggest you write the function somewhat differently -
function* product(t, ...more) {
if (t == null) return yield []
for (const p of product(...more))
for (const v of t)
yield [v, ...p]
}
for (const p of product([0,1], [0,1], [0,1]))
console.log(p.join(","))
for (const p of product(["J", "Q", "K", "A"], ['♡', '♢', '♤', '♧']))
console.log(p.join(""))
0,0,0
1,0,0
0,1,0
1,1,0
0,0,1
1,0,1
0,1,1
1,1,1
J♡
Q♡
K♡
A♡
J♢
Q♢
K♢
A♢
J♤
Q♤
K♤
A♤
J♧
Q♧
K♧
A♧