Node.js - Different permutation implementations: iterative buffer-based, iterative array-based and recursion-based

index.mjs

// A reasonably-efficient approach that uses "DMA" ("Direct Memory Access"), avoids multiple allocations (well, except for stack array) and (ab)uses mathematics 
// In my tests, permutateBuffer is the fastest among the three.
const permutateBuffer = function(amount){
    // It *should* work for browsers if Buffer is replaced with Uint8Array
    
    if(isNaN(amount) || amount < 1 || amount > 10) // If you have sufficient memory and V8 is configured with enough heap, 10 can be increased
        return Buffer.alloc(0)

    let expected = 1
    let carrier = 1
    let sum = 0

    amount = Math.ceil(amount)
    
    for(let i = 0; i < amount; i++){
        expected *= (i+1) // final expected = fact(amount) = (1, 1, 2, 6, 24, ...)
        carrier *= (amount - i) // final carrier = fact(amount) = (1, 1, 2, 6, 24, ...) // (N), N(N-1), N(N-1)(N-2), ...
        sum+=carrier*(i+1) // final sum = A093964(amount) = (0, 1, 6, 33, 196, ...)
    }
    
    let subperms = Buffer.alloc(sum) // A093964(amount) bytes (so e.g. amount = 9 would take ~7MiB ) 
    let perms = Buffer.alloc(expected*amount) //factorial(amount)*amount (e.g. amount = 9 would take 9 × 9! = ~3MiB)
    let permOffset = 0
    let stack = []
    let currentState = {
        k: 0, d: 0, o: null
    }
    while(1){ // A111063(amount+1) total hits (1, 3, 9, 31)
        let pushed = false

        if(currentState.d == amount){ // factorial(amount) total hits (1, 1, 2, 6, 24, ...)
            for(let r = 0; r < amount; r++)
                perms[permOffset+r] = subperms[currentState.o + r]
            
            permOffset+=amount
            // factorial(amount)*amount (0, 1, 4, 18, 96, ) total bytes read/written
            // for amount=9, 362880 total hits / 3265920 total Bytes, it consumes around 90ms overall  
        } else while(currentState.k < amount){ // A345887(amount-1) total hits (0, 1, 6, 30, 164, 1030, 7422, ...)
            let {k,d,o} = currentState
            currentState.k++
            let allowsSub = (d == 0)
            if(!allowsSub){ // A345887(amount-1)-amount total hits (0, 0, 4, 27, 160, 1025, ...)
                allowsSub = true
                for(let r = 0; r < d; r++)
                    if(subperms[r+o] == k){
                        allowsSub = false
                        break
                    }
            }

            if(allowsSub){ // A007526(amount) total hits (0, 1, 4, 15, 64, ...)
                pushed = true
                stack.push(currentState)
                sum-=d+1
                if(d>0)
                    for(let r = 0; r < d; r++)
                        subperms[sum+r] = subperms[o+r]
                subperms[sum+d] = k

                currentState = {
                    d: d+1,
                    k: 0,
                    o: sum
                }
                break
            }
        }

        if(!pushed)
            if(!(currentState = stack.pop())) // just 1, of course
                break
    }
    let arrPerms = []
    for(let k = 0; k < permOffset; k+=amount){
        let subPerm = Array.from(Array(amount))
        for(let r = 0; r < amount; r++)
            subPerm[r] = perms[k+r]
        
        arrPerms.push(subPerm)
    }
    
    return arrPerms
}

// Something in-between, using its own stack but (ab)using arrays and spread operator (it's slow). It's here just for comparison.
const permutateIterateArr = function(amount){
    let perms = []

    if(isNaN(amount) || amount <= 0 || amount > 12) // factorial(12) is too big. 
        return perms

    let stack = []
    let currentState = {
        k: 0, d: 0, p: []
    }

    while(1){ // A111063(amount+1) total hits (0, 3, 9, 31, 129, 651, ...)
        let pushed = false

        if(currentState.d >= amount) // factorial(amount) total hits (1, 1, 2, 6, 24, ...)
            perms.push(currentState.p)
        else while(currentState.k < amount){ // A345887(amount-1) total hits (0, 1, 6, 30, 164, 1030, 7422, ...)
            let {k,p,d} = currentState
            currentState.k++

            if(!p.includes(k)){ // A007526(amount) total hits (0, 1, 4, 15, 64, ....)
                pushed = true
                stack.push(currentState)
                currentState = {
                    d: d+1,
                    p: [...p, k],
                    k: 0
                }
                break
            }
        }

        if(!pushed) // A007526(N)+1 total hits (1, 2, 5, 16, 65, ....)
            if(!(currentState = stack.pop())) // exactly 1 (obviously)
                break
            // else: A007526(amount) total hits (0, 1, 4, 15, 64, ...)
        // else: A007526(amount) total hits (0, 1, 4, 15, 64, ...)
    }
    return perms
}
// The classical approach: recursion (but beware the call stack limitation).
const permutateRecursive = function(amount, stack = []){
    if(isNaN(amount) || amount < 0 || amount >= 10) // 10! is expected to yield maximum call stack, so 0<amount<10 seems reasonable.
        return []

    if(stack.length >= amount) // factorial(amount) total hits
        return stack

    let subPerm = []

    for(let k = 0; k < amount; k++){
        if(!stack.includes(k)){ // A007526(amount) total hits
            let m = permutateRecursive(amount, [...stack, k])
            if(Array.isArray(m[0])) // A038156(amount) total hits
                subPerm.push(...m)
            else 
                subPerm.push(m)
        }
    }

    return subPerm
}