title: How to calculate permutations in linear time, with a twist
body: <p>I have a resource scheduling issue in Java where things need to be sequenced, but there are restrictions on what resources can be next to each other.  A good analogy is a string of "digits", where only certain digits can be next to each other.  My solution was recursive, and works fine for small strings, but run time is O(X^N), where X is the number of possible digits (the base), and N is the length of the string.  It quickly becomes unmanageable.</p>
  
  <p>Using the compatibility matrix below, here are a few examples of allowed strings<br>
  Length of 1:  0, 1, 2, 3, 4<br>
  Length of 2:  02, 03, 14, 20, 30, 41<br>
  Length of 3:  020, 030, 141, 202, 203, 302, 303, 414<br></p>
  
  <pre>
       0  1  2  3  4
     ---------------------
  0|  0  0  1  1  0
  1|  0  0  0  0  1
  2|  1  0  0  0  0
  3|  1  0  0  0  0
  4|  0  1  0  0  0
  </pre>
  
  <p>My solution for counting all strings of length N was start with an empty string, permute the first digit, and make a recursive call for all strings of length N-1.  The recursive calls check the last digit that was added and try all permutations that can be next to that digit.  There are some optimizations made so that I don't try and permute 00, 01, 04 every time, for example - only 02, 03, but performance is still poor as it scales from base 5 (the example) to base 4000.</p>
  
  <p>Any thoughts on a better way to count the permutations other than trying to enumerate all of them?</p>