5

Trying to create a function mCreate() that given a set a numbers returns a multidimensional array (matrix):

mCreate(2, 2, 2)    
//   [[[0, 0], [0, 0]], [[0, 0], [0, 0]]]

When this functions handles just 2 levels of depth ie: mCreate(2, 2) //[[0, 0], [0, 0]] I know to do 2 levels, you can use 2 nested for loops but the problem I'm having is how to handle an n'th number of arguments.

Would this problem be better approached with recursion, otherwise how can I dynamically determine the number of nested for loops I'm going to need given the number of arguments?

ps: the most performant way would be great but not essential

RE-EDIT - After using Benchmark.js to check perf the results were as follows:

BenLesh x 82,043 ops/sec ±2.56% (83 runs sampled)
Phil-P x 205,852 ops/sec ±2.01% (81 runs sampled)
Brian x 252,508 ops/sec ±1.17% (89 runs sampled)
Rick-H x 287,988 ops/sec ±1.25% (82 runs sampled)
Rodney-R x 97,930 ops/sec ±1.67% (81 runs sampled)
Fastest is Rick-H

@briancavalier also came up with a good solution JSbin:

const mCreate = (...sizes) => (initialValue) => _mCreate(sizes, initialValue, sizes.length-1, 0)

const _mCreate = (sizes, initialValue, len, index) =>
    Array.from({ length: sizes[index] }, () => 
        index === len ? initialValue : _mCreate(sizes, initialValue, len, index+1))
mCreate(2, 2, 2)(0)
10
  • 1
    Can you explain what exactly are you trying to achieve. Commented May 1, 2016 at 16:46
  • function mCreate(...arg){} Commented May 1, 2016 at 16:47
  • @PranavCBalan this would only return [2, 2, 2] not what I'm after :( Commented May 1, 2016 at 16:51
  • 1
    @cmdv : you can get n arguments , then using some method implement what you want Commented May 1, 2016 at 16:53
  • 1
    @RickHitchcock it would contain 1 element Commented May 1, 2016 at 17:06

5 Answers 5

7

One simple recursive answer is this (in ES2015):

const mCreate = (...sizes) => 
    Array.from({ length: sizes[0] }, () => 
        sizes.length === 1 ? 0 : mCreate(...sizes.slice(1)));

JS Bin here

EDIT: I think I'd add the initializer in with a higher order function though:

const mCreate = (...sizes) => (initialValue) => 
    Array.from({ length: sizes[0] }, () => 
        sizes.length === 1 ? initialValue : mCreate(...sizes.slice(1))(initialValue));

Which could be used like:

mCreate(2, 2, 2)('hi'); 
// [[["hi", "hi"], ["hi", "hi"]], [["hi", "hi"], ["hi", "hi"]]]

JSBin of that

Sign up to request clarification or add additional context in comments.

Comments

4

Here's a non-recursive solution:

function mCreate() {
  var result = 0, i;

  for(i = arguments.length - 1; i >= 0 ; i--) {
    result = new Array(arguments[i]).fill(result);
  }

  return JSON.parse(JSON.stringify(result));
}

The JSON functions are used to mimic a deep clone, but that causes the function to be non-performant.

function mCreate() {
  var result = 0, i;
  
  for(i = arguments.length - 1; i >= 0 ; i--) {
    result = new Array(arguments[i]).fill(result);
  }

  return JSON.parse(JSON.stringify(result));
}


console.log(JSON.stringify(mCreate(2, 2, 2)));
console.log(JSON.stringify(mCreate(1, 2, 3, 4)));
console.log(JSON.stringify(mCreate(5)));
console.log(JSON.stringify(mCreate(1, 5)));
console.log(JSON.stringify(mCreate(5, 1)));

var m = mCreate(1, 2, 3, 4);
m[0][1][1][3] = 4;
console.log(JSON.stringify(m));

7 Comments

this looks great, do you think it would be more performant than a recursive option?
Yes, because a recursive solution would add the execution context to the stack for each dimension.
woah that looks really clean it's also improved the perf!! was not expecting that, though the test I'm running are really bad and on jsfiddle!!
This solution has a slight problem once you start modifying values of the generated array. for var x = mCreate(2, 1); the following is true: x[0] === x[1]. So if you did x[0][0] = 1; you would also have x[1][0] === 1. Using .slice() when "cloning" the array would solve that.
@rodneyrehm, great point! Unfortunately, .slice() does a narrow copy, and we'd need a deep copy instead. My solution needs more work.
|
3

Recursive algorithms may be easier to reason about, but generally they're not required. In this particular case the iterative approach is simple enough.

Your problem consists of two parts:

  1. creating an array with variable number of 0-value elements
  2. creating variable number of arrays of previously created arrays

Here's an implementation of what I think you're trying to create:

function nested() {
  // handle the deepest level first, because we need to generate the zeros
  var result = [];
  for (var zeros = arguments[arguments.length - 1]; zeros > 0; zeros--) {
    result.push(0);
  }

  // for every argument, walking backwards, we clone the
  // previous result as often as requested by that argument
  for (var i = arguments.length - 2; i >= 0; i--) {
    var _clone = [];
    for (var clones = arguments[i]; clones > 0; clones--) {
      // result.slice() returns a shallow copy
      _clone.push(result.slice(0));
    }

    result = _clone;
  }

  if (arguments.length > 2) {
    // the shallowly copying the array works fine for 2 dimensions,
    // but for higher dimensions, we need to compensate
    return JSON.parse(JSON.stringify(result));
  }

  return result;
}

Since writing the algorithm is only half of the solution, here's the test to verify our function actually performs the way we want it to. We'd typically use one of the gazillion test runners (e.g. mocha or AVA). But since I don't know your setup (if any), we'll just do this manually:

var tests = [
  {
    // the arguments we want to pass to the function.
    // translates to nested(2, 2)
    input: [2, 2],
    // the result we expect the function to return for
    // the given input
    output: [
      [0, 0],
      [0, 0]
    ]
  },
  {
    input: [2, 3],
    output: [
      [0, 0, 0],
      [0, 0, 0]
    ]
  },
  {
    input: [3, 2],
    output: [
      [0, 0],
      [0, 0],
      [0, 0]
    ]
  },
  {
    input: [3, 2, 1],
    output: [
      [
        [0], [0]
      ],
      [
        [0], [0]
      ],
      [
        [0], [0]
      ]
    ]
  },
];

tests.forEach(function(test) {
  // execute the function with the input array as arguments
  var result = nested.apply(null, test.input);
  // verify the result is correct
  var matches = JSON.stringify(result) === JSON.stringify(test.output);
  if (!matches) {
    console.error('failed input', test.input);
    console.log('got', result, 'but expected', rest.output);
  } else {
    console.info('passed', test.input);
  }
});

It's up to you to define and handle edge-cases, like nested(3, 0), nested(0, 4), nested(3, -1) or nested(-1, 2).

7 Comments

thank you for the great explanation, I'm just going to quickly set up proper perf tests but using a quick jsfiddle from Phil-plückthun, looks like @rick-hitchcock it comming out top :-) jsfiddle.net/2v4zj76t
Rick's solution is not cloning the arrays, thereby producing a result that cannot be mutated without side-effects. If that's a problem and you fix that, both functions would be doing the same thing and performance should be equal.
I would much rather it cloned the arrays as I'm trying to use this function towards this FP library I've been trying to write github.com/Cmdv/linearJs
@cmdv if Math.js already has the function you need, why not simply load that as a dependency and be done with it? I mean, the library is APL, documented and tested. It has >3k stars. From where I stand you're wasting your time re-implementing this already solved problem… You even could only only load the zeros module: github.com/josdejong/mathjs/blob/master/lib/function/matrix/… - why do this again?
Your solution also needs a deep copy. See jsfiddle.net/8k5w0gvh. There should be only one "2"
|
0

As suggested by @Pranav, you should use arguments object.

Recursion + arguments object

function mCreate() {
  var args = arguments;
  var result = [];
  if (args.length > 1) {
    for (var i = 1; i < args.length; i++) {
      var new_args = Array.prototype.slice.call(args, 1);
      result.push(mCreate.apply(this, new_args));
    }
  } else {
    for (var i = 0; i < args[0]; i++) {
      result.push(0)
    }
  }
  return result;
}

function print(obj) {
  document.write("<pre>" + JSON.stringify(obj, 0, 4) + "</pre>");
}
print(mCreate(2, 2, 2, 2))

1 Comment

thanks the only thing that draws me away is the use of apply as thats a pretty slow process but I like the recursion :)
0

The gist is to pass in the result of a create as the second argument of create except for the last (or the first depending on how you look at it) instance:

function create(n, v) {
  let arr = Array(n || 0);
  if (v !== undefined) arr.fill(v);
  return arr;
}

create(2, create(2, 0)); // [[0,0],[0,0]]
create(2, create(2, create(2, 0))); // [[[0,0],[0,0]],[[0,0],[0,0]]]

DEMO

Using a loop we can build up array dimensions:

function loop(d, l) {
  var out = create(d, 0);
  for (var i = 0; i < l - 1; i++) {
    out = create(d, out);
  }
  return out;
}

loop(2,2) // [[0,0],[0,0]]
loop(2,3) // [[[0,0],[0,0]],[[0,0],[0,0]]]
loop(1,3) // [[[0]]]

DEMO

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.