CODEWITHSUNDEEP
javascriptrecursion
Mathematical Lie
Mathematical Lie

Reputation: 143

How to recursively copy arrays

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]

Upvotes: 0

Views: 130

Answers (2)

Mulan
Mulan

Reputation: 135377

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♧

Upvotes: 1

qrsngky
qrsngky

Reputation: 2916

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.

Upvotes: 1

Related Questions