Ways to arrange Balls such that adjacent balls are of different types | Python3 program to count number of ways to arrange three types of balls such that no two balls of same color are adjacent to each other ; table to store to store results of subproblems ; Returns count of arrangements where last placed ball is ' last ' . ' last ' is 0 for ' p ' , 1 for ' q ' and 2 for 'r ; if number of balls of any color becomes less than 0 the number of ways arrangements is 0. ; If last ball required is of type P and the number of balls of P type is 1 while number of balls of other color is 0 the number of ways is 1. ; Same case as above for ' q ' and 'r ; If this subproblem is already evaluated ; if last ball required is P and the number of ways is the sum of number of ways to form sequence with ' p - 1' P balls , q Q Balls and r R balls ending with Q and R . ; Same as above case for ' q ' and 'r ; ( last == 2 ) ; Returns count of required arrangements ; Three cases arise : Last required balls is type P Last required balls is type Q Last required balls is type R ; Driver Code
MAX = 100 ; NEW_LINE dp = [ [ [ [ - 1 ] * 4 for i in range ( MAX ) ] for j in range ( MAX ) ] for k in range ( MAX ) ] ; NEW_LINE ' NEW_LINE def countWays ( p , q , r , last ) : NEW_LINE INDENT if ( p < 0 or q < 0 or r < 0 ) : NEW_LINE INDENT return 0 ; NEW_LINE DEDENT if ( p == 1 and q == 0 and r == 0 and last == 0 ) : NEW_LINE INDENT return 1 ; NEW_LINE DEDENT DEDENT ' NEW_LINE INDENT if ( p == 0 and q == 1 and r == 0 and last == 1 ) : NEW_LINE INDENT return 1 ; NEW_LINE DEDENT if ( p == 0 and q == 0 and r == 1 and last == 2 ) : NEW_LINE INDENT return 1 ; NEW_LINE DEDENT if ( dp [ p ] [ q ] [ r ] [ last ] != - 1 ) : NEW_LINE INDENT return dp [ p ] [ q ] [ r ] [ last ] ; NEW_LINE DEDENT if ( last == 0 ) : NEW_LINE INDENT dp [ p ] [ q ] [ r ] [ last ] = ( countWays ( p - 1 , q , r , 1 ) + countWays ( p - 1 , q , r , 2 ) ) ; NEW_LINE DEDENT DEDENT ' NEW_LINE INDENT elif ( last == 1 ) : NEW_LINE INDENT dp [ p ] [ q ] [ r ] [ last ] = ( countWays ( p , q - 1 , r , 0 ) + countWays ( p , q - 1 , r , 2 ) ) ; NEW_LINE DEDENT else : NEW_LINE INDENT dp [ p ] [ q ] [ r ] [ last ] = ( countWays ( p , q , r - 1 , 0 ) + countWays ( p , q , r - 1 , 1 ) ) ; NEW_LINE DEDENT return dp [ p ] [ q ] [ r ] [ last ] ; NEW_LINE DEDENT def countUtil ( p , q , r ) : NEW_LINE INDENT return ( countWays ( p , q , r , 0 ) + countWays ( p , q , r , 1 ) + countWays ( p , q , r , 2 ) ) ; NEW_LINE DEDENT p , q , r = 1 , 1 , 1 ; NEW_LINE print ( countUtil ( p , q , r ) ) ; NEW_LINE