Find total arrangements such that no two balls of the same color are together
Given r red, b blue, and g green balls, find the total number of arrangements in a row such that no two balls of the same color end up together.
For example,
Input: r = 1, b = 2, g = 1
Output: Total number of arrangements are 6
The arrangements are [bgbr, bgrb, brbg, brgb, gbrb, rbgb]
Input: r = 2, b = 3, g = 1
Output: Total number of arrangements are 10
The arrangements are [bgbrbr, bgrbrb, brbgbr, brbgrb, brbrbg, brbrgb, brgbrb, gbrbrb, rbgbrb, rbrbgb]
Output: Total number of arrangements are 6
The arrangements are [bgbr, bgrb, brbg, brgb, gbrb, rbgb]
Input: r = 2, b = 3, g = 1
Output: Total number of arrangements are 10
The arrangements are [bgbrbr, bgrbrb, brbgbr, brbgrb, brbrbg, brbrgb, brgbrb, gbrbrb, rbgbrb, rbrbgb]
Let f(r, b, g, c) denote the total number of the arrangements where r red, b blue, and g green balls are left, and the color of the last ball was c. Now, there are three possible cases:
- If the last ball taken was red, then the total number of ways is
f(r, b, g, red) = f(r, b - 1, g, blue) + f(r, b, g - 1, green) - If the last ball taken was blue, then the total number of ways is
f(r, b, g, blue) = f(r - 1, b, g, red) + f(r, b, g - 1, green) - If the last ball taken was green, then the total number of ways is
f(r, b, g, green) = f(r - 1, b, g, red) + f(r, b - 1, g, blue)
Following is the recursive implementation in C, Java, and Python to find the total number of arrangements using the above recurrence:
C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
#include <stdio.h> // Function to find the total number of arrangements of `r` red, `b` blue, and // `g` green balls such that no two balls of the same color are together int f(int r, int b, int g, char prev) { // base case: invalid number of balls if (r < 0 || b < 0 || g < 0) { return 0; } // base case: all balls are exhausted if (r == 0 && b == 0 && g == 0) { return 1; } // if the last ball was red if (prev == 'r') { // current ball can be either blue or green… recur with one less ball return f(r, b - 1, g, 'b') + f(r, b, g - 1, 'g'); } // if the last ball was blue if (prev == 'b') { // current ball can be either red or green… recur with one less ball return f(r - 1, b, g, 'r') + f(r, b, g - 1, 'g'); } // if the last ball was green if (prev == 'g') { // current ball can be either red or blue… recur with one less ball return f(r - 1, b, g, 'r') + f(r, b - 1, g, 'b'); } } // Wrapper over function `f()` int totalWays(int r, int b, int g) { /* Recursively call `f()` for the following cases and return their total: 1. Start with the red ball and recur with one less red ball 2. Start with the blue ball and recur with one less blue ball 3. Start with the green ball and recur with one less green ball */ return f(r - 1, b, g, 'r') + f(r, b - 1, g, 'b') + f(r, b, g - 1, 'g'); } int main() { int r = 2, b = 3, g = 1; printf("The total number of distinct arrangements are %d", totalWays(r, b, g)); return 0; } |
Output:
The total number of distinct arrangements are 10
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
class Main { // Function to find the total number of arrangements of `r` red, `b` blue, and // `g` green balls such that no two balls of the same color are together public static int f(int r, int b, int g, char prev) { // base case: invalid number of balls if (r < 0 || b < 0 || g < 0) { return 0; } // base case: all balls are exhausted if (r == 0 && b == 0 && g == 0) { return 1; } // if the last ball was red if (prev == 'r') { // current ball can be either blue or green… recur with one less ball return f(r, b - 1, g, 'b') + f(r, b, g - 1, 'g'); } // if the last ball was blue if (prev == 'b') { // current ball can be either red or green… recur with one less ball return f(r - 1, b, g, 'r') + f(r, b, g - 1, 'g'); } // if the last ball was green if (prev == 'g') { // current ball can be either red or blue… recur with one less ball return f(r - 1, b, g, 'r') + f(r, b - 1, g, 'b'); } return 0; } // Wrapper over method `f()` public static int totalWays(int r, int b, int g) { /* Recursively call `f()` for the following cases and return their total: 1. Start with the red ball and recur with one less red ball 2. Start with the blue ball and recur with one less blue ball 3. Start with the green ball and recur with one less green ball */ return f(r - 1, b, g, 'r') + f(r, b - 1, g, 'b') + f(r, b, g - 1, 'g'); } public static void main(String[] args) { int r = 2, b = 3, g = 1; System.out.println("The total number of distinct arrangements are " + totalWays(r, b, g)); } } |
Output:
The total number of distinct arrangements are 10
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
# Function to find the total number of arrangements of `r` red, `b` blue, and # `g` green balls such that no two balls of the same color are together def f(r, b, g, prev): # base case: invalid number of balls if r < 0 or b < 0 or g < 0: return 0 # base case: all balls are exhausted if r == 0 and b == 0 and g == 0: return 1 # if the last ball was red if prev == 'r': # current ball can be either blue or green… recur with one less ball return f(r, b - 1, g, 'b') + f(r, b, g - 1, 'g') # if the last ball was blue if prev == 'b': # current ball can be either red or green… recur with one less ball return f(r - 1, b, g, 'r') + f(r, b, g - 1, 'g') # if the last ball was green if prev == 'g': # current ball can be either red or blue… recur with one less ball return f(r - 1, b, g, 'r') + f(r, b - 1, g, 'b') # Wrapper over function `f()` def totalWays(r, b, g): ''' Recursively call `f()` for the following cases and return their total: 1. Start with the red ball and recur with one less red ball 2. Start with the blue ball and recur with one less blue ball 3. Start with the green ball and recur with one less green ball ''' return f(r - 1, b, g, 'r') + f(r, b - 1, g, 'b') + f(r, b, g - 1, 'g') if __name__ == '__main__': (r, b, g) = (2, 3, 1) print('The total number of distinct arrangements are', totalWays(r, b, g)) |
Output:
The total number of distinct arrangements are 10
We can also devise a recurrence relation by assuming the next ball’s color instead of tracking the last ball’s color.
Let f(r, b, g, c) denote the total number of the arrangements where r red, b blue, and g green balls are left, and the color of the next ball will be c. Now, there are three possible cases:
- If the next ball is red, then the total number of ways is
f(r, b, g, red) = f(r - 1, b, g, blue) + f(r - 1, b, g, green) - If the next ball is blue, then the total number of ways is
f(r, b, g, blue) = f(r, b - 1, g, red) + f(r, b - 1, g, green) - If the next ball is green, then the total number of ways is
f(r, b, g, green) = f(r, b, g - 1, red) + f(r, b, g - 1, blue)
Following is the implementation of the above recurrence in C, Java, and Python:
C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
#include <stdio.h> // Function to find the total number of arrangements of `r` red, `b` blue, and // `g` green balls such that no two balls of the same color are together int f(int r, int b, int g, char next) { // base case: invalid number of balls if (r < 0 || b < 0 || g < 0) { return 0; } // if the next ball is red if (next == 'r') { // base case: only 1 red ball is left, and other color balls are exhausted if (r == 1 && b == 0 && g == 0) { return 1; } // recur with one less red ball… the next ball can be either blue or green return f(r - 1, b, g, 'b') + f(r - 1, b, g, 'g'); } // if the next ball is blue if (next == 'b') { // base case: only 1 blue ball is left, and other color balls are exhausted if (r == 0 && b == 1 && g == 0) { return 1; } // recur with one less blue ball… the next ball can be either red or green return f(r, b - 1, g, 'r') + f(r, b - 1, g, 'g'); } // if the next ball is green if (next == 'g') { // base case: only 1 green ball is left, and other color balls are exhausted if (r == 0 && b == 0 && g == 1) { return 1; } // recur with one less green ball… the next ball can be either red or blue return f(r, b, g - 1, 'r') + f(r, b, g - 1, 'b'); } } // Wrapper over function `f()` int totalWays(int r, int b, int g) { /* Recursively call `f()` for the following cases and return their total: 1. Start with the red ball 2. Start with the blue ball 3. Start with the green ball */ return f(r, b, g, 'r') + f(r, b, g, 'b') + f(r, b, g, 'g'); } int main() { int r = 2, b = 3, g = 1; printf("The total number of distinct arrangements are %d", totalWays(r, b, g)); return 0; } |
Output:
The total number of distinct arrangements are 10
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
class Main { // Function to find the total number of arrangements of `r` red, `b` blue, and // `g` green balls such that no two balls of the same color are together public static int f(int r, int b, int g, char next) { // base case: invalid number of balls if (r < 0 || b < 0 || g < 0) { return 0; } // if the next ball is red if (next == 'r') { // base case: only 1 red ball is left, and other color balls are exhausted if (r == 1 && b == 0 && g == 0) { return 1; } // recur with one less red ball… the next ball can be either blue or green return f(r - 1, b, g, 'b') + f(r - 1, b, g, 'g'); } // if the next ball is blue if (next == 'b') { // base case: only 1 blue ball is left, and other color balls are exhausted if (r == 0 && b == 1 && g == 0) { return 1; } // recur with one less blue ball… the next ball can be either red or green return f(r, b - 1, g, 'r') + f(r, b - 1, g, 'g'); } // if the next ball is green if (next == 'g') { // base case: only 1 green ball is left, and other color balls are // exhausted if (r == 0 && b == 0 && g == 1) { return 1; } // recur with one less green ball… the next ball can be either red or blue return f(r, b, g - 1, 'r') + f(r, b, g - 1, 'b'); } return 0; } // Wrapper over function `f()` public static int totalWays(int r, int b, int g) { /* Recursively call `f()` for the following cases and return their total: 1. Start with the red ball 2. Start with the blue ball 3. Start with the green ball */ return f(r, b, g, 'r') + f(r, b, g, 'b') + f(r, b, g, 'g'); } public static void main(String[] args) { int r = 2, b = 3, g = 1; System.out.println("The total number of distinct arrangements are " + totalWays(r, b, g)); } } |
Output:
The total number of distinct arrangements are 10
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
# Function to find the total number of arrangements of `r` red, `b` blue, and # `g` green balls such that no two balls of the same color are together def f(r, b, g, next): # base case: invalid number of balls if r < 0 or b < 0 or g < 0: return 0 # if the next ball is red if next == 'r': # base case: only 1 red ball is left, and other color balls are exhausted if r == 1 and b == 0 and g == 0: return 1 # recur with one less red ball… the next ball can be either blue or green return f(r - 1, b, g, 'b') + f(r - 1, b, g, 'g') # if the next ball is blue if next == 'b': # base case: only 1 blue ball is left, and other color balls are exhausted if r == 0 and b == 1 and g == 0: return 1 # recur with one less blue ball… the next ball can be either red or green return f(r, b - 1, g, 'r') + f(r, b - 1, g, 'g') # if the next ball is green if next == 'g': # base case: only 1 green ball is left, and other color balls are exhausted if r == 0 and b == 0 and g == 1: return 1 # recur with one less green ball… the next ball can be either red or blue return f(r, b, g - 1, 'r') + f(r, b, g - 1, 'b') # Wrapper over function `f()` def totalWays(r, b, g): ''' Recursively call `f()` for the following cases and return their total: 1. Start with the red ball 2. Start with the blue ball 3. Start with the green ball ''' return f(r, b, g, 'r') + f(r, b, g, 'b') + f(r, b, g, 'g') if __name__ == '__main__': (r, b, g) = (2, 3, 1) print('The total number of distinct arrangements are', totalWays(r, b, g)) |
Output:
The total number of distinct arrangements are 10
The time complexity of the above solution is exponential, as many subproblems are recalculated repeatedly. The repeated subproblems can be easily seen by drawing a recursion tree.
The problems having an optimal substructure and overlapping subproblems can be solved using dynamic programming. The dynamic programming solution is left as an exercise to readers. The expected time complexity of the dynamic programming solution is O(r.b.g).
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)