Number of ways to arrange N items under given constraints | C ++ program to find number of ways to arrange items under given constraint ; method returns number of ways with which items can be arranged ; Calculate value of Binomial Coefficient in bottom up manner ; Base Cases ; Calculate value using previously stored values ; declare dp array to store result up to ith colored item ; variable to keep track of count of items considered till now ; loop over all different colors ; populate next value using current value and stated relation ; return value stored at last index ; Driver code to test above methods
#include <bits/stdc++.h> NEW_LINE using namespace std ; int waysToArrange ( int N , int K , int k [ ] ) { int C [ N + 1 ] [ N + 1 ] ; int i , j ; for ( i = 0 ; i <= N ; i ++ ) { for ( j = 0 ; j <= i ; j ++ ) { if ( j == 0 j == i ) C [ i ] [ j ] = 1 ; else C [ i ] [ j ] = ( C [ i - 1 ] [ j - 1 ] + C [ i - 1 ] [ j ] ) ; } } int dp [ K ] ; int count = 0 ; dp [ 0 ] = 1 ; for ( int i = 0 ; i < K ; i ++ ) { dp [ i + 1 ] = ( dp [ i ] * C [ count + k [ i ] - 1 ] [ k [ i ] - 1 ] ) ; count += k [ i ] ; } return dp [ K ] ; } int main ( ) { int N = 4 ; int k [ ] = { 2 , 2 } ; int K = sizeof ( k ) / sizeof ( int ) ; cout << waysToArrange ( N , K , k ) << endl ; return 0 ; }