Um algoritmo para dividir uma sequência em subsequências igualmente espaçadas e não colididas

Question

Eu tive esse problema que não posso simplesmente resolver algoritmicamente.

Digamos que eu tenha uma captura de vídeo que sempre captura quadros de vídeo a uma taxa fixa F (digamos 30 quadros por segundo).

O que eu quero é "dividir" essa sequência de quadros em n (digamos, quatro) subsequências. Cada subseqüência tem seu FRAMREATE FN, obviamente são os quadros <F. em uma subsequência, são igualmente espaçados no tempo; portanto, por exemplo, alguma sequência válida de 10 fps F1 será contratada como a f = 30 fps e tempo = 1 segundo:

(0s são quadros que não belogam para a subsequência, 1s são quadros que fazem):

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

ou

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

ou, para f = 30 e f = 8:

100000001

(e levaria o MCD (30,8) = 120 quadros antes de um segundo reiniciar com um "1").

O problema é que as subsequências não podem colidir; portanto, se F = 30, F1 = 10 fps (a cada três quadros) e F2 = 5 fps (a cada seis quadros), essa sequência está OK:

102100 (again, in a second: 102100102100102100102100102100)

Mas se adicionarmos f3 = 6 fps

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

ou

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

A terceira subsequência colidiria com o primeiro.

A questão é:

• Existe uma maneira de encontrar todo Combinação dos frameratos das subsequências n (com n <= 4) que não colidirão e seriam igualmente espaçadas?

(Eu preciso do caso geral, mas nesse caso em particular, eu precisaria de todas as combinações válidas apenas para uma sequência (trivial), todas as combinações válidas para duas sequências, todas as combinações válidas de três seqüências e todas para quatro sequências) .

Espero que alguém possa esclarecer minha mente. Obrigada!

Answer 1

Se você der uma olhada nas tarifas, você vai comentar que:

• Há k em n (inteiros> = 0) tal que f1 = k * f2
• Não há k em n tal que f1 = k * f3

Além disso, F1 e F2 são especiais, pois F2 oferece uma subsequência do que F1 daria a partir do mesmo ponto. Então, como duas sequências F1 nunca cruzariam se não começarem no mesmo ponto (pense em paralelo), naturalmente F2 também não vai atravessar a F1!

Você também pode ver que o contrário, como F3 não é uma subsequência de F1 (ou seja, F3 não é um divisor de F1), então existe i, j em z (números inteiros) que euF1 + jF3 = 1, embora eu não se lembre de qual teorema é isso. Isso significa que eu realmente posso encontrar uma colisão, seja qual for a posição que ambas as subsequências começam.

Isso significa que você pode se safar com F1 = 29 e F3 = 27 se você pudesse ter apenas alguns quadros, mas eles vão colidir se você continuar por tempo suficiente (embora preveja e não esteja computando, está além de mim no momento) .

---

Em resumo: elege uma frequência 'mestre' (a mais rápida de todos aqueles que você deseja) e, em seguida, pegue apenas divisores dessa frequência e você ficará bem, seja qual for o comprimento do seu vídeo.

Answer 2

Acredito que isso faria isso no caso de 4 fluxo, e deve ser óbvio o que fazer para os casos de menor fluxo.

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

Basicamente, quaisquer que sejam as frequências que você está considerando, 1) eles não podem ocupar mais do que todo o fluxo 2) Se o maior denominador comum for <4, você não pode encontrar um arranjo deles que não entre em conflito. (Por exemplo, considere o caso de dois números primos; GCD (P1, P2) é sempre 1, e eles sempre entram em conflito em quadros <= p1*p2, independentemente de como você os compensa)