20
\$\begingroup\$

Write a program that takes an input such as:

n,k

which then computes:

$$\binom n k = \frac {n!} {k!(n-k)!}$$

and then prints the result.

A numerical example:

Input:

5,2

Internal computation:

$$\frac {5!} {3!\times2!}$$

Printed Output:

10

I'd like to see an answer that beats my python solution of 65 characters, but all languages are obviously welcome.

Here's my solution:

n,k=input();f=lambda x:+(x<2)or x*f(x-1);print f(n)/(f(k)*f(n-k))

Edit:

I admit that this question is from the codegolf website mathematical combination puzzle. I know that my answer may look like not much progress can be made on it, but the leaders of this puzzle have solved it in nearly half as many characters.

Improve this question
\$\endgroup\$
9
  • \$\begingroup\$ Function or full program? Your description says function that returns the correct result, but your example is a full program that prints it. \$\endgroup\$
    – Ventero
    Commented Mar 22, 2011 at 16:38
  • \$\begingroup\$ @Ventero You're right I meant program. Sorry about that. \$\endgroup\$
    – backus
    Commented Mar 22, 2011 at 17:34
  • 3
    \$\begingroup\$ Generally, basic math concepts aren't great golf questions because J, APL, Maple, Mathematica and many others will have them built in. Also, be a bit more specific about input and output format, and provide example results - I can't tell if you mean 5 choose 2 or 2 choose 5 here. \$\endgroup\$
    – Jesse Millikan
    Commented Mar 22, 2011 at 21:39
  • \$\begingroup\$ @Jesse I got this challenge from another website that only allows major scripting languages, I'll remember this guideline in the future. I edited my question to try and make the challenge requirements more clear, let me know if its clear enough or not. \$\endgroup\$
    – backus
    Commented Mar 22, 2011 at 23:36
  • \$\begingroup\$ I'm new, so we're in much the same boat. However, don't summarize the results; they will just get outdated. Just vote and (if appropriate) accept answers. (Also, you'll make people unhappy if you ignore J and GolfScript answers without a reason.) \$\endgroup\$
    – Jesse Millikan
    Commented Mar 23, 2011 at 4:09

36 Answers 36

Reset to default
1
2
12
\$\begingroup\$

C 96

With I/O (which takes about 34 chars). Added a couple of newlines to make it readable.

main(a,b,c,d){scanf("%d,%d",&a,&b);
d=a-b;for(c=1;a>b;){c*=a--;}for(;d;)
{c/=d--;}printf("%d",c);}

Now if you'll excuse me, I have an ASCII n choose k rocket to catch.

    d;main(a
   ,         b
  ,           c
 )  int        a
 ;   {scanf    (
 (   "%d %d"   )
 ,   &a,  &b   )
 ;   d    =a   -
 b   +     b   -
 b   *     1   ;
 a             -
 a  ;for    (  c
 =  1;a>   b   ;
 )  {c=   c    *
 (  (a-- )     )
 ;  }for(      b
 =  b + 1      ;
 d  ;    )     {
 c  =     c    /
 (  d--    )   ;
  }           {
  }           {
   }         (
  printf("%d",c)
 )      ;       }
/*     *  *   * *\
 * * X   * 8 * * |
|     *      *    \
*/    //       *  */
Improve this answer
\$\endgroup\$
0
11
\$\begingroup\$

APL, 3 bytes

⎕!⎕

Or for those whose browser doesn't render the above, in an ASCII rendering:

{Quad}!{Quad}
Improve this answer
\$\endgroup\$
1
  • 3
    \$\begingroup\$ To be completely conformant to the n,k input, you'd have to do !/⌽⎕. \$\endgroup\$
    – marinus
    Commented Dec 5, 2012 at 23:41
9
\$\begingroup\$

R (11 Chars)

choose(n,r)
Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ You can save 5 bytes (and make it compliant with modern I/O rules) by removing (n,r) \$\endgroup\$
    – caird coinheringaahin g ♦
    Commented Feb 23, 2021 at 4:22
7
\$\begingroup\$

GolfScript, 17 chars

This solution handles cases like k=0 or k=1 correctly.

~>.,,]{1\{)*}/}//

Factorial-like portion is based off a previous answer.

Improve this answer
\$\endgroup\$
6
\$\begingroup\$

GolfScript 21

~~)>.,,]{{)}%{*}*}%~/

Not particularly short, GolfScript lacks a real factorial function, however this has got to be the most wicked data manipulation that I have ever done, this calls for a stack trace:

