How to find out the number of possible ways of adding 1 2 and 3 to given sum avoiding repetition?

Question

This problem is related to this and this one, but I want to put some restrictions here.

Repeat the question

So, I want to find out the number of possible ways to add 1, 2 and 3 to N. The solution can be calculated using recursive formula F[n] = F[n-1] + F[n-2] + F[n-3], where F[0] = 1, F[1] = 1, F[2] = 2. Of course, using dynamic programming I can solve it in linear time.

My restriction

The restriction is: the resulting sequence must have no two elements repeated in a row.
So, for N = 4 the result could be [[1, 1, 1, 1], [2, 1, 1], [1, 2, 1], [3, 1], [1, 1, 2], [2, 2], [1, 3]], but 1 1 1 1, 2 1 1, 1 1 2 and 2 2 is forbidden, so, applying the restriction F[4] becomes 3.

Can someone say how the recursive formula for this problem will look like? Or maybe someone has better idea?

I'm posting this problem here, because it's related to dynamic programming, not to math and combinatorics.

If I understand your restriction correctly, then `F[4] = 2`, not 3, as `[1, 2, 1]` is also forbidden? — Zionsof, Apr 14 '19 at 15:00
@Zionsof, no, because number should not be **repeated in a row**. In simple words, either `1 1` or `2 2` or `3 3` is bad, but `1 2` or `2 1` is good. — Paul Lynn, Apr 14 '19 at 15:07
If you cannot repeat number then you only have limited number of option as 8 (2^3 - as 3 numbers and each can be 1 or 0 times) - so just check all 8 options — dWinder, Apr 14 '19 at 15:19
@dWinder, I can't get you. Could you please apply your idea to `F[5]` or `F[4]`? — Paul Lynn, Apr 14 '19 at 15:22
I will try demonstrate like this - what will be the solution for `F[6]`? Should be 0 as max available is 5 (`F[5]` = 1 because only is `[2,3]`. So all you have to do is run loop 8 times and count solutions — dWinder, Apr 14 '19 at 15:27

score 1 · Answer 1 · answered Apr 14 '19 at 15:27

Well all you need to do is add one more dimension to classical fibonaccii dp solution.

So dp[n][x] - number of possible ways to get some numbers 1,2,3 such that their sum is n and they do not have elements repeated in a row

base case is easy just pick some unused element (i.e. 0) and set it as one way to make sum of 0.

So dp[0][0] = 1

Now just fill up dp table

const int n = 4;
    int dp[n+5][5] = {};
    dp[0][0] = 1;

    for(int i=0; i<=n; i++) //current sum
        for(int j=1; j<=3; j++) //what we use now to extend sum
            for(int k=0; k<=3; k++) //last used
            if(j!=k) //we cant use same as last
            dp[i+n][j]+=dp[i][k];

    cout<<dp[n][1]+dp[n][2]+dp[n][3]; //our sequence could end in any of 1,2,3 so just sum it up

Complexity O(n)

Paul Hankin · Accepted Answer · 2019-04-14T16:05:00.327

Let F1, F2, F3 be the number of ways of constructing N from 1, 2 and 3, without starting with 1, 2, 3 respectively.

Then:

F1(N) = F2(N-2) + F3(N-3)
F2(N) = F1(N-1) + F3(N-3)
F3(N) = F1(N-1) + F2(N-2)

with the edge conditions:

F1(0) = F2(0) = F3(0) = 1
F1(x) = F2(x) = F3(x) = 0 (for x < 0)

Then to solve the original problem: F(0) = 1, F(N) = F1(N-1) + F2(N-2) + F3(N-3)

A linear-time solution that uses O(1) space:

def F(N):
    a, b, c, d, e, f, g, h, i = 1, 0, 0, 1, 0, 0, 1, 0, 0
    for _ in range(N-1):
        a, b, c, d, e, f, g, h, i = e+i, a, b, a+i, d, e, a+e, g, h
    return a+e+i

for n in range(11):
    print(n, F(n))

This uses these recurrence relations:

F1(i+1), F1(i), F1(i-1) = F2(i-1)+F3(i-2), F1(i), F1(i-1)
F2(i+1), F2(i), F2(i-1) = F1(i)+F3(i-2), F2(i), F2(i-1)
F3(i+1), F3(i), F3(i-1) = F1(i)+F2(i-1), F3(i), F3(i-1)

This gives you a way to construct Fn(i+1), Fn(i), Fn(i-1) from Fn(i), Fn(i-1), Fn(i-2) in the same way that the usual linear-time Fibonacci algorithm works (constructing Fib(n+1), Fib(n) from Fib(n), Fib(n-1)). These recurrence relations are encoded in the line that updates the variables a to i.

How to find out the number of possible ways of adding 1 2 and 3 to given sum avoiding repetition?

Repeat the question

My restriction

2 Answers2