How do I write this code

Write your question here.

If there are 18 people in your class and you want to divide the class into programming teams of 3
members, you can compute the number of different teams that can be arranged using this formula
(𝑛! 𝑟!(𝑛―𝑟)!).
Write a C++ program that determines the number of potential team arrangements. You will need
to use the double type variable for this computation.

kigar64551 (784)

https://en.wikipedia.org/wiki/Binomial_coefficient

The binomial coefficient "n over k" tells you how many different ways there are to pick k elements from a set of n elements. You can look up the correct formulae to compute the binomial coefficient on Wikipedia.

You obviously will need to implement the factorial (i.e. n!) function, because it's needed for the computation.

The double type needs to be used for the final division, as you do not want integer division here!

(Anything before the final division can be done with integers)

Last edited on

lastchance (6980)

#include <iostream>

double nCr( int n, int r ) { return r ? nCr( n - 1, r - 1) * n / r : 1.0; }

int main()
{
   std::cout << nCr( 18, 3 ) << '\n';
}

You don't strictly need a double, either.

#include <iostream>

unsigned long long nCr( int n, int r )
{
   if ( r > n - r ) return nCr( n, n - r );      // slightly more efficient
   unsigned long long result = 1;
   for ( int i = 1, j = n; i <= r; i++, j-- ) result = result * j / i;
   return result;
}


int main()
{
   std::cout << nCr( 18, 3 ) << '\n';
}

Last edited on

seeplus (6460)

#include <iostream>
#include <utility>

using T = unsigned long long;

T ncr(T n, T r) {
	if (r > n)
		std::swap(n, r);

	T res { 1 };

	for (; r >= 1; --r, --n)
		res = (res * n) / r;

	return res;
}

int main() {
	std::cout << "18C3: " << ncr(18, 3) << '\n';
}


18C3: 816

Last edited on

lastchance (6980)

Your code is wrong, @seeplus and the problem is here:

1
2

	for (; r >= 1; --r, --n)
		res = (res * n) / r;

Try ¹⁸C₅ instead - it will produce the wrong answer.

To avoid problems with integer division (i.e. ensure that the required factors are already present in the result) you have to work the divisor upwards from 1, not downwards from the original r.

Your code only works for ¹⁸C₃ because, fortuitously, 18 happens to have a factor of 3 ... it doesn't have a factor of 5.

The lines

1
2

	if (r > n)
		std::swap(n, r);

also do not make sense. ³C₁₈ does not exist, for example. There is no question of it being ¹⁸C₃.

Last edited on

seeplus (6460)

Ahhh....... I only tried it with the given numbers. That just shows the requirement for thorough testing! Yes - it should be 8568.

I should have realised as:

res *= n /r;

doesn't work.

Dohhh...

I blame lack of caffeine...

Last edited on

seeplus (6460)

OK. Lets try this one more time...

#include <iostream>
#include <algorithm>

using T = unsigned long long;

constexpr T ncr(T n, T r) {
	T num { n }, dom { r = std::min(r, n - r) };

	for (; r > 1; num *= --n, dom *= --r);

	return num / dom;
}

int main() {
	std::cout << "18C5: " << ncr(18, 5) << '\n';
	std::cout << "18C4: " << ncr(18, 4) << '\n';
	std::cout << "18C3: " << ncr(18, 3) << '\n';
}


18C5: 8568
18C4: 3060
18C3: 816

Last edited on

lastchance (6980)

#include <iostream>
#include <valarray>
using namespace std;

using ARRAY = valarray<unsigned long long>;

ARRAY Pascal( int n )
{
   ARRAY result( 0ull, n + 1 );   result[0] = 1;
   for ( int i = 1; i <= n; i++ ) result += result.shift( -1 );
   return result;
}

int main()
{
   for ( auto e : Pascal( 18 ) ) cout << e << " ";
}

1 18 153 816 3060 8568 18564 31824 43758 48620 43758 31824 18564 8568 3060 816 153 18 1

Yes, 816, 3060, 8568 are correct.

But because you don't do the division until the end you will overflow for smaller n than you need to.

Last edited on

anup30 (968)

//nCr
#include <iostream>
using namespace std;

int main(){
	int n=18, r=3;
	int nn=1, nr=1;
	for(int i=r, j=n; i>0; i--, j--){
		nn *= j;
		nr *= i;
	}
	cout<< nn/nr;
}

lastchance (6980)

@anup,
Try n=18, r=9
(The answer should be 48620 - well within the range of an int.)

Or try n=18, r=15 (which should give the same answer as n=18,r=3).

Last edited on

anup30 (968)

@lastchance, nice catch. in for loop, line 9, nn becomes greater than INT_MAX.
so,

long long nn=1, nr=1;
is fix for line7.

//nCr
#include <iostream>
using namespace std;

int main(){
	int n=18, r=15;
	long long nn=1, nr=1;
	for(int i=r, j=n; i>0; i--, j--){
		nn *= j;
		nr *= i;
	}
	cout<< nn/nr;
}

lastchance (6980)

The extra range of a long long certainly buys you more time. However, despite the formula, avoiding ever having to store r! allows you to calculate to much higher values. The Pascal’s Triangle approach is useful here, as it is purely additive.

seeplus (6460)

Also make unsigned rather than signed. See lastchance's 2 versions and my version above.

As you are effectively decrementing r whilst positive, the smaller the value of r the fewer times round the loop - hence fewer multiplications and the higher the value of n that can be used without overflow.

As nCr is the same as nC(n-r), then for i use the minimum of either r or (n - r).

JLBorges (13770)

#include <iostream>
#include <map>
#include <boost/multiprecision/cpp_int.hpp>

boost::multiprecision::cpp_int nCr( unsigned int n, unsigned int r )
{
    static std::map< std::pair< unsigned int, unsigned int >, boost::multiprecision::cpp_int > memo ;

    boost::multiprecision::cpp_int& result = memo[ {n,r} ] ;

    if( n == r || r == 0 ) result = 1 ; // base case
    else if( r == 1 ) result = n ; // base case
    else if( result == 0 ) result = nCr( n-1, r ) + nCr( n-1, r-1 ) ; // recurse

    return result ;
}

int main()
{
    std::cout << nCr( 1000, 300 ) << '\n' ;
}

http://coliru.stacked-crooked.com/a/92a2f4dd6128b539

Topic archived. No new replies allowed.

C++

Forum

How do I write this code