Generate number - Linkedin

http://wxx5433.github.io/generate-number.html

There is a particular sequence that only uses 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).

Analysis

We can use DFS to find the result. Each time we try to append a number, we check if it is the same as previous number. If it is, then it's invalid.

Complexity

Time: O(4^len), len is the totally lengt

Space: O(len), the length of the path DFS will search.

https://miafish.wordpress.com/2015/03/10/how-many-particular-sequence-without-adjacent/

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).

Solution 1: the easy way to do it would be using recursion and back trace.  if count of 1 is greater than 0 and the string’s end is not 1, try 1 and back trace, so do 2, 3, 4.
- DP + cache? Map: key is string: "n1-n2-n3-n4"

        private int count = 0;
        public int Sequence(int n1, int n2, int n3, int n4)
        {
            this.SequenceRecursion(n1, n2, n3, n4, string.Empty);

            return count;
        }

        private bool SequenceRecursion(int n1, int n2, int n3, int n4, string str)
        {
            if (n1 == 0 && n2 == 0 && n3 == 0 && n4 == 0)
            {
                count++;
                return true;
            }

            if (str.Length == 0 || (str.Length > 0 && n1 > 0 && !str[str.Length - 1].Equals('1')))
            {
                str += "1";
                this.SequenceRecursion(n1 - 1, n2, n3, n4, str);
                str = str.Substring(0, str.Length - 1);
            }

            if (str.Length == 0 || (str.Length > 0 && n2 > 0 && !str[str.Length - 1].Equals('2')))
            {
                str += "2";
                this.SequenceRecursion(n1, n2 - 1, n3, n4, str);
                str = str.Substring(0, str.Length - 1);
            }

            if (str.Length == 0 || (str.Length > 0 && n3 > 0 && !str[str.Length - 1].Equals('3')))
            {
                str += "3";
                this.SequenceRecursion(n1, n2, n3 - 1, n4, str);
                str = str.Substring(0, str.Length - 1);
            }

            if (str.Length == 0 || (str.Length > 0 && n4 > 0 && !str[str.Length - 1].Equals('4')))
            {
                str += "4";
                this.SequenceRecursion(n1, n2, n3, n4 - 1, str);
                str = str.Substring(0, str.Length - 1);
            }

            return false;
        }

Solution 2: if we use 4 dimension arrays to store how many number of particular sequence without adjacent. It would save a lot of time.

dp1[i][j][k][l] : how many number of particular sequence without adjacent end with 1 and has i 1s, j 2s, k 3s, l 4s.

dp2[i][j][k][l] : how many number of particular sequence without adjacent end with 2 and has i 1s, j 2s, k 3s, l 4s.

So dp1[i][j][k][l] = dp2[i – 1][j][k][l] + dp3[i – 1][j][k][l] +dp4[i – 1][j][k][l]; dp1 would be the sum of i – 1 1s end with 2(dp2), 3(dp3), 4(dp4);

        public int Sequence2(int n1, int n2, int n3, int n4)
        {
            var dp1 = new int[n1 + 1, n2 + 1, n3 + 1, n4 + 1];
            var dp2 = new int[n1 + 1, n2 + 1, n3 + 1, n4 + 1];
            var dp3 = new int[n1 + 1, n2 + 1, n3 + 1, n4 + 1];
            var dp4 = new int[n1 + 1, n2 + 1, n3 + 1, n4 + 1];

            const int MOD = 1000000007;
            dp1[1, 0, 0, 0] = 1;
            dp2[0, 1, 0, 0] = 1;
            dp3[0, 0, 1, 0] = 1;
            dp4[0, 0, 0, 1] = 1;

            for (int i = 0; i <= n1; i++)
            {
                for (int j = 0; j <= n2; j++)
                {
                    for (int k = 0; k <= n3; k++)
                    {
                        for (int l = 0; l <= n4; l++)                                        {                             
                            if (i + j + k + l > 1)
                            {
                                if (i > 0) dp1[i, j, k, l] = dp2[i - 1, j, k, l] + dp3[i - 1, j, k, l] + dp4[i - 1, j, k, l] % MOD;
                                if (j > 0) dp2[i, j, k, l] = dp1[i, j - 1, k, l] + dp3[i, j - 1, k, l] + dp4[i, j - 1, k, l] % MOD;
                                if (k > 0) dp3[i, j, k, l] = dp2[i, j, k - 1, l] + dp1[i, j, k - 1, l] + dp4[i, j, k - 1, l] % MOD;
                                if (l > 0) dp4[i, j, k, l] = dp2[i, j, k, l - 1] + dp3[i, j, k, l - 1] + dp1[i, j, k, l - 1] % MOD;
                            }
                        }
                    }

                }
            }
            return dp1[n1, n2, n3, n4] + dp2[n1, n2, n3, n4] + dp3[n1, n2, n3, n4] + dp4[n1, n2, n3, n4] % MOD;
        }

public static void generateNumber(List<Integer> result, String number, int[] count, int len) {
    if (number.length() == len) {
        BigInteger num = new BigInteger(number).mod(new BigInteger("1000000007"));
        result.add(new Integer(num.toString()));
        return ;
    }

    for (int i = 0; i < 4; ++i) {
        int num = i + 1;
        if (count[i] > 0 && (number.length() == 0 
                || number.charAt(number.length() - 1) - '0' != num)) {
            --count[i];
            generateNumber(result, number + num, count, len);
            ++count[i];
        }
    }
}

https://www.careercup.com/question?id=5653460783464448