7

我在 Java 中有一个资源调度问题，需要对事物进行排序，但是对于哪些资源可以彼此相邻存在限制。一个很好的类比是一串“数字”，其中只有某些数字可以彼此相邻。我的解决方案是递归的，适用于小字符串，但运行时间为 O(X^N)，其中 X 是可能的位数（基数），N 是字符串的长度。它很快变得无法管理。

使用下面的兼容性矩阵，这里有一些允许字符串的示例
长度为 1：0、1、2、3、4
长度为 2：02、03、14、20、30、41
长度为 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

我计算所有长度为 N 的字符串的解决方案是从一个空字符串开始，置换第一个数字，然后递归调用所有长度为 N-1 的字符串。递归调用检查添加的最后一个数字并尝试该数字旁边的所有排列。进行了一些优化，因此我不会每次都尝试置换 00、01、04，例如 - 只有 02、03，但性能仍然很差，因为它从基数 5（示例）扩展到基数 4000。

除了尝试枚举所有排列之外，还有什么更好的方法来计算排列吗？

4

5 回答 5

19

如果您只想要一定长度的字符串的数量，您可以将兼容性矩阵与自身相乘几次，然后将其值相加。

n =字符串长度
A =兼容性矩阵
可能字符串的数量= A n -1的总和

几个例子：

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

原始矩阵（第i行，第j列）可以被认为是以符号i开头的字符串的数量，其下一个符号是符号j。或者，您可以将其视为长度为2的字符串数，以符号i开头并以符号j结尾。

矩阵乘法保留了这个不变量，因此在求幂之后，A n -1将包含以符号i开头、长度为n并以符号j结尾的字符串的数量。

参见Wikipedia: Exponentiation by squareing以了解更快计算矩阵幂的算法。

（感谢 stefan.ciobaca）

这种特殊情况简化为公式：

可能的字符串数= f ( n ) = 4 + Σ k =1.. n 2 ⌊ k -1 ⁄ 2 ⌋ = f ( n -1) + 2 ⌊ n -1 ⁄ 2 ⌋

n       f(n)
----    ----
   1       5
   2       6
   3       8
   4      10
   5      14
   6      18
   7      26
   8      34
   9      50
  10      66
于 2009-01-27T16:35:42.560 回答
3

您是否只想知道使用给定矩阵中的规则可以构建多少个给定长度的字符串？如果是这样，那么这样的方法应该有效：

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))
于 2009-01-27T16:05:48.783 回答
2

您的算法似乎是最佳的。

你是如何使用这些排列的？您是将它们累积在一个列表中，还是一个一个地使用它？由于存在大量此类排列，因此性能不佳可能是由于内存使用量大（如果您正在收集所有这些排列），或者只是花费了太多时间。您无法在微不足道的时间内完成数十亿次循环。

回复评论：

如果您只想计算它们，那么您可以使用动态编程：

令 count[n][m] 是一个数组，其中 count[l][j] 是长度为 l 并以 j 结尾的此类排列的数量，

那么 count[l][i] = count[l-1][i1]+count[l-1][i2]+...，其中 i1, i2, ... 是可以在 i 之前的数字（这可以保存在预先计算的数组中）。

count 的每个单元格都可以通过对 K 个数字求和来填充（K 取决于兼容矩阵），因此复杂度为 O(KMN)，M 是排列的长度，N 是总位数。

于 2009-01-27T16:06:05.100 回答
1

也许我不明白这一点，但如果有一个列表表，对于每个数字都有一个可以跟随它的有效数字列表，这难道不可以吗？

然后，您要生成的例程将采用累积结果、数字编号和当前数字。就像是：

// 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);
    }
}

复杂性随着要生成的位数而增加，但该函数取决于任何一位数的有效跟随总数。如果每个数字的跟随总数相同，例如 k，那么生成所有可能的排列的时间将是 O(k^n)，其中 n 是数字的数量。对不起，我不能改变数学。生成以 10 为底的 n 位数字的时间是 10^n。

于 2009-01-27T15:53:37.013 回答
1

我不确定你在问什么，但因为可能有 n! 一串 n 位数字的排列，您将无法比 n 更快地列出它们！我不确定你认为你是如何获得 O(n^2) 的运行时间的。

于 2009-01-27T16:18:05.623 回答