## Sunday, July 30, 2017

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.

### 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.
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.
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"));
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