"5,2" Data on the stack from input.
~ Eval command, note that , is an operator that turns a number into an array.
[0 1 2 3 4] 2
~ Binary not.
[0 1 2 3 4] -3
) Increment.
[0 1 2 3 4] -2
> Take end of array, -2 as parameter to get the last 2 elements.
[3 4]
. Duplicate element.
[3 4] [3 4]
, Array length.
[3 4] 2
, Turn number to array.
[3 4] [0 1]
] Create array.
[[3 4] [0 1]]
{{)}%{*}*} Block of code.
[[3 4] [0 1]] {{)}%{*}*}
% Execute block once for each element of the array. The following part only demonstrate the first loop.
[3 4]
{)}% Increment each array element.
[4 5]
{*} Block containing a multiply command.
[4 5] {*}
* "Fold" the array using the block command, that is in this case make the product of all elements.
20
After the big loop has finished it returns an array with the results.
[20 2]
~ Deconstruct the array.
20 2
/ Division.
10

Improve this answer
\$\endgroup\$
6
\$\begingroup\$

Ruby 1.9, 52 46 (42) characters

eval"A,B="+gets;i=0;p eval"(A-B+i+=1)/i*"*B+?1

If stderr is ignored:

eval"A,B=I="+gets;p eval"I/(A-I-=1)*"*B+?1

Ruby 1.8, 43 characters, no additional output to stderr:

eval"a,b=i="+gets;p eval"i/(a-i-=1)*"*b+"1"

Edits:

  • (52 -> 48) Found a shorter way to parse the input
  • (48 -> 46) Less looping, more eval.
Improve this answer
\$\endgroup\$
4
\$\begingroup\$

Python (56)

f=lambda n,k:k<1and 1or f(n-1,k-1)*n/k;print f(*input())

Ungolfed code and some explanation of a shortcut for calculating the binomial coefficient. (Note: There is some insight that I just haven't figured out in order to get down to the 39 char version; I don't think this approach will get you there.)

# Since choose(n,k) =
#
#     n!/((n-k)!k!)
#
#          [n(n-1)...(n-k+1)][(n-k)...(1)]
#        = -------------------------------
#            [(n-k)...(1)][k(k-1)...(1)]
#
# We can cancel the terms:
#
#     [(n-k)...(1)]
#
# as they appear both on top and bottom, leaving:
#
#    n (n-1)     (n-k+1)
#    - ----- ... -------
#    k (k-1)       (1)
#
# which we might write as:
#
#      choose(n,k) = 1,                      if k = 0
#                  = (n/k)*choose(n-1, k-1), otherwise
#
def choose(n,k):
    if k < 1:
        return 1
    else:
        return choose(n-1, k-1) * n/k

# input() evaluates the string it reads from stdin, so "5,2" becomes
# (5,2) with no further action required on our part.
#
# In the golfed version, we make use of the `*` unpacking operator, 
# to unpack the tuple returned by input() directly into the arguments
# of f(), without the need for intermediate variables n, k at all.
#
n, k = input()

# This line is left as an exercise to the reader.
print choose(n, k)
Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ Could you provide an ungolfed example of your script? \$\endgroup\$
    – backus
    Commented Mar 23, 2011 at 4:43
  • \$\begingroup\$ Can we use * for parsing inputs of the form 4545 78? \$\endgroup\$
    – Quixotic
    Commented Mar 23, 2011 at 14:27
  • \$\begingroup\$ Unfortunately, no, but it's not * that's the issue. 4545 78 isn't a valid Python expression, so input() will raise a SyntaxError. This trick depends entirely on the problem asking for x,y. If you had a function that read x y and returned a tuple, then you could use * with that just fine. \$\endgroup\$
    – user1011
    Commented Mar 23, 2011 at 16:52
4
\$\begingroup\$

RPL (4)

(using built-in function)

COMB
Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Windows PowerShell, 57

$a,$b=iex $input
$p=1
for($a-=$b;$a-ge1){$p*=1+$b/$a--}$p
Improve this answer
\$\endgroup\$
3
\$\begingroup\$

J, 33 36

(":!~/".;._1}:toJ',',1!:1(3))1!:2(4)

35 characters are input, parsing and output. The other character, !, is n choose k.

I don't have Windows around for testing this at the moment, but I believe it should work there.

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Q, 32 chars

{f:{1*/1.+(!)x};f[x]%f[y]*f x-y}
Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Python 2, 39 bytes

n,k=input()
B=2<<n
print(B+1)**n/B**k%B

Try it online!

A full program, as the challenge asks for. The method is explained in this tip.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Perl 6 (55)

my ($a,$b)=lines;$_=1;for 1..$a-$b {$_+=$_*$b/$^a};.say
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

RPL (22)

(not using built-in COMB function)

→ n k 'n!/(k!*(n-k)!)'
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Q (50 45)

 f:{(prd 1.+til x)%((prd 1.+til y)*prd 1.+til x-y)}

You can shave a few characters off the above by removing redundant brackets and using 1*/ instead of prd.

f:{(1*/1.+til x)%(1*/1.+til y)*1*/1.+til x-y}
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Mathematica 12

Straightforward, built-in function.

n~Binomial~k
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Perl 6, 25 16 bytes

-9 bytes thanks to nwellnhof

+*o&combinations

Try it online!

Anonymous function that takes two numbers and returns an int. This uses the built-in combinations and converts the returned list to an int.

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ 16 bytes \$\endgroup\$
    – nwellnhof
    Commented Dec 8, 2018 at 10:45
  • \$\begingroup\$ @nwellnhof Ah, I didn't realise combinations could take an number instead of a list \$\endgroup\$
    – Jo King ♦
    Commented Dec 8, 2018 at 11:02
2
\$\begingroup\$

Python 3.8 (pre-release), 21 bytes

import math
math.comb

Try it online!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

PHP (71 79)

<?$a=fgetcsv(STDIN);$x=1;while($a[1]-$i)$x=$x*($a[0]-++$i+1)/$i;echo$x;


<?php $a=fgetcsv(STDIN);$x=1;while(++$i<=$a[1])$x=$x*($a[0]-$i+1)/$i;echo $x?>

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Python (54)

f=lambda n,k:k<1or f(n-1,k-1)*n/k;print 1*f(*input())

Essentially the same as the Python one above, but I shave off four bytes by dropping the

and 1

from the function definition. However, this results in the function returning True instead of 1 if k=0, but this can be fixed by multiplying with 1 before printing, since 1*True=1, thus adding two bytes.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

J, 11 characters

!~/".1!:1[1

Takes input from the keyboard.

    !~/".1!:1[1
5,2
10
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Jelly, 1 byte

c

Try it online!

2 bytes to take input as n,k

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Rust, 53 bytes

fn f(n:i32,k:i32)->i32{if k<1{1}else{f(n-1,k-1)*n/k}}

This is essentially the same as the Python code in some of the previous answers, and computes the binomial coefficient through recursion.

Try it online!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Go, 58 bytes

func b(n,k int)int{if k<1{return 1}
return b(n-1,k-1)*n/k}

Attempt This Online!

Alternative using math.Gamma(), 82 bytes

import."math"
func b(n,k float64)float64{g:=Gamma
return g(n+1)/(g(k+1)*g(n-k+1))}

Attempt This Online!

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Haskell (80)

f(_,0)=1
f(n,k)=n/k*f(n-1,k-1)
main=getLine>>=putStr.show.f.read.(++")").('(':)

But, if input in the format x y is allowed instead of in the format x,y, it's 74 chars:

f[_,0]=1
f[n,k]=n/k*f[n-1,k-1]
main=interact$show.f.map read.take 2.words
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Scala 54

val n,k=readInt
((k+1)to n product)/(1 to(n-k)product)
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Python (52)

 f=lambda n,k:k<1or f(n-1,k-1)*n/k;print+f(*input())

Improved from the other two by using print+ to convert the result of f from boolean to int in case k==0.

Still have no idea how to shrink it to 39, I wonder whether they are using lambda at all.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

(The OP only loosely specified the input & output method/format, so the following seems acceptable.)

Sage Notebook (39 41 40)

In the current cell,

f=lambda n,k:k<1or f(n-1,k-1)*n/k;+f(*_)

where the input in the form n,k is entered & evaluated in the preceding cell. This simulates "command-line input" by assigning it to _ (similar to command-line arguments).

Sage Notebook (42 44 43)

Alternatively, using "in-source input" (with only the x= and newline characters adding to the score), e.g.,

x=5,2
f=lambda n,k:k<1or f(n-1,k-1)*n/k;+f(*x)

Both of these approaches are obviously spin-offs from earlier answers by others.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Tcl, 80 bytes

proc C n\ k {proc f n {expr $n?($n)*\[f $n-1]:1}
expr [f $n]/([f $k]*[f $n-$k])}

Try it online!

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ Very ungolfy approach, 165 bytes: tio.run/… \$\endgroup\$
    – sergiol
    Commented Dec 4, 2018 at 23:23
0
\$\begingroup\$

Javascript, 27 bytes

First my own 35-byte solutions:

f=(n,k)=>n-k&&k?f(--n,k)+f(n,k-1):1

Or, alternatively,

f=(n,k,i=k)=>i?f(n-1,k-1,i-1)*n/k:1

The first working recursively, with the simple (n,k) = (n-1,k) + (n-1,k-1) rule. The second using that (n,k) = (n-1,k-1) * n/k.

EDIT

I just noticed the solution by Arnould in a duplicate of this:

f=(n,k)=>k?n*f(n-1,k-1)/k:1

Which is a whopping 8 bytes less (27 bytes)

Improve this answer
\$\endgroup\$
1
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.