Permutation formula n!/(n-r)!

hack3rcon · November 25, 2024, 7:22am

Hello,
To calculate the formula n!/(n-r)!, I wrote the following program:

function combinations(n, r)
    n = BigInt(factorial(n))
    r = BigInt(factorial(r))
    t = BigInt(factorial(n-r))
    final = BigInt(n / (t * r))
    return final
end

function start()
    print("Please enter N: ")
    n = parse(Int, readline())
    print("Please enter R: ")
    r = parse(Int, readline())
    println(combinations(n, r))
end

start()

I got InexactError error. How to fix it?

Thank you.

Tarny_GG_Channie · November 25, 2024, 7:47am

You need to apply the factorial function to the numbers already converted to BigInt, not convert the numbers to BigInt after the call.

Also… you accidentally reassigned r, so the r.

Also, check out the doc for binomial if you just want the result.

DNF · November 25, 2024, 8:27am

Here’s a hint for better performance, and less risk of overflow:
6!/3! = 1\cdot 2\cdot 3\cdot 4\cdot 5\cdot 6/(1\cdot 2\cdot 3) = 4\cdot 5\cdot 6

Vasily_Pisarev · November 25, 2024, 8:36am

Maybe at this point it’s time to think why you are writing this function.

If that’s just to practice reusing your previous results, this implementation is fine.

If that’s to get an idea how things are done in practice, you need to think of how you can simplify the problem. In this implementation, you do enormous calculations to get C_n^n, which is totally redundant, as we know it’s 1.

The things to notice are:

C^n_k = C^n_{n-k}. Using this, you can always transform your calculations so that r \ge n / 2.
n! / r! = (r+1)(r+2)\dots n, so that it makes sense to make a specialized function for that operation.

In the end, it might be:

function combinations(n::Integer, r::Integer)
    p = max(r, n - r)

# (p+1)(p+2)...n - implementation is left as an exercise
    numer = factorial_ratio(n, p) 
    denom = factorial(n - p)
    return div(numer, denom)
end

Benny · November 25, 2024, 9:16am

In general, stop sharing programs with readline inputs because a function call with inputs written into source code is much clearer to us and we can’t guess what you’re typing. You should also generally share an error’s stacktrace so we have some idea where it’s happening.

In this specific case however, it’s more apparent where things are going wrong. We know that the combination formula should always have an integer value, ignoring overflow issues. InexactErrors happen when you try to convert non-integer values to integer types. Let’s see what you’re computing:

function combinations(n, r)
    n = BigInt(factorial(n))  # n!
    r = BigInt(factorial(r))  # r!
    t = BigInt(factorial(n-r))# (n!-r!)!
    final = BigInt(n / (t * r)) # n!/ ((n!-r!)! * r!)
    return final
end

Reusing variable names ruined the formula, you are neither calculating the permutation formula n!/(n-r)! in your title nor the combination formula n!/(r!(n-r)!) in your actual code. Trailing ! are legal in variable names:

julia> function combinations2(n, r)
           n! = BigInt(factorial(n))  # n!
           r! = BigInt(factorial(r))  # r!
           n_r! = BigInt(factorial(n-r))# (n-r)!
           final = BigInt(n! / (n_r! * r!)) # n!/ ((n-r)! * r!)
           final
       end
combinations2 (generic function with 1 method)

julia> combinations2(4, 3)
4

But I don’t like that much because n_r! was very easy to mistype as n-r! and that mistake is only caught at runtime.

The less immediate issue is that your type conversions are misguided (combinations2 does not fix this). If you want to deal with big integers, n and r need to be BigInt to begin with. There’s no point in erroring on factorial(21) before attempting to convert to BigInt. Dividing 2 BigInts is also problematic because it makes a BigFloat, which is designed to have a limited but adjustable precision. If you don’t fix any possible precision losses from that, converting to BigInt afterward won’t help. Since n!/r! or n!/(n-r)! is a product of a sequence of integers, try to pick the prod call to minimize intermediate values.

hack3rcon · November 25, 2024, 9:29am

Hello,
I changed my code as below:

function combinations(n, r)
    n = BigInt(factorial(n))
    r = BigInt(factorial(r))
    v = BigInt(n - r)
    t = BigInt(factorial(v))
    final = BigInt(n / (t * r))
    return final
end

I got the following error:

Please enter N: 4
Please enter R: 3
ERROR: LoadError: InexactError: BigInt(6.247682787434490584886545740022933369407761633787846742164271645199818938450171e-16)

Benny · November 25, 2024, 9:31am

Thanks for providing the readline inputs for clarity, but you should share the other lines in the error’s stacktrace for clarity as well. That aside, you’re running into the same error because you didn’t fix the reusage of variable names that ruined the formula.

hack3rcon · November 25, 2024, 9:37am

Thanks.
The new code is:

function combinations(n, r)
    x = BigInt(factorial(n))
    z = BigInt(factorial(r))
    t = BigInt(factorial(x - z))
    final = BigInt(x / (t * z))
    return final
end

And error is:

Please enter N: 4
Please enter R: 3
ERROR: LoadError: InexactError: BigInt(6.247682787434490584886545740022933369407761633787846742164271645199818938450171e-16)
Stacktrace:
  [1] BigInt(x::BigFloat)
    @ Base.MPFR ./mpfr.jl:374
  [2] combinations(n::Int64, r::Int64)
    @ Main ~/Julia/File.jl:249
  [3] star()
    @ Main ~/Julia/File.jl:257
  [4] top-level scope
    @ ~/Julia/File.jl:259
  [5] include(fname::String)
    @ Base.MainInclude ./client.jl:489
  [6] run(debug_session::VSCodeDebugger.DebugAdapter.DebugSession, error_handler::VSCodeDebugger.var"#3#4"{String})
    @ VSCodeDebugger.DebugAdapter ~/.vscode-oss/extensions/julialang.language-julia-1.127.2-universal/scripts/packages/DebugAdapter/src/packagedef.jl:122
  [7] startdebugger()
    @ VSCodeDebugger ~/.vscode-oss/extensions/julialang.language-julia-1.127.2-universal/scripts/packages/VSCodeDebugger/src/VSCodeDebugger.jl:45
  [8] top-level scope
    @ ~/.vscode-oss/extensions/julialang.language-julia-1.127.2-universal/scripts/debugger/run_debugger.jl:12
  [9] include(mod::Module, _path::String)
    @ Base ./Base.jl:495
 [10] exec_options(opts::Base.JLOptions)
    @ Base ./client.jl:318
 [11] _start()
    @ Base ./client.jl:552
in expression starting at /Julia/File.jl:259
 *  Terminal will be reused by tasks, press any key to close it.

Benny · November 25, 2024, 9:41am

Still the same error over the exact same value. It’s really worth commenting through your lines to 100% know what you’re computing

function combinations(n, r)
    x = BigInt(factorial(n)) # n!
    z = BigInt(factorial(r)) # r!
    t = BigInt(factorial(x - z)) # (n! - r!)!
    final = BigInt(x / (t * z)) # n! / ( (n! - r!)! * r! )
    return final
end

t = BigInt(factorial(x - z)) does (n! - r!)!, that is nowhere in the permutations or combinations formula. See my first comment for an edit where this particular mistake is fixed.

hack3rcon · November 25, 2024, 9:44am

Thank you so much.
The correct version is as follows:

function combinations(n, r)
    x = BigInt(factorial(n))
    z = BigInt(factorial(r))
    t = BigInt(factorial(n - r))
    final = BigInt(x / (t * z))
    return final
end

DNF · November 25, 2024, 10:59am

You are still ignoring that you have to convert to BigInt before calculating the factorial: factorial(BigInt(n)) etc.

Also, you are ignoring the advice that:

And finally, you are ignoring the advice to not use floating point division.

stevengj · November 25, 2024, 1:45pm

As @DNF said, to avoid overflow you need to convert to BigInt before computing factorials. It’s easiest to do this once, before the subsequent calls:

function combinations(n, r)
    nbig, rbig = BigInt(n), BigInt(r) # convert to BigInt to avoid overflow
    x = factorial(nbig)
    z = factorial(rbig)
    t = factorial(nbig - rbig)
    final = div(x, t * z) # use integer division, not /
    return final
end

Note that this corresponds to the built-in binomial(n, r) function.

There are more efficient ways of computing it by canceling terms from the factorials in the numerator and denominator analytically, as @DNF mentioned, but you want to focus on correctness before worrying about performance.

Henrique_Becker · November 25, 2024, 3:59pm

Are you a ChatGPT bot? Why give the exact same code again and say “The new code is:” or “The correct version is as follows:”?

hack3rcon · November 26, 2024, 6:26am

Hi,
Thanks.
But n and r are ordinary integers. Why does a memory overflow occur?

hack3rcon · November 26, 2024, 6:29am

Hi,
No, I’m not.
First of all, why do you think something like ChatGPT hasn’t existed before? Second, I don’t know what benefit a bot-based Q&A would have for a newbie like me?

Benny · November 26, 2024, 6:57am

Fixed precision integer datatypes generally silently overflow (or underflow). It doesn’t mean you run out of memory (that’ll be an OutofMemoryError or some sort of crash) and it isn’t the kind of overflow where you write to the wrong memory addresses, it’s the value circling when the computation attempts to go outside its range. For an easy example, imagine a 2-bit signed integer. Its values are only -2, -1, 0 and 1. There cannot be a value of 2, so if you attempt 1+1, you circle back to -2.

Respectfully, I haven’t seen OP repeat code in this thread and I double checked just now. They were editing variable names as I suggested, albeit in a few attempts that didn’t fix the formula error.

While formulaic responses are characteristic of generative AI, they are ALSO characteristic of people who have less experience in English. Similarly, GPT detectors were observed to misidentify non-native speakers at a higher rate, paradoxically reducing the detection rate after the submitted essays’ vocabulary was edited by ChatGPT. I think we should be more cautious before making inflammatory accusations, be more open to other explanations.

abraemer · November 26, 2024, 6:58am

It is an integer overflow. The largest Int64 is typemax(Int64) (gives 9223372036854775807). When you exceed this value then it “wraps around” to the negatives:

julia> typemax(Int64)+10
-9223372036854775799

julia> typemax(Int64)*2
-2

Since factorial grows very fast this happens very easily. In fact for Int64 the first factorial to overflow is only 21:

julia> factorial(20)
2432902008176640000

julia> factorial(21)
ERROR: OverflowError: 21 is too large to look up in the table; consider using `factorial(big(21))` instead
# Stacktrace

This is why the folks in this thread (and also the helpful error message) advise you to use BigInt instead which indeed will fill up the memory instead of overflowing.

hack3rcon · November 26, 2024, 7:10am

Thank you so much.
Could a template like this fix the problem?

function Test(VARIABLE::Type, VARIABLE::Type)
    <BODY>
end

Test(VARIABLE::Type, VARIABLE::Type)

Benny · November 26, 2024, 7:15am

Sorry I can’t tell what problem that could possibly fix or how it’s relevant to anything in this thread. It just looks like an unfinished method for a call taking two types, and I am curious why you wrote this.

hack3rcon · November 26, 2024, 7:27am

For example, I call the function as follows:

Test(a::BigInt, b::BigInt)

Wouldn’t this automatically convert the values a and b to BigInt?