Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Calculate value of n choose k

What is the most efficient method to evaluate the value of n choose k ? The brute force way I think would be to find n factorial / k factorial / (n-k) factorial .

A better strategy may be to use dp according to this recursive formula. Is there any other better method to evaluate n choose k ?

like image 223
Nikunj Banka Avatar asked Mar 08 '13 19:03

Nikunj Banka


People also ask

What is n choose k calculator?

N Choose K Calculator is a free online tool that displays the number of ways to choose the elements irrespective of the order from the set.

How do you find K from n?

To convert Newtons to kilograms, divide by 9.81. For instance, 20 Newtons would be equivalent to 20/9.81 or 2.04 kilograms.

What does n choose k mean in stats?

(pronounced “n choose k” ) is the number of distinct subsets of size k of a set of size n. More informally, it's the number of different ways you can choose k things from a collection of n of them (hence n choose k).


1 Answers

Here is my version, which works purely in integers (the division by k always produces an integer quotient) and is fast at O(k):

function choose(n, k)     if k == 0 return 1     return (n * choose(n - 1, k - 1)) / k 

I wrote it recursively because it's so simple and pretty, but you could transform it to an iterative solution if you like.

like image 117
user448810 Avatar answered Sep 16 '22 15:09

user448810