How to calculate permutations in linear time, with a twist

Question

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.

Using the compatibility matrix below, here are a few examples of allowed strings
Length of 1: 0, 1, 2, 3, 4
Length of 2: 02, 03, 14, 20, 30, 41
Length of 3: 020, 030, 141, 202, 203, 302, 303, 414

     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

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.

Any thoughts on a better way to count the permutations other than trying to enumerate all of them?

Answer 1

If you just want the number of strings of a certain length, you could just multiply the compatibility matrix with itself a few times, and sum it's values.

n = length of string
A = compatibility matrix
number of possible strings = sum of A^n-1

A few examples:

n = 1
| 1 0 0 0 0 |
| 0 1 0 0 0 |
| 0 0 1 0 0 |
| 0 0 0 1 0 |
| 0 0 0 0 1 |
sum: 5

n = 3
| 2 0 0 0 0 |
| 0 1 0 0 0 |
| 0 0 1 1 0 |
| 0 0 1 1 0 |
| 0 0 0 0 1 |
sum: 8

n = 8
| 0 0 8 8 0 |
| 0 0 0 0 1 |
| 8 0 0 0 0 |
| 8 0 0 0 0 |
| 0 1 0 0 0 |
sum: 34

The original matrix (row i, column j) could be thought of as the number of strings that start with symbol i, and whose next symbol is symbol j. Alternatively, you could see it as number of strings of length 2, which start with symbol i and ends with symbol j.

Matrix multiplication preserves this invariant, so after exponentiation, A^n-1 would contain the number of strings that start with symbol i, has length n, and ends in symbol j.

See Wikipedia: Exponentiation by squaring for an algorithm for faster calculation of matrix powers.

(Thanks stefan.ciobaca)

This specific case reduces to the formula:

number of possible strings = f(n) = 4 + Σ_k=1..n 2^{⌊k-1⁄₂⌋} = f(n-1) + 2^{⌊n-1⁄₂⌋}

n       f(n)
----    ----
   1       5
   2       6
   3       8
   4      10
   5      14
   6      18
   7      26
   8      34
   9      50
  10      66

Answer 2

Do you just want to know how many strings of a given length you can build with the rules in the given matrix? If so, that an approach like this should work:

n = 5
maxlen = 100

combine = [
      [0, 0, 1, 1, 0],
      [0, 0, 0, 0, 1],
      [1, 0, 0, 0, 0],
      [1, 0, 0, 0, 0],
      [0, 1, 0, 0, 0]
   ]

# counts of strings starting with 0,1,...,4, initially for strings of length one:
counts = [1, 1, 1, 1, 1]

for size in range(2, maxlen+1):
   # calculate counts for size from count for (size-1)
   newcount = []
   for next in range(n):
      total = 0
      for head in range(n):
         if combine[next][head]:
            # |next| can be before |head|, so add the counts for |head|
            total += counts[head]
      # append, so that newcount[next] == total
      newcount.append(total)
   counts = newcount
   print "length %i: %i items" % (size, sum(counts))

Answer 3

Your algorithm seems to be optimal.

How are you using these permutations? Are you accumulating them in one list, or using it one by one? Since there are a huge number of such permutations, so the poor performance maybe due to large memory usage (if you are collecting all of them) or it just takes so much time. You just can't do billions of loops in trivial time.

Reply to comment:

If you just want to count them, then you can using dynamic programming:

Let count[n][m] be an array, where count[l][j] is the number of such permutations whose length is l and end with j,

then count[l][i] = count[l-1][i1]+count[l-1][i2]+..., where i1, i2, ... are the digits that can precede i (this can be saved in an pre-calculated array).

Every cell of count can be filled by summing K numbers (K depends on the compatible matrix), so the complexity is O(KMN), M is the length of the permutation, and N is the total number of digits.

Answer 4

Maybe I don't understand this, but wouldn't this be served by having a table of lists that for each digit has a list of valid digits that could follow it.

Then your routine to generate will take an accumulated result, the digit number, and the current digit. Something like:

// not really Java - and you probably don't want chars, but you'll fix it
void GenerateDigits(char[] result, int currIndex, char currDigit)
{
    if (currIndex == kMaxIndex) {
        NotifyComplete(result);
        return;
    }
    char[] validFollows = GetValidFollows(currDigit); // table lookup
    foreach (char c in validFollows) {
        result[currIndex] = c;
        GenerateDigits(result, currIndex+1, c);
    }
}

The complexity increases as a function of the number of digits to generate, but that function depends on the total number of valid follows for any one digit. If the total number of follows is the same for every digit, let's say, k, then the time to generate all possible permutations is going to be O(k^n) where n is the number of digits. Sorry, I can't change math. The time to generate n digits in base 10 is 10^n.

Answer 5

I'm not exactly sure what you're asking, but since there are potentially n! permutations of a string of n digits, you're not going to be able to list them faster than n!. I'm not exactly sure how you think you got a runtime of O(n^2).