algorithm - 一种将序列拆分为等距、非冲突子序列的算法

Question

我遇到了无法仅通过算法解决的问题。

假设我有一个始终以固定速率 F(假设每秒 30 帧)捕获视频帧的视频捕获。

我想要的是将这个帧序列“拆分”为 n(比如四个)子序列。每个子序列都有其帧速率 fn，这显然 < F。子序列中的帧在时间上是等间隔的，因此例如一些有效的 10 fps 序列 f1 将像 F = 30 fps 和时间 = 1 秒那样构造:

(0 是不属于子序列的帧，1 是属于子序列的帧):

100 (in 1 second it will repeated like: 100100100100100100100100100100)

或

010 (again, in 1 sec it will go like: 010010010010010010010010010010)

或者，对于 F = 30 和 f = 8:

100000001

(在一秒以“1”重新开始之前需要 MCD (30,8) = 120 帧)。

问题是子序列不能冲突，所以如果 F=30，f1 = 10 fps(每三帧)和 f2 = 5 fps(每六帧)，这个序列是可以的:

102100 (again, in a second: 102100102100102100102100102100)

但是如果我们加上 f3 = 6 fps

132100 (1 AND 3) <--- collides! 02100102100102100102100

或

102103102130102 (1 AND 3) <--- collides! 00102100102100

第三个子序列将与第一个相撞。

问题是:

• 有没有一种方法可以找到 n 个(n <= 4)个子序列的每个帧率组合，这些子序列不会发生碰撞并且间隔相等？

(我需要一般情况，但在这种特殊情况下，我只需要一个序列的所有有效组合(微不足道)，两个序列的所有有效组合，三个序列的所有有效组合，以及所有四个序列)。

希望有人能开导我。谢谢!

Answer 1

我相信这对于 4 流的情况会起作用，对于较少的流情况应该做什么应该是显而易见的。

for a in range(1,31):
    for b in range(a,31):
        for c in range(b,31):
            for d in range(c,31):
                if (1.0/a+1.0/b+1.0/c+1.0/d)<=1.0 and gcd(a,b,c,d)>=4:
                    print a,b,c,d

基本上，无论您考虑的是什么频率，1) 它们所占用的频率都不会超过整个流 2) 如果它们的最大公分母小于 4，您就无法找到它们的排列方式冲突。 (例如，考虑两个素数的情况；gcd(p1,p2) 始终为 1，并且无论您如何偏移它们，它们在 <=p1*p2 帧中总是会发生冲突)