Mathematical Combination

Question

Write a program that takes an input such as:

n,k

which then computes:

and then prints the result.

---

A numerical example:

Input:

5,2

Internal computation:

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.

The current lowest character counts by language are:

Perl: 35

Ruby: 36

Python: 39

PHP: 62

Answer 1

APL, 3 chars

⎕!⎕

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

{Quad}!{Quad}

Answer 2

GolfScript, 17 chars

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

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

Factorial-like portion is based off a previous answer.

Answer 3

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

Answer 4

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.

Answer 5

R (11 Chars)

choose(n,r)

Answer 6

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)

Answer 7

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.

Answer 8

RPL (4)

(using built-in function)

COMB

Answer 9

Q, 32 chars

{f:{1*/1.+(!)x};f[x]%f[y]*f x-y}

Answer 10

Windows PowerShell, 57

$a,$b=iex $input
$p=1
for($a-=$b;$a-ge1){$p*=1+$b/$a--}$p

Answer 11

RPL (22)

(not using built-in COMB function)

→ n k 'n!/(k!*(n-k)!)'

Answer 12

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}

Answer 13

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 * * |
|     *      *    \
*/    //       *  */

Answer 14

Perl 6 (55)

my ($a,$b)=lines;$_=1;for 1..$a-$b {$_+=$_*$b/$^a};.say

Answer 15

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

Answer 16

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.

Answer 17

J, 11 characters

!~/".1!:1[1

Takes input from the keyboard.

    !~/".1!:1[1
5,2
10

Answer 18

Mathematica 12

Straightforward, built-in function.

n~Binomial~k

Answer 19

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

Answer 20

Scala 54

val n,k=readInt
((k+1)to n product)/(1 to(n-k)product)

Answer 21

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.

Answer 22

PHP 52 bytes

If you'll allow command line arguments (instead of reading from STDIN, as codegolf requires), the shortest PHP solution can be made 10 bytes shorter:

<?for($j++;$k=&$argv[2];$j*=$argv[1]--/$k--);echo$j;

Sample I/O:

$ php choose.php 75 71
1215450

A few other interesting, but slightly longer variants include:

55 bytes

<?for($j++,list(,$n,$k)=$argv;$k;$j*=$n--/$k--);echo$j;

56 bytes

<?for(extract($argv,4,$j++);$_2;$j*=$_1--/$_2--);echo$j;

Answer 23

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

Answer 24

Python (49)

n,k=input()
f=1
while k:f*=n/k;n-=1;k-=1
print f