Un algoritmo per suddividere una sequenza in equidistanti, sottosequenze non urtano

Question

Ho questo problema che non posso risolvere algoritmicamente.

Diciamo che ho una cattura video in grado di catturare fotogrammi video sempre a tasso fisso F (diciamo 30 fotogrammi al secondo).

Quello che voglio è quello di "split" questa sequenza di frame n (diciamo quattro) sottosequenze. Ogni sottosequenza ha il suo fn framerate, che è ovviamente

(0s sono fotogrammi che non belogn alla sottosequenza, 1s sono cornici che fanno):

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

o

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

o, per F = 30 e f = 8:

100000001

(e ci sarebbero voluti MCD (30,8) = 120 fotogrammi prima di una seconda riparte con un "1").

Il problema è che sottosuccessioni non possono entrare in collisione, quindi se F = 30, f1 = 10 fps (ogni tre fotogrammi) e F2 = 5 fps (ogni sei fotogrammi), questa sequenza è ok:

102100 (again, in a second: 102100102100102100102100102100)

Ma se aggiungiamo F3 = 6 fps

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

o

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

Il terzo sottosequenza sarebbe entrare in collisione con il primo.

La domanda è:

• C'è un modo per trovare tutti combinazione di framerate del n (con n <= 4) sottosequenze che non si scontrano e si sarebbe distanziati ugualmente?

(devo caso generale, ma in questo caso particolare, avrei bisogno tutte le combinazioni valide per una sola sequenza (banale), tutte le combinazioni valide per due sequenze, tutte le combinazioni valide di tre sequenze, e tutto per quattro sequenze).

La speranza che qualcuno potesse illuminare la mia mente. Grazie!

Answer 1

Se si dispone di uno sguardo a voi tariffe, che si sta per notare che:

• C'è k in N (interi> = 0) tale che f1 = k * f2
• Non v'è alcun k in N tale che f1 = k * f3

Più precisamente, F1 e F2 sono offerte speciali in che f2 ti dà una sottosequenza di ciò che f1 darebbe a partire dallo stesso punto. Quindi dal momento che due sequenze f1 non avrebbero mai attraversare se non iniziano nello stesso punto (si pensi in parallelo), poi naturalmente f2 non sta per attraversare f1 sia!

Si può anche vedere che al contrario detiene, dal momento F3 non è una successione di f1 (vale a dire, f3 non è un divisore di f1), poi esistono i, j in Z (interi) in modo tale che i f1 + j F3 = 1, anche se non ricordo quale teorema questo è da. Questo significa che posso effettivamente trovare una collisione qualunque sia la posizione sia sottosequenze partono da.

Ciò significa alos che si potrebbe ottenere via con f1 = 29 e F3 = 27 se si potesse avuto solo pochi fotogrammi, ma alla fine si scontreranno se andare avanti abbastanza a lungo (anche se la previsione e non di calcolo è al di là di me il momento).

---

In breve: l'elezione di un frequenza 'master' (il più veloce di tutti quelli che si desidera) e poi scegliere solo fino divisori di questa frequenza e sarete a posto qualunque sia la durata del video

.

Answer 2

Credo che questo lo farebbe per il caso 4 torrente, e dovrebbe essere ovvio che cosa fare per i casi meno flusso.

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

In sostanza, qualunque sia le frequenze che si sta valutando, 1) non possono occupare più di tutto il flusso 2) se il loro massimo comune denominatore è <4, non è possibile trovare un accordo di loro che non lo faranno conflitto. (Ad esempio, si consideri il caso di due numeri primi; MCD (p1, p2) è sempre 1, e saranno sempre in conflitto <= p1 * cornici p2 indipendentemente da come li offset)