CS21003 Algorithms I CS29003 Algorithms Laboratory Autumn 2012, L-T-P: 3-1-0 L-T-P: 0-0-3

## Warm-up Assignment

You are given R red marbles and B blue marbles. Your task is to arrange the R + B marbles in a line such that certain restrictions are satisfied (see below). You print all possible arrangements under the given restrictions, and the total count of arrangements possible.

### Part 1

In this part, the restriction is that no two red marbles may be placed consecutively. Write a single recursive function to print the arrangements and return the count of possibilities. Do not use any global or static variables. Place the available marbles one by one in an array of size R + B. When u red and v blue marbles are placed, find out the options (red and/or blue) at the (u + v + 1)-st position. For each available option, recursively compute the acceptable configurations with u + v + 1 marbles placed in the array.

### Part 2

In this part, two red marbles may appear in consecutive positions, but three or more red marbles are not allowed to come consecutively. Write a second recursive function following the same line of programming logic as in Part 1.

### Sample output

```   Enter number of red marbles (R)  : 2
Enter number of blue marbles (B) : 4

Part 1
rbrbbb
rbbrbb
rbbbrb
rbbbbr
brbrbb
brbbrb
brbbbr
bbrbrb
bbrbbr
bbbrbr
Total number of possibilities is 10

Part 2
rrbbbb
rbrbbb
rbbrbb
rbbbrb
rbbbbr
brrbbb
brbrbb
brbbrb
brbbbr
bbrrbb
bbrbrb
bbrbbr
bbbrrb
bbbrbr
bbbbrr
Total number of possibilities is 15
```

### Theoretical exercises

• Construct recurrence relations for computing these counts of arrangements.

• Analyze the running times of these recursive algorithms.