Алгоритм расщепления последовательности на равные, не сталкивающиеся подпоследовательности

Question

У меня есть проблема, которую я не могу просто решить алгоритмически.

Допустим, у меня есть видео захват, который всегда захватывает видеокадры с фиксированной скоростью F (скажем, 30 кадров в секунду).

Что я хочу, так это «разбить» эту последовательность кадров на n (скажем, четыре) подпоследовательности. Каждая подпоследовательность имеет частоту кадров fn, то есть, очевидно,

(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

(и потребуется MCD (30,8) = 120 кадров, прежде чем секунда перезапустится с "1").

Проблема в том, что подпоследовательности не могут конфликтовать, поэтому если F = 30, f1 = 10 кадров в секунду (каждые три кадра) и f2 = 5 кадров в секунду (каждые шесть кадров), эта последовательность в порядке:

102100 (again, in a second: 102100102100102100102100102100)

Но если мы добавим f3 = 6 кадров в секунду

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

или

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

Третья подпоследовательность столкнется с первой.

Вопрос:

• Есть ли способ найти каждую комбинацию частоты кадров n (с n <= 4) подпоследовательностей, которая не будет сталкиваться и будет иметь одинаковое расстояние? </li>

(мне нужен общий случай, но в этом конкретном случае мне потребуются все действительные комбинации только для одной последовательности (тривиальные), все действительные комбинации для двух последовательностей, все действительные комбинации трех последовательностей и все для четыре последовательности).

Надеюсь, кто-то мог просветить мой разум. Спасибо!

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 кадрах независимо от того, как вы их смещаете) </p>

Answer 2

Если вы посмотрите на свои ставки, вы заметите, что:

• Существует N в N (целые числа> = 0), такие что f1 = k * f2
• Нет такого числа в N, что f1 = k * f3

Более того, f1 и f2 являются специальными в том смысле, что f2 дает вам последовательность того, что f1 даст, начиная с той же точки. Тогда, поскольку две последовательности f1 никогда не пересекутся, если они не начнутся в одной и той же точке (думайте параллельно), то естественно, что f2 также не пересечет f1!

Вы также можете видеть, что верно обратное, поскольку f3 не является подпоследовательностью f1 (т. Е. F3 не является делителем f1), то существуют i, j в Z (целые числа), такие что i f1 + j f3 = 1, хотя я не могу вспомнить, из какой это теоремы. Это означает, что я действительно могу найти столкновение независимо от того, с какой позиции начинаются обе подпоследовательности.

Это также означает, что вы могли бы обойтись без f1 ​​= 29 и f3 = 27, если бы у вас было всего несколько кадров, но в конечном итоге они будут сталкиваться, если вы будете продолжать работать достаточно долго (хотя прогнозировать и не вычислять это не по мне в момент).

---

Короче говоря: выберите одну «ведущую» частоту (самую быструю из всех тех, которые вам нужны), а затем подберите только делители этой частоты, и вы будете в порядке независимо от длины вашего видео.