我在 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。
除了尝试枚举所有排列之外,还有什么更好的方法来计算排列吗?