Ways to arrange Balls such that adjacent balls are of different types - GeeksforGeeks
There are 'a' balls of type A, 'b' balls of type B and 'c' balls of type C. Using the balls we want to create a straight colorful line such that no two balls of same type are adjacent.
Read full article from Ways to arrange Balls such that adjacent balls are of different types - GeeksforGeeks
There are 'a' balls of type A, 'b' balls of type B and 'c' balls of type C. Using the balls we want to create a straight colorful line such that no two balls of same type are adjacent.
Input : a = 1, b = 1, c = 0 Output : 2 There are only two arrangements AB and BA Input : a = 1, b = 1, c = 1 Output : 6 There are only six arrangements ABC, BAC, BCA, CBA, ACB and CAB
We can observe that there are many subproblems being solved again and again so the problem can be solved using Dynamic Programming (DP). We can easily make memoization solution to this problem.
Time complexity : O(a*b*c)
Auxiliary Space : O(a*b*c*3)
Auxiliary Space : O(a*b*c*3)
// table to store to store results of subproblems
int
dp[MAX][MAX][MAX][3];
// Returns count of arrangements where last placed ball is
// 'last'. 'last' is 0 for 'a', 1 for 'b' and 2 for 'c'
int
countWays(
int
a,
int
b,
int
c,
int
last)
{
// if number of balls of any color becomes less
// than 0 the number of ways arrangements is 0.
if
(a<0 || b<0 || c<0)
return
0;
// If last ball required is of type A and the number
// of balls of A type is 1 while number of balls of
// other color is 0 the number of ways is 1.
if
(a==1 && b==0 && c==0 && last==0)
return
1;
// Same case as above for 'b' and 'c'
if
(a==0 && b==1 && c==0 && last==1)
return
1;
if
(a==0 && b==0 && c==1 && last==2)
return
1;
// If this subproblem is already evaluated
if
(dp[a][b][last] != -1)
return
dp[a][b][last];
// if last ball required is A and the number of ways is
// the sum of number of ways to form sequence with 'a-1' A
// balls, b B Balls and c C balls ending with B and C.
if
(last==0)
dp[a][b]1[last] = countWays(a-1,b,c,1) + countWays(a-1,b,c,2);
// Same as above case for 'b' and 'c'
else
if
(last==1)
dp[a][b]1[last] = countWays(a,b-1,c,0) + countWays(a,b-1,c,2);
else
//(last==2)
dp[a][b]1[last] = countWays(a,b,c-1,0) + countWays(a,b,c-1,1);
return
dp[a][b]1[last];
}
// Returns count of required arrangements
int
countUtil(
int
a,
int
b,
int
c)
{
// Initialize 'dp' array
memset
(dp, -1,
sizeof
(dp));
// Three cases arise:
return
countWays(a, b, c, 0) +
// Last required balls is type A
countWays(a, b, c, 1) +
// Last required balls is type B
countWays(a, b, c, 2);
// Last required balls is type C
}
The naive solution to this problem is a recursive solution. We recursively call for three cases
1) Last ball to be placed is of type A
2) Last ball to be placed is of type B
3) Last ball to be placed is of type C
1) Last ball to be placed is of type A
2) Last ball to be placed is of type B
3) Last ball to be placed is of type C
// Returns count of arrangements where last placed ball is
// 'last'. 'last' is 0 for 'a', 1 for 'b' and 2 for 'c'
int
countWays(
int
a,
int
b,
int
c,
int
last)
{
// if number of balls of any color becomes less
// than 0 the number of ways arrangements is 0.
if
(a<0 || b<0 || c<0)
return
0;
// If last ball required is of type A and the number
// of balls of A type is 1 while number of balls of
// other color is 0 the number of ways is 1.
if
(a==1 && b==0 && c==0 && last==0)
return
1;
// Same case as above for 'b' and 'c'
if
(a==0 && b==1 && c==0 && last==1)
return
1;
if
(a==0 && b==0 && c==1 && last==2)
return
1;
// if last ball required is A and the number of ways is
// the sum of number of ways to form sequence with 'a-1' A
// balls, b B Balls and c C balls ending with B and C.
if
(last==0)
return
countWays(a-1,b,c,1) + countWays(a-1,b,c,2);
// Same as above case for 'b' and 'c'
if
(last==1)
return
countWays(a,b-1,c,0) + countWays(a,b-1,c,2);
if
(last==2)
return
countWays(a,b,c-1,0) + countWays(a,b,c-1,1);
}
// Returns count of required arrangements
int
countUtil(
int
a,
int
b,
int
c)
{
// Three cases arise:
return
countWays(a, b, c, 0) +
// Last required balls is type A
countWays(a, b, c, 1) +
// Last required balls is type B
countWays(a, b, c, 2);
// Last required balls is type C
}
Read full article from Ways to arrange Balls such that adjacent balls are of different types - GeeksforGeeks