# Number of sequences when no adjacent items can be the same

I came across this one problem,

There is a particular sequence only uses the numbers 1, 2, 3, 4 and no two adjacent numbers are the same. Write a program that given n1 1s, n2 2s, n3 3s, n4 4s will output the number of such sequences using all these numbers. Output your answer modulo 1000000007 (10^9 + 7).

I can't figure out the solution of this. Will this be done with DP or some kind of DFS with backtracking?

• This seems to be a question of simple combinatorics, no DP or graph algorithms needed. However, I don't understand what `n1 1s, n2 2s, n3 3s, n4 4s` is supposed to mean, and whether there is an upper limit on sequence length. – amon Nov 9 '14 at 9:54
• It means that symbol `1` can be used `n1` times maximum in any sequence, symbol `2` - `n2` times max, etc. I suppose lower limit is 0 for each, so sequences with some "leftover" symbols are allowed. – scriptin Nov 9 '14 at 9:59

If I'm correct, the graph traversal solution is pretty straightforward: you may traverse the graph with recursive function memorizing only current "left" symbols and last used one.

1. let there be a function `f` of `input` (key-value pairs, where keys are `1`..`4`; values are `n1`..`n4`) and `p` - last used number, and `p` is initially undefined
2. in a loop, if `input[i] > 0` and `i != p`, where `i` is a key
1. add 1 to result, because you found another solution, 1 symbol longer
2. set `inputUpd := input` (copy for recursive call)
3. decrement `inputUpd[i]`, because we've just used symbol `i` and there is one such symbol less left
4. set `p := i`, because we've just used `i`
5. add the value of `f(inputUpd, p)` (recursive call with "smaller" input and last used symbol) to result

I couldn't help myself, so here is the code in JS. Skip it if you want to figure out the solution yourself.

``````function f(input, prev) {
var acc = 0;
for (i in input) {
if (i != prev && input[i] > 0) {
var inputUpd = {};
for (j in input) {
inputUpd[j] = (j == i) ? (input[j] - 1) : input[j];
}
acc += 1 + f(inputUpd, i);
}
}
return acc;
}

f({'1': 1, '2': 1}) // -> 4: , , [1,2], [2,1]
f({'1': 1, '2': 2}) // -> 5: , , [1,2], [2,1], [2,1,2]
f({'1': 1, '2': 3}) // -> 5: same as before, but single `2` is leftover
f({'1': 1, '2': 1, '3': 2, '4': 2}) // -> 288
``````