シーケンスを等間隔で衝突しないサブシーケンスで分割するためのアルゴリズム

StackOverflow https://stackoverflow.com/questions/1526281

質問

アルゴリズムを解決することはできないというこの問題が発生しました。

常に固定レートFでビデオフレームをキャプチャするビデオキャプチャがあるとしましょう（たとえば、1秒あたり30フレームなど）。

私が望んでいるのは、このフレームシーケンスをn（たとえば4つの）サブシーケンスで「分割」することです。各サブシーケンスにはフレームレートFNがあり、それは明らかに<F.サブシーケンスのフレームが時間内に等しく間隔を置いているため、たとえば、F = 30 fpsと時間= 1秒で、いくつかの有効な10 fpsシーケンスF1がそれのように重要になります。

（0Sは、サブシーケンスに依存しないフレームであり、1Sはそれを行うフレームです）：

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フレームがかかります。

問題は、サブシーケンスが衝突できないため、f = 30、f1 = 10 fps（3つのフレームごと）およびf2 = 5 fps（6つのフレームごとに）の場合、このシーケンスは問題ありません。

102100 (again, in a second: 102100102100102100102100102100)

ただし、F3 = 6 fpsを追加する場合

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

また

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

3番目のサブシーケンスは、最初のサブシーケンスと衝突します。

質問は：

  • 見つける方法はありますか 毎日 nのフレームレートの組み合わせ（n <= 4）サブシーケンスは衝突せず、等しく間隔を空けますか？

（一般的なケースが必要ですが、この特定のケースでは、1つのシーケンスのみ（些細な）のすべての有効な組み合わせ、2つのシーケンスのすべての有効な組み合わせ、3つのシーケンスのすべての有効な組み合わせ、および4つのシーケンスのすべてが必要です） 。

誰かが私の心を啓発できることを願っています。ありがとうございました！

役に立ちましたか？

解決

あなたがあなたの料金を見ているなら、あなたは次のように述べるつもりです：

  • n（integers> = 0）にはkがあります。
  • nにはf1 = k * f3がありません

さらに、F1とF2は、F2が同じポイントで開始するもののサブシーケンスを提供するという点で特別です。次に、2つのF1シーケンスが同じポイントで開始しない場合（並行してください）、決して交差しないため、自然にF2もF1を横切ることはありません！

また、F3はF1のサブシーケンスではないため、反対が当てはまることがわかります（すなわち、F3はF1の除数ではありません）。F1 + jf3 = 1ですが、これがどの定理から来たのか思い出せません。これは、両方のサブシーケンスが始まる位置が何であれ、実際に衝突を見つけることができることを意味します。

Alosは、F1 = 29とF3 = 27で逃げることができることを意味しますが、数フレームしか持っていない場合はF1 = 29およびF3 = 27ですが、最終的には十分に長く進んでいれば衝突します（予測して計算しないことは現時点では私を超えています） 。

要するに、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未満の場合、競合しない配置を見つけることができません。 （たとえば、2つの素数の場合を考慮してください。GCD（P1、P2）は常に1であり、それらをオフセットする方法に関係なく<= P1*P2フレームで常に矛盾します）

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top