Permutation formula n!/(n-r)!

New to Julia
1

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.

2

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.

3

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

1 Like
4

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:

  1. C^n_k = C^n_{n-k}. Using this, you can always transform your calculations so that r \ge n / 2.
  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
1 Like
5

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.

1 Like
6

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

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.

1 Like
8

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.
9

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.

1 Like
10

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