0

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
1

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], [1,2], [2,1]
f({'1': 1, '2': 2}) // -> 5: [1], [2], [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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.