Permutations function crashes

May 4, 2010 at 3:11pm

Permutations function crashes

I wrote the following js function that generates all permutations of a given array. It seem to work fine for for short arrays; however, where length > 5 elements it crashes Max.

This seem to be a stack space issue? Could it be workarounded in any way?

I also tested the code in Firefox, and there it works fine for any number of elements (it is of course really slow for arrays where length > 9).

/**
 * Returns an array containing all permutations of this array.
 */
Array.prototype.permute = function ()
{
    // FIXME crashes for >5 elements
    var result = []
    permute(this, this.length, result);
    return result;
}

// Private
function permute(values, n, result)
{
    if (n == 1)
        result.push(values);
    else {
        for (var i = 0; i < n; i++) {
            values = permute(values, n - 1, result);
            if (n % 2 === 1)
                values = values.swap(0, n - 1);
            else
                values = values.swap(i, n - 1);
        }
    }
    return values;
}
#50177
May 4, 2010 at 3:15pm

Sorry, this swap function is also required to run the above code.

/**
 * Returns a copy of this array with the given elements swapped.
 */
Array.prototype.swap = function(a, b)
{
    if (a === b)
        return this.slice(0);
    if (a > b)
        return swap(this, b, a);

    return this.slice(0, a).concat(

        // Wrap single elements in a new array to ensure that eventual nested
        // arrays are not flattened
        [ this[b] ],
        this.slice(a + 1, b),

        [ this[a] ],
        this.slice(b + 1)
    )
}
#180122
May 5, 2010 at 5:49am

i didn’t try it in max, but if your problem really is stack space, here’s a non-recursive version:

Array.prototype.permutei = function() {
    var result = [this];

    for(var i = 0; i != this.length; i++) {
	var nr = [];
	for(var j = 0; j != result.length; j++) {
	    for(var k = i + 1; k != this.length; k++) {
		nr.push(result[j].swap(i,k));
	    }
	}
	result.push.apply(result, nr);
    }

    return result;
}

and, because it makes me happy, a very functional approach which will not solve your problem:

Array.prototype.removei = function(i) {
    return this.slice(0,i).concat(this.slice(i + 1));
}

Array.prototype.permute = function() {
    if(this.length < = 1) {
	return [this];
    }

    var result = [];

    this.forEach(
	function(val, i, a) {
	    a.removei(i).permute().map(function(r) { return [val].concat(r) }).forEach(function(v,i,a){result.push(v)});
	});

    return result;
}
#180123
May 5, 2010 at 4:49pm

Thanks for these versions Brian! Unfortunately, behaviour is the same as for my implementation.

I found out that the problem was not actually related to the permute function, but to printing of the result.

I use a custom defined print function that passes objcts to JSON.stringify for serialization rather than printing ‘jsobject…’. Seemingly, this function can not handle large arrays (neither can stringify). I guess that stringify builds up a buffer of serialized objects and that this creates a memory problem.

It would be nice to know the exact cause. I work with a lot of big data structures and the moment and the recurring crashes are very annoying, so I would like to know how to circumvent them.

#180124
May 19, 2010 at 1:45am

Perhaps this is the issue – you can’t print out a string that’s longer than 1023 characters without crashing Max?

This is pretty easy to work around – split the string and print it in parts.

#180125
May 20, 2010 at 9:57pm

Really? I have to check that.

#180126

You must be logged in to reply to this topic.