Permutations function crashes

Hans Höglund

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;
}

Hans Höglund

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)
    )
}

Brian Gruber

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

Hans Höglund

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.

Tom Swirly

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.

Hans Höglund

Really? I have to check that.