logo标签列表

如何在线性时间内计算排列，带有一些变化。

algorithmpermutation
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。
除了尝试枚举所有排列之外，对于计算排列有更好的方法吗？
什么决定了元素是否可接受？兼容性矩阵是算法的输入吗？ - Jason S
请澄清一下：您只想计算排列的总数吗？ - Zach Scrivena
矩阵是以前一个函数的结果。上面显示长度为1、2和3的矩阵是我一直用来测试其他算法的。F(1)=5，F(2)=6, F(3)=8。是的 - 只计数，不枚举。 - cmmp
兄弟，你对O(.)符号一无所知。你描述的算法是指数级的O(5^N)，而不是O(N^2)。请看下面提供的一个非常快速的好解决方案：D - user51568
5个回答
19

如果您只想知道特定长度的字符串数量，您可以将兼容矩阵与自身相乘几次，然后计算其值之和。

n = 字符串长度
A = 兼容矩阵
可能的字符串数 = An-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结尾。

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

查看Wikipedia: Exponentiation by squaring中提供的快速计算矩阵幂的算法。

（感谢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
利用兼容矩阵的能力是一个非常干净的想法。但是需要注意的是，该公式仅适用于此情况。 - user49117
非常好的解决方案。为了更快速和更高的信誉，请确保使用http://en.wikipedia.org/wiki/Exponentiation_by_squaring双倍加算法。 - user51568
此外，答案应该提到为什么这是正确的。正确的解释是A^i[x][y]是长度为i且以x开头、以y结尾的“兼容”字符串的数量。显然可以看出为什么乘法保持这种不变性。 - user51568
4
这很酷，但问题不是关于一个受限制的排列集合的大小吗？这并没有强制执行每个数字只能使用一次的限制，这就是我理解“排列”所意味的。哦，等等，“202”是一个例子。那么这只是对问题表述的一种混淆。 - Darius Bacon
1
非常好的解决方案 - 谢谢。我按照建议使其工作，现在正在尝试使用Stefan提到的平方指数法进行优化。 - cmmp
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))
谢谢。我认为这可能有效，但我认为它有与我相同的问题...嵌套循环/递归遍历N个元素。如果我错了，请纠正我。 - cmmp
你缺少了什么。 这是与未知（Yahoo）建议的相同的动态规划算法。 - user51568
它的时间复杂度是O(n^2 * maxlen)，这并不好。根据你的描述，我认为你的算法可能类似于O(n^2 * n^(maxlen-1))，但我不太确定你是如何做到的。我认为上面的矩阵解法可以在O(n^2*log(maxlen))内实现，但这也并没有真正帮助到解决问题... - sth
但是，如果您有一个n * n矩阵，其中包含兼容性信息并且需要查看其中的所有元素，则需要O（n ^ 2）时间才能完成。也许有更好的方法来描述兼容性吗？ - sth
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是总位数。

目前只是简单计算它们 - 没有使用它们。就迭代/递归解决方案而言，我认为我的解决方案还不错，但正如你所说，无法在合理时间内计算4000 ^ 10，因此我正在尝试寻找另一种方法。 - cmmp
1

我不确定你在问什么，但由于n个数字的字符串可能有n!种排列方式，你不可能比n!更快地列出它们。我不确定你是如何得到O(n^2)的运行时间的。

O(K^N)，其中K是不同数字的数量，N是“排列”的长度。 - user51568
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是数字的数量。抱歉，我无法改变数学规律。在十进制中生成n位数字的时间是10^n。

谢谢。您的建议已经被实现为我提到的优化，即只查看可以跟随当前数字的数字。这将运行时间从O(n^2)改进了，但指数级别的规模仍然在处理数千个数字时崩溃。 - cmmp
我认为他并没有提出建议。他只是试图理解你的算法。你过于频繁地使用“线性”、“指数”、“O(N^2)”等词汇，却不理解它们的含义。 - user51568
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接