昨日のアルゴリズムのテストでこの質問がありましたが、答えがわかりません。約40ポイントの価値があったので、それは私を完全に夢中にさせています. 過去 24 時間以内に解決策を思いつかなかったので、クラスのほとんどが正しく解決していないと思います。
長さ n の任意のバイナリ文字列が与えられた場合、文字列内に等間隔にある 3 つのバイナリ文字列が存在する場合はそれらを見つけます。これを O(n * log(n)) 時間で解くアルゴリズムを書きなさい。
したがって、これらのような文字列には、「等間隔」の 3 つの文字列があります: 11100000、0100100100
編集：これは乱数なので、どの数値でも機能するはずです。私が挙げた例は、「等間隔」の特性を説明するためのものでした。したがって、1001011 は有効な数値です。1、4、および 7 は等間隔です。
ついに！sdcvvc's answer のリードをフォローアップすると、問題の O(n log n) アルゴリズムが得られます! 理解すればそれも簡単です。FFTを推測した人は正しかった。
S問題:長さnのバイナリー・ストリングが与えられ、その中で 3 つの等間隔の 1 を見つけたいとします。たとえば、n = 9のS場合はです。2、5、および 8 の位置に 1 が等間隔で配置されています。110110010
S左から右にスキャンしL、1 の位置のリストを作成します。S=110110010上の場合、リスト L = [1, 2, 4, 5, 8] があります。このステップは O(n) です。ここでの問題は、長さ 3 の等差数列を で見つけることです。つまり、でba = cb、または同等に a+c=2bLとなる別個の a、b、cを見つけることです。上記の例では、進行 (2、5、8) を見つけたいと考えています。L
各k inに対して項x kをもつ多項式 を作成します。上記の例では、多項式p(x) = (x + x 2 + x 4 + x 5 +x 8 )を作成します。このステップは O(n) です。pL
高速フーリエ変換を使用して、多項式q= p 2を求めます。上記の例では、多項式q(x) = x 16 + 2x 13 + 2x 12 + 3x 10 + 4x 9 + x 8 + 2x 7 + 4x 6 + 2x 5 + x 4 + 2x 3 + x 2を取得します。このステップは O(n log n) です。
あるk inのx 2kに対応する項を除くすべての項を無視します。上記の例では、x 16、 3x 10、 x 8、 x 4、 x 2という用語が得られます。このステップは、実行することを選択した場合、O(n) です。L
ここに重要な点があります: b inの任意のx 2bの係数は、正確にはa+c=2bとなるペア(a,c) inの数です。[CLRS、例。30.1-7] そのようなペアの 1 つは常に ( b,b)です (したがって、係数は少なくとも 1 です)。ただし、他のペア(a,c)が存在する場合、係数は(a,cから) 少なくとも 3 です。)および(c,a)。上記の例では、AP (2,5,8) のため、x 10の係数は正確に 3 になります。(これらの係数x 2bLL上記の理由により、常に奇数になります。また、q の他のすべての係数は常に偶数になります。)
したがって、アルゴリズムは、これらの項x 2bの係数を見て、それらのいずれかが 1 より大きいかどうかを確認することです。何もない場合、等間隔の 1 はありません。x 2bの係数が1 より大きい a b が存在する場合、(b,b) 以外に a+c=2b となるペア( a , c )が存在することがわかります。実際のペアを見つけるには、各a in (対応するcは2b-aになります) を試して、 2b-a inの位置に 1 があるかどうかを確認します。このステップは O(n) です。LLS
以上です。
FFT を使用する必要があるのでしょうか? beta、flybywire、rspなどの多くの回答は、1 の各ペアをチェックし、「3 番目」の位置に 1 があるかどうかを確認するアプローチが、直感に基づいて O(n log n) で機能する可能性があることを示唆しています。 1 が多すぎるとトリプルを簡単に見つけることができ、1 が少なすぎると、すべてのペアをチェックするのにほとんど時間がかかりません。残念ながら、この直感は正しく、単純なアプローチはO(n 2 ) よりも優れていますが、大幅に優れているわけではありません。sdcvvc's answerのように、長さn=3 kの文字列の「Cantor のようなセット」を取ることができます、3 進表現に 0 と 2 しかない (1 がない) 位置に 1 があります。このような文字列には2 k = n (log 2)/(log 3) ≈ n 0.63の 1 があり、等間隔の 1 がないため、すべてのペアをチェックすると、その中の 1 の数の 2 乗のオーダーになります。4 k ≈ n 1.26残念ながら、漸近的に (n log n) よりもはるかに大きくなります。実際、最悪のケースはさらに悪い: 1953 年に Leo Moser は、n 個の 1-c/√(log n) 1 を含む文字列を (事実上)構築しましたが、等間隔の 1 はありません。つまり、そのような文字列では、単純なアプローチにはΘ(n 2-2c/√(log n) )が必要です—驚くべきことに、Θ (n 2 )よりもわずかに優れています!
長さ n の文字列内の 1 の最大数について、3 つの等間隔の 1 はありません (上記で見たのは、簡単なカントールのような構成から少なくともn 0.63であり、少なくともn 1-c/√(log n)であり、 Moser の構造) — これはOEIS A003002です。A065825(k) ≤ n < A065825(k+1) となる k として、OEIS A065825から直接計算することもできます。これらを見つけるプログラムを書きましたが、貪欲なアルゴリズムではそのような最長の文字列が得られないことがわかりました。たとえば、n = 9 の場合、5 つの 1 (110100011) を得ることができますが、欲張りは 4 (110110000) しか与えません。=26 we can get 11 1s (11001010001000010110001101) but the greedy gives only 8 (11011000011011000000000000), and for n =74 we can get 22 1s (11000010110001000001011010001000000000000000010001011010000010001101000011) but the greedy gives only 16 (11011000011011000000000000011011000011011000000000000000000000000000000000). ただし、50 までかなりの数の場所で一致します (たとえば、38 から 50 のすべて)。OEIS の参考文献にあるように、Jaroslaw Wroblewski はこの問題に関心を持っているようで、これらの非平均集合に関する Web サイトを維持しています。正確な数は 194 までしかわかっていません。
これは解決策ではありませんが、Olexiy が考えていたことと同様の考え方です
最大数の 1 でシーケンスを作成して遊んでいましたが、それらはすべて非常に興味深いものでした。最大 125 桁になりました。これは、できるだけ多くの「1」ビットを挿入しようとして見つかった最初の 3 つの数字です。
それらはすべてフラクタルであることに注意してください(制約を考えるとそれほど驚くことではありません)。逆に考えると何かがあるかもしれません。文字列が特徴のあるフラクタルでない場合、繰り返しパターンがあるに違いないのでしょうか?
これらの数値を表すより適切な用語を提供してくれた beta に感謝します。
更新: 残念ながら、10000000000001 のような十分に大きな初期文字列で開始すると、パターンが壊れているように見えます。
100000000000011
10000000000001101
100000000000011011
10000000000001101100001
100000000000011011000011
10000000000001101100001101
100000000000011011000011010000000001
100000000000011011000011010000000001001
1000000000000110110000110100000000010011
1000000000000110110000110100000000010011001
10000000000001101100001101000000000100110010000000001
10000000000001101100001101000000000100110010000000001000001
1000000000000110110000110100000000010011001000000000100000100000000000001
10000000000001101100001101000000000100110010000000001000001000000000000011
1000000000000110110000110100000000010011001000000000100000100000000000001101
100000000000011011000011010000000001001100100000000010000010000000000000110100001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001
1000000000000110110000110100000000010011001000000000100000100000000000001101000010010000010000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001
1000000000000110110000110100000000010011001000000000100000100000000000001101000010010000010000001100010000000010000000000000000000000000000000000000000100000010000000000000011
1000000000000110110000110100000000010011001000000000100000100000000000001101000010010000010000001100010000000010000000000000000000000000000000000000000100000010000000000000011000000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000011
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000011000001
1000000000000110110000110100000000010011001000000000100000100000000000001101000010010000010000001100010000000010000000000000000000000000000000000000000100000010000000000000011000000001100100000000100100000000000010000000010000100000100100010010000010000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000110000010000000000000000000001
1000000000000110110000110100000000010011001000000000100000100000000000001101000010010000010000001100010000000010000000000000000000000000000000000000000100000010000000000000011000000001100100000000100100000000000010000000010000100000100100010010000010000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000110000010000000000000000000001001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000001100000100000000000000000000010010000000000000000000000000000000000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000011000001000000000000000000000100100000000000000000000000000000000000011
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000011000001000000000000000000000100100000000000000000000000000000000000011001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000001100000100000000000000000000010010000000000000000000000000000000000001100100000000000000000000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000001100000100000000000000000000010010000000000000000000000000000000000001100100000000000000000000001001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000001100000100000000000000000000010010000000000000000000000000000000000001100100000000000000000000001001000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000011000001000000000000000000000100100000000000000000000000000000000000011001000000000000000000000010010000010000001
1000000000000110110000110100000000010011001000000000100000100000000000001101000010010000010000001100010000000010000000000000000000000000000000000000000100000010000000000000011000000001100100000000100100000000000010000000010000100000100100010010000010000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000110000010000000000000000000001001000000000000000000000000000000000000110010000000000000000000000100100000100000011
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000001100000100000000000000000000010010000000000000000000000000000000000001100100000000000000000000001001000001000000110000000000001
O(n^2) のように見える単純なアプローチは、実際には O(n ln(n)) のようなより良い結果をもたらすと思います。テストに最も時間がかかるシーケンス (任意の n について) は、トリオを含まないシーケンスであり、シーケンスに含まれる 1 の数に厳しい制限が課せられます。
手を振っている議論をいくつか思いつきましたが、きちんとした証拠を見つけることができませんでした。私は暗闇の中で刺すつもりです.答えは、教授が長い間知っていた非常に賢いアイデアであり、それは明白に見えるようになりましたが、学生にとっては難しすぎます. （それか、あなたがそれをカバーした講義を通して眠りました。）
改訂：2009-10-17 23:00
私はこれを多数（たとえば、2,000万の文字列）で実行しましたが、このアルゴリズムはO（n logn）ではないと今では信じています。それにもかかわらず、それは十分にクールな実装であり、それを本当に高速に実行するための多くの最適化が含まれています。25秒以内に24桁以下のバイナリ文字列のすべての配置を評価します。
0 <= L < M < U <= X-1今日の初めからの観察を含むようにコードを更新しました。
オリジナル
これは、概念的には、私が答えた別の質問に似ています。そのコードはまた、一連の3つの値を調べ、トリプレットが条件を満たすかどうかを判断しました。これを応用したC＃コードは次のとおりです。
using System;
using System.Collections.Generic;
namespace StackOverflow1560523
{
class Program
{
public struct Pair<T>
{
public T Low, High;
}
static bool FindCandidate(int candidate,
List<int> arr,
List<int> pool,
Pair<int> pair,
ref int iterations)
{
int lower = pair.Low, upper = pair.High;
while ((lower >= 0) && (upper < pool.Count))
{
int lowRange = candidate - arr[pool[lower]];
int highRange = arr[pool[upper]] - candidate;
iterations++;
if (lowRange < highRange)
lower -= 1;
else if (lowRange > highRange)
upper += 1;
else
return true;
}
return false;
}
static List<int> BuildOnesArray(string s)
{
List<int> arr = new List<int>();
for (int i = 0; i < s.Length; i++)
if (s[i] == '1')
arr.Add(i);
return arr;
}
static void BuildIndexes(List<int> arr,
ref List<int> even, ref List<int> odd,
ref List<Pair<int>> evenIndex, ref List<Pair<int>> oddIndex)
{
for (int i = 0; i < arr.Count; i++)
{
bool isEven = (arr[i] & 1) == 0;
if (isEven)
{
evenIndex.Add(new Pair<int> {Low=even.Count-1, High=even.Count+1});
oddIndex.Add(new Pair<int> {Low=odd.Count-1, High=odd.Count});
even.Add(i);
}
else
{
oddIndex.Add(new Pair<int> {Low=odd.Count-1, High=odd.Count+1});
evenIndex.Add(new Pair<int> {Low=even.Count-1, High=even.Count});
odd.Add(i);
}
}
}
static int FindSpacedOnes(string s)
{
// List of indexes of 1s in the string
List<int> arr = BuildOnesArray(s);
//if (s.Length < 3)
// return 0;
// List of indexes to odd indexes in arr
List<int> odd = new List<int>(), even = new List<int>();
// evenIndex has indexes into arr to bracket even numbers
// oddIndex has indexes into arr to bracket odd numbers
List<Pair<int>> evenIndex = new List<Pair<int>>(),
oddIndex = new List<Pair<int>>();
BuildIndexes(arr,
ref even, ref odd,
ref evenIndex, ref oddIndex);
int iterations = 0;
for (int i = 1; i < arr.Count-1; i++)
{
int target = arr[i];
bool found = FindCandidate(target, arr, odd, oddIndex[i], ref iterations) ||
FindCandidate(target, arr, even, evenIndex[i], ref iterations);
if (found)
return iterations;
}
return iterations;
}
static IEnumerable<string> PowerSet(int n)
{
for (long i = (1L << (n-1)); i < (1L << n); i++)
{
yield return Convert.ToString(i, 2).PadLeft(n, '0');
}
}
static void Main(string[] args)
{
for (int i = 5; i < 64; i++)
{
int c = 0;
string hardest_string = "";
foreach (string s in PowerSet(i))
{
int cost = find_spaced_ones(s);
if (cost > c)
{
hardest_string = s;
c = cost;
Console.Write("{0} {1} {2}\r", i, c, hardest_string);
}
}
Console.WriteLine("{0} {1} {2}", i, c, hardest_string);
}
}
}
}
主な違いは次のとおりです。
一般的な考え方は、データの生の表現ではなく、インデックスで作業することです。1が現れる配列を計算すると、データの長さに比例する時間ではなく、データ内の1の数に比例する時間でアルゴリズムを実行できます。これは標準的な変換です。問題を同等に保ちながら、より高速な操作を可能にするデータ構造を作成します。
結果は古くなっています：削除されました。
編集：2009-10-16 18:48
計算するハードデータの代表として他の応答である程度の信頼を与えられているyxのデータで、私はこれらの結果を取得します...私はこれらを削除しました。それらは古くなっています。
このデータは私のアルゴリズムにとって最も難しいものではないことを指摘しておきます。そのため、yxのフラクタルを解くのが最も難しいという仮定は間違っていると思います。特定のアルゴリズムの最悪のケースは、アルゴリズム自体に依存し、異なるアルゴリズム間で一貫していない可能性が高いと思います。
編集：2009-10-17 13:30
これに関するさらなる観察。
まず、0と1の文字列を、1の位置ごとにインデックスの配列に変換します。その配列Aの長さをXとすると、目標は次のようになります。
0 <= L < M < U <= X-1
そのような
A[M] - A[L] = A[U] - A[M]
また
2*A[M] = A[L] + A[U]
A[L]とA[U]の合計は偶数であるため、（偶数、奇数）または（奇数、偶数）にすることはできません。一致の検索は、A []を奇数と偶数のプールに分割し、奇数と偶数の候補のプールでA[M]の一致を順番に検索することで改善できます。
ただし、これはアルゴリズムの改善というよりもパフォーマンスの最適化であると思います。比較の数は減るはずですが、アルゴリズムの順序は同じである必要があります。
2009-10-1800:45を編集
候補を偶数と奇数に分けるのと同じように、さらに別の最適化が私に起こります。3つのインデックスは3の倍数に追加する必要があるため（a、a + x、a + 2x-mod 3は0であり、aとxに関係なく）、L、M、およびUをそれらのmod3値に分離できます。 ：
M L U
0 0 0
1 2
2 1
1 0 2
1 1
2 0
2 0 1
1 0
2 2
実際、これを偶数/奇数の観測と組み合わせて、それらをmod6の値に分離することができます。
M L U
0 0 0
1 5
2 4
3 3
4 2
5 1
等々。これにより、パフォーマンスがさらに最適化されますが、アルゴリズムによる高速化は行われません。
まだ解決策を思い付くことができませんでした:(、しかしいくつかのアイデアがあります。
逆の問題から始めた場合はどうなりますか。最大数が1で、等間隔のトリオを使用せずにシーケンスを作成します。1の最大数がo（n）であることを証明できる場合は、1のリストのみを反復処理することで推定を改善できます。
これは役立つかもしれません....
この問題は次のようになります。
正の整数のシーケンスが与えられた場合、サブシーケンスのプレフィックスの合計がサブシーケンスのサフィックスの合計と等しくなるように、プレフィックスとサフィックスに分割された連続したサブシーケンスを見つけます。
たとえば、 のシーケンスが与えられた場合、接頭辞 の接頭辞の合計と接尾辞の合計 の接尾辞 を持つ[ 3, 5, 1, 3, 6, 5, 2, 2, 3, 5, 6, 4 ]の部分列が見つかります。[ 3, 6, 5, 2, 2][ 3, 6 ]9[ 5, 2, 2 ]9
削減額は次のとおりです。
0 と 1 のシーケンスが与えられ、左端のものから開始して、右に移動し続けます。別のものに遭遇するたびに、前のものに遭遇してからの移動数を記録し、その数を結果のシーケンスに追加します。
たとえば、 のシーケンスが与えられた場合、[ 0, 1, 1, 0, 0, 1, 0, 0, 0, 1 0 ]のリダクションが見つかります[ 1, 3, 4]。この削減から、 の連続した部分列[ 1, 3, 4]、 の接頭辞[ 1, 3]with sum of 4、接尾辞with with [ 4 ]sum of を計算し4ます。
この削減は で計算できますO(n)。
残念ながら、ここからどこへ行くべきかわかりません。
私は分割統治法がうまくいくかもしれないと考えました。
まず、前処理では、入力サイズの半分（ n / 3）未満のすべての数値をリストに挿入する必要があります。
与えられた文字列:(0000010101000100この特定の例は有効であることに注意してください）
1から（16/2）までのすべての素数（および1）をリストに挿入します：{1、2、3、4、5、6、7}
次に、それを半分に分割します。
100000101 01000100
サイズ1の文字列に到達するまで、これを続けます。すべてのサイズ1の文字列で、1が含まれている場合は、文字列のインデックスを可能性のリストに追加します。それ以外の場合は、失敗の場合は-1を返します。
また、各開始インデックスに関連付けられた、まだ可能な間隔距離のリストを返す必要があります。（上記で作成したリストから始めて、数字を削除していきます）ここで、空のリストは、1つだけを扱っていることを意味するため、この時点で任意の間隔を使用できます。それ以外の場合、リストには除外する必要のある間隔が含まれます。
したがって、上記の例を続けます。
1000 0101 0100 0100
10 00 01 01 01 00 01 00
1 0 0 0 0 1 0 1 0 1 0 0 0 1 0 0
最初の結合ステップでは、2つのセットが8つあります。最初に、セットの可能性がありますが、他のゼロが存在するため、1による間隔は不可能であることがわかります。したがって、1による間隔が不可能であるという事実のために、0（インデックスの場合）と{2,3,4,5,7}を返します。2番目の例では、何もないため、-1を返します。3番目では、インデックス5でスペースが削除されていない一致があるため、5、{1,2,3,4,5,7}を返します。4番目のペアでは、7、{1,2,3,4,5,7}を返します。5番目に、9、{1,2,3,4,5,7}を返します。6番目に、-1を返します。7番目に、13、{1,2,3,4,5,7}を返します。8番目に、-1を返します。
再び4つの4つのセットに組み合わせると、次のようになります。
1000：リターン（0、{4,5,6,7}）
0101：リターン（5、{2,3,4,5,6,7}）、（7、{1,2,3,4,5,6 、7}）
0100：リターン（9、{3,4,5,6,7}）
0100：リターン（13、{3,4,5,6,7}）
8つのセットに組み合わせる：
10000101：Return（0、{5,7}）、（5、{2,3,4,5,6,7}）、（7、{1,2,3,4,5,6,7}）
01000100：戻り値（9、{4,7}）、（13、{3,4,5,6,7}）
16のセットに組み合わせる：
10000101 01000100
私たちが進歩するにつれて、私たちはこれまでのところすべての可能性をチェックし続けています。このステップまで、文字列の終わりを超えたものを残しましたが、これですべての可能性を確認できます。
基本的に、最初の1を5と7の間隔でチェックし、それらが1と並んでいないことを確認します。（各チェックは線形時間ではなく一定であることに注意してください）次に、2、3、4、5、6、および7の間隔で2番目のチェック（インデックス5）をチェックします。それは実際に一致します。
ふぅ！これはかなり長いアルゴリズムです。
最後のステップでO（n log n）かどうかは100％わかりませんが、私が知る限り、そこまでのすべては間違いなくO（n log n）です。後でこれに戻り、最後のステップを改善してみます。
編集：ウェルボグのコメントを反映するように私の答えを変更しました。エラーでごめんなさい。後で、もう一度書いたものを解読する時間が少しできたら、擬似コードも書きます。;-)
面白い質問ですが、2 つの '1' の間の実際のパターンが問題ではないことに気付くと、アルゴリズムは次のようになります。
コードでは、JTest のように (このコードは最も効率的に記述されているわけではないことに注意してください。何が起こるかを確認するためにいくつかの println を追加しました。)
import java.util.Random;
import junit.framework.TestCase;
public class AlgorithmTest extends TestCase {
/**
* Constructor for GetNumberTest.
*
* @param name The test's name.
*/
public AlgorithmTest(String name) {
super(name);
}
/**
* @see TestCase#setUp()
*/
protected void setUp() throws Exception {
super.setUp();
}
/**
* @see TestCase#tearDown()
*/
protected void tearDown() throws Exception {
super.tearDown();
}
/**
* Tests the algorithm.
*/
public void testEvenlySpacedOnes() {
assertFalse(isEvenlySpaced(1));
assertFalse(isEvenlySpaced(0x058003));
assertTrue(isEvenlySpaced(0x07001));
assertTrue(isEvenlySpaced(0x01007));
assertTrue(isEvenlySpaced(0x101010));
// some fun tests
Random random = new Random();
isEvenlySpaced(random.nextLong());
isEvenlySpaced(random.nextLong());
isEvenlySpaced(random.nextLong());
}
/**
* @param testBits
*/
private boolean isEvenlySpaced(long testBits) {
String testString = Long.toBinaryString(testBits);
char[] ones = testString.toCharArray();
final char ONE = '1';
for (int n = 0; n < ones.length - 1; n++) {
if (ONE == ones[n]) {
for (int m = n + 1; m < ones.length - m + n; m++) {
if (ONE == ones[m] && ONE == ones[m + m - n]) {
System.out.println(" IS evenly spaced: " + testBits + '=' + testString);
System.out.println(" at: " + n + ", " + m + ", " + (m + m - n));
return true;
}
}
}
}
System.out.println("NOT evenly spaced: " + testBits + '=' + testString);
return false;
}
}
私はこのようなものを思いついた：
def IsSymetric(number):
number = number.strip('0')
if len(number) < 3:
return False
if len(number) % 2 == 0:
return IsSymetric(number[1:]) or IsSymetric(number[0:len(number)-2])
else:
if number[len(number)//2] == '1':
return True
return IsSymetric(number[:(len(number)//2)]) or IsSymetric(number[len(number)//2+1:])
return False
これは andycjw に触発されています。
複雑さに関しては、これは O(nlogn) である可能性があります。これは、各再帰で 2 で除算しているためです。
それが役に立てば幸い。
ここで私の大まかな推測を述べます。複雑さを計算するのが得意な人に、私のアルゴリズムが O 記法でどのように機能するかを教えてもらいましょう。
これの複雑さを計算する方法がわかりません。誰か助けてもらえますか?
編集：私の考えを説明するためにいくつかのコードを追加してください
edit2: コードをコンパイルしようとしたところ、重大なミスがいくつか見つかりました。修正しました
char *binaryStr = "0000010101000100";
int main() {
int head, tail, pos;
head = 0;
tail = strlen(binaryStr)-1;
if( (pos = find3even(head, tail)) >=0 )
printf("found it at position %d\n", pos);
return 0;
}
int find3even(int head, int tail) {
int pos = 0;
if(head >= tail) return -1;
while(binaryStr[head] == '0')
if(head<tail) head++;
while(binaryStr[tail] == '0')
if(head<tail) tail--;
if(head >= tail) return -1;
if( (tail-head)%2 == 0 && //true if odd numbered
(binaryStr[head + (tail-head)/2] == '1') ) {
return head;
}else {
if( (pos = find3even(head, tail-1)) >=0 )
return pos;
if( (pos = find3even(head+1, tail)) >=0 )
return pos;
}
return -1;
}
わかりました、私は問題にもう一度突き刺します。バランスのとれた二分木を使用して 1 間の距離を格納することで、既に説明したものと同様の O(n log(n)) アルゴリズムを証明できると思います。このアプローチは、問題を 1 の間の距離のリストに還元するという Justice の観察に触発されました。
入力文字列をスキャンして、各ノードが 1 の位置を格納し、各エッジが各子ノードの隣接する 1 までの距離でラベル付けされるように、1 の位置の周りにバランスの取れたバイナリ ツリーを構築できますか。例えば：
10010001 gives the following tree
3
/ \
2 / \ 3
/ \
0 7
これは O(n log(n)) で実行できます。これは、サイズ n の文字列の場合、最悪の場合、各挿入に O(log(n)) かかるためです。
次に問題は、ツリーを検索して、任意のノードで、そのノードから左の子を通るパスが、右の子を通るパスと同じ距離を持つかどうかを発見することです。これは、各サブツリーで再帰的に実行できます。検索で 2 つのサブツリーをマージする場合、左側のサブツリーのパスからの距離と右側のパスからの距離を比較する必要があります。サブツリー内のパスの数は log(n) に比例し、ノードの数は n であるため、これは O(n log(n)) 時間で実行できると思います。
何か見逃しましたか？
単純な問題タイプ (つまり、3 つの "1" を検索し、間に"0" のみ (つまり、0 個以上)を含める) の場合、非常に単純です: シーケンスをすべての "1" で分割し、2 つの隣接するサブシーケンスを探すことができます。同じ長さ (もちろん、2 番目のサブシーケンスは最後のサブシーケンスではありません)。明らかに、これはO(n)時間で実行できます。
より複雑なバージョン (つまり、 のようにインデックスiとギャップg >0を検索する) の場合、 O (n log n)の解がs[i]==s[i+g]==s[i+2*g]=="1"存在するかどうかはわかりません。このプロパティ (すべて 1 の文字列を考えてください。そのようなトリプレットは約n²/2あります)。もちろん、あなたはこれらのうちの 1 つだけを探していますが、私は現在、それを見つける方法がわかりません...
私の最善の努力にもかかわらず、お辞儀をしているようには見えないだろうといういくつかの考えがあります。それでも、それらは誰かの分析のための有用な出発点になるかもしれません。
提案された解決策を次のように考えてください。これは、この回答の以前のバージョンに私を含めて、何人かの人々が提案したアプローチです。:)
ここで、次のような入力文字列文字列について考えてみます。これには解決策がありません。
101
101001
1010010001
101001000100001
101001000100001000001
一般に、これは、j 0の形式のk個の文字列と、それに続くゼロからk-1までのjの1の連結です。
k=2 101
k=3 101001
k=4 1010010001
k=5 101001000100001
k=6 101001000100001000001
サブストリングの長さは1、2、3などであることに注意してください。したがって、問題サイズnには、n = k（k + 1）/2となる長さ1からkのサブストリングがあります。
k=2 n= 3 101
k=3 n= 6 101001
k=4 n=10 1010010001
k=5 n=15 101001000100001
k=6 n=21 101001000100001000001
kは、考慮しなければならない1の数も追跡することに注意してください。1を見るたびに、これまでに見たすべての1を考慮する必要があることを忘れないでください。したがって、2番目の1を見るときは、最初の1つだけを考慮し、3番目の1を見るときは、最初の2つを再検討し、4番目の1を見るときは、最初の3つを再検討する必要があります。アルゴリズムの終わりまでに、1のk（k-1）/2ペアを検討しました。そのpを呼び出します。
k=2 n= 3 p= 1 101
k=3 n= 6 p= 3 101001
k=4 n=10 p= 6 1010010001
k=5 n=15 p=10 101001000100001
k=6 n=21 p=15 101001000100001000001
nとpの関係は、n = p+kです。
文字列を通過するプロセスにはO（n）時間がかかります。1に遭遇するたびに、最大（k-1）の比較が行われます。n = k（k + 1）/ 2、n> k ** 2であるため、sqrt（n）>kとなります。これにより、O（n sqrt（n））またはO（n ** 3/2）が得られます。ただし、比較の数は1から最大kまでであるため、これは実際には厳密な範囲ではない可能性があることに注意してください。常にkではありません。しかし、数学でそれをどのように説明するかはわかりません。
それはまだO（n log（n））ではありません。また、これらの入力が最悪のケースであることを証明することはできませんが、最悪のケースであるとは思います。前面に1を密に詰めると、最後にさらにまばらに詰まると思います。
誰かがまだそれが役に立つと思うかもしれないので、Perlでのその解決策のための私のコードはここにあります：
#!/usr/bin/perl
# read input as first argument
my $s = $ARGV[0];
# validate the input
$s =~ /^[01]+$/ or die "invalid input string\n";
# strip leading and trailing 0's
$s =~ s/^0+//;
$s =~ s/0+$//;
# prime the position list with the first '1' at position 0
my @p = (0);
# start at position 1, which is the second character
my $i = 1;
print "the string is $s\n\n";
while ($i < length($s)) {
if (substr($s, $i, 1) eq '1') {
print "found '1' at position $i\n";
my @t = ();
# assuming this is the middle '1', go through the positions
# of all the prior '1's and check whether there's another '1'
# in the correct position after this '1' to make a solution
while (scalar @p) {
# $p is the position of the prior '1'
my $p = shift @p;
# $j is the corresponding position for the following '1'
my $j = 2 * $i - $p;
# if $j is off the end of the string then we don't need to
# check $p anymore
next if ($j >= length($s));
print "checking positions $p, $i, $j\n";
if (substr($s, $j, 1) eq '1') {
print "\nsolution found at positions $p, $i, $j\n";
exit 0;
}
# if $j isn't off the end of the string, keep $p for next time
push @t, $p;
}
@p = @t;
# add this '1' to the list of '1' positions
push @p, $i;
}
$i++;
}
print "\nno solution found\n";
問題への侵入の 1 つは、因子とシフトを考えることです。
シフトでは、1 と 0 の文字列をそれ自体のシフトされたバージョンと比較します。次に、一致するものを取ります。次の例を 2 シフトします。
1010101010
1010101010
------------
001010101000
結果の 1 (ビットごとの AND 演算) は、2 で均等に配置されたすべての 1 を表す必要があります。同じ例を 3 シフト:
1010101010
1010101010
-------------
0000000000000
この場合、3 等間隔に 1 が並ぶことはありません。
それで、これはあなたに何を伝えますか？素数であるシフトのみをテストする必要があります。たとえば、6 つ離れた 2 つの 1 があるとします。「2」シフトと「3」シフトのみをテストする必要があります (これらは 6 を分割するため)。例えば：
10000010
10000010 (Shift by two)
10000010
10000010 (We have a match)
10000010
10000010 (Shift by three)
10000010 (We have a match)
したがって、チェックする必要がある唯一のシフトは、2、3、5、7、11、13 などです。数字列のサイズの平方根に最も近い素数までです。
ほぼ解決？
解決に近づいたと思います。基本的：
答えへの最大の手がかりは、最速のソートアルゴリズムが O(n*log(n)) であるということだと思います。
違う
同僚が指摘したように、ステップ 1 は間違っています。位置 2、12、および 102 に 1 があるとします。次に、モジュラスを 10 にすると、それらはすべて同じ剰余になりますが、等間隔ではありません! ごめん。
# <algorithm>
def contains_evenly_spaced?(input)
return false if input.size < 3
one_indices = []
input.each_with_index do |digit, index|
next if digit == 0
one_indices << index
end
return false if one_indices.size < 3
previous_indexes = []
one_indices.each do |index|
if !previous_indexes.empty?
previous_indexes.each do |previous_index|
multiple = index - previous_index
success_index = index + multiple
return true if input[success_index] == 1
end
end
previous_indexes << index
end
return false
end
# </algorithm>
def parse_input(input)
input.chars.map { |c| c.to_i }
end
数百万桁という最悪のシナリオで困っています。からのファジングは/dev/urandom基本的に O(n) を提供しますが、最悪の場合はそれよりも悪いことを知っています。どれほど悪いかはわかりません。が小さいn場合、約 で入力を見つけるのは簡単3*n*log(n)ですが、この特定の問題の他の成長順序とそれらを区別するのは驚くほど困難です。
最悪の場合の入力に取り組んでいた人は、たとえば 10 万を超える長さの文字列を生成できますか?
ここには理論的な答えはありませんが、実行時の動作を k と n の関数として調査する簡単な Java プログラムを作成しました。ここで、n は合計ビット長、k は 1 の数です。ビット位置のすべてのペアをチェックして 3 番目のビットを探す「通常の」アルゴリズムは、最悪の場合 O(k^2) を必要とするにもかかわらず、現実には、最悪の場合はまばらなビット文字列が必要になるため、O(n ln n) になります。
とにかく、ここにプログラムがあります。これはモンテカルロ スタイルのプログラムであり、定数 n に対して多数の試行 NTRIALS を実行し、ベルヌーイ プロセスを使用して一定範囲の k 値に対してビットセットをランダムに生成し、指定可能な限界間で 1 密度を制約し、実行時間を記録します。等間隔のトリプレットを見つけたか、または見つけられなかったのか、時間は CPU 時間ではなくステップで測定されます。n = 64、256、1024、4096、16384 *（まだ実行中）で実行しました。最初に500000回の試行でテストを実行して、どのk値が最も長い実行時間を要したかを確認し、次に狭いもので5000000回の試行で別のテストを行いました-密度フォーカスを使用して、それらの値がどのように見えるかを確認します。最長の実行時間は、密度が非常にまばらな場合に発生します (たとえば、n=4096 の場合、実行時間のピークは k=16-64 の範囲にあり、k=31 で 4212 ステップで平均実行時間の緩やかなピークがあります。最大実行時間は 5101 ステップ @ k=58 でピークに達しました)。最悪の場合の O(k^2) ステップが、ビット文字列をスキャンして 1 の位置インデックスを見つける O(n) ステップよりも大きくなるには、N の値が非常に大きくなるようです。
package com.example.math;
import java.io.PrintStream;
import java.util.BitSet;
import java.util.Random;
public class EvenlySpacedOnesTest {
static public class StatisticalSummary
{
private int n=0;
private double min=Double.POSITIVE_INFINITY;
private double max=Double.NEGATIVE_INFINITY;
private double mean=0;
private double S=0;
public StatisticalSummary() {}
public void add(double x) {
min = Math.min(min, x);
max = Math.max(max, x);
++n;
double newMean = mean + (x-mean)/n;
S += (x-newMean)*(x-mean);
// this algorithm for mean,std dev based on Knuth TAOCP vol 2
mean = newMean;
}
public double getMax() { return (n>0)?max:Double.NaN; }
public double getMin() { return (n>0)?min:Double.NaN; }
public int getCount() { return n; }
public double getMean() { return (n>0)?mean:Double.NaN; }
public double getStdDev() { return (n>0)?Math.sqrt(S/n):Double.NaN; }
// some may quibble and use n-1 for sample std dev vs population std dev
public static void printOut(PrintStream ps, StatisticalSummary[] statistics) {
for (int i = 0; i < statistics.length; ++i)
{
StatisticalSummary summary = statistics[i];
ps.printf("%d\t%d\t%.0f\t%.0f\t%.5f\t%.5f\n",
i,
summary.getCount(),
summary.getMin(),
summary.getMax(),
summary.getMean(),
summary.getStdDev());
}
}
}
public interface RandomBernoulliProcess // see http://en.wikipedia.org/wiki/Bernoulli_process
{
public void setProbability(double d);
public boolean getNextBoolean();
}
static public class Bernoulli implements RandomBernoulliProcess
{
final private Random r = new Random();
private double p = 0.5;
public boolean getNextBoolean() { return r.nextDouble() < p; }
public void setProbability(double d) { p = d; }
}
static public class TestResult {
final public int k;
final public int nsteps;
public TestResult(int k, int nsteps) { this.k=k; this.nsteps=nsteps; }
}
////////////
final private int n;
final private int ntrials;
final private double pmin;
final private double pmax;
final private Random random = new Random();
final private Bernoulli bernoulli = new Bernoulli();
final private BitSet bits;
public EvenlySpacedOnesTest(int n, int ntrials, double pmin, double pmax) {
this.n=n; this.ntrials=ntrials; this.pmin=pmin; this.pmax=pmax;
this.bits = new BitSet(n);
}
/*
* generate random bit string
*/
private int generateBits()
{
int k = 0; // # of 1's
for (int i = 0; i < n; ++i)
{
boolean b = bernoulli.getNextBoolean();
this.bits.set(i, b);
if (b) ++k;
}
return k;
}
private int findEvenlySpacedOnes(int k, int[] pos)
{
int[] bitPosition = new int[k];
for (int i = 0, j = 0; i < n; ++i)
{
if (this.bits.get(i))
{
bitPosition[j++] = i;
}
}
int nsteps = n; // first, it takes N operations to find the bit positions.
boolean found = false;
if (k >= 3) // don't bother doing anything if there are less than 3 ones. :(
{
int lastBitSetPosition = bitPosition[k-1];
for (int j1 = 0; !found && j1 < k; ++j1)
{
pos[0] = bitPosition[j1];
for (int j2 = j1+1; !found && j2 < k; ++j2)
{
pos[1] = bitPosition[j2];
++nsteps;
pos[2] = 2*pos[1]-pos[0];
// calculate 3rd bit index that might be set;
// the other two indices point to bits that are set
if (pos[2] > lastBitSetPosition)
break;
// loop inner loop until we go out of bounds
found = this.bits.get(pos[2]);
// we're done if we find a third 1!
}
}
}
if (!found)
pos[0]=-1;
return nsteps;
}
/*
* run an algorithm that finds evenly spaced ones and returns # of steps.
*/
public TestResult run()
{
bernoulli.setProbability(pmin + (pmax-pmin)*random.nextDouble());
// probability of bernoulli process is randomly distributed between pmin and pmax
// generate bit string.
int k = generateBits();
int[] pos = new int[3];
int nsteps = findEvenlySpacedOnes(k, pos);
return new TestResult(k, nsteps);
}
public static void main(String[] args)
{
int n;
int ntrials;
double pmin = 0, pmax = 1;
try {
n = Integer.parseInt(args[0]);
ntrials = Integer.parseInt(args[1]);
if (args.length >= 3)
pmin = Double.parseDouble(args[2]);
if (args.length >= 4)
pmax = Double.parseDouble(args[3]);
}
catch (Exception e)
{
System.out.println("usage: EvenlySpacedOnesTest N NTRIALS [pmin [pmax]]");
System.exit(0);
return; // make the compiler happy
}
final StatisticalSummary[] statistics;
statistics=new StatisticalSummary[n+1];
for (int i = 0; i <= n; ++i)
{
statistics[i] = new StatisticalSummary();
}
EvenlySpacedOnesTest test = new EvenlySpacedOnesTest(n, ntrials, pmin, pmax);
int printInterval=100000;
int nextPrint = printInterval;
for (int i = 0; i < ntrials; ++i)
{
TestResult result = test.run();
statistics[result.k].add(result.nsteps);
if (i == nextPrint)
{
System.err.println(i);
nextPrint += printInterval;
}
}
StatisticalSummary.printOut(System.out, statistics);
}
}
これは楽しい問題のように思えたので、自分で試してみることにしました。
111000001 が最初の 3 つを見つけて成功すると仮定しています。あなたの定義によれば、0111000 は 111000 と同じであるため、基本的に 1 に続くゼロの数が重要です。1 のケースを 2 つ見つけたら、次に見つかった 1 つで 3 部作が完成します。
ここにPythonがあります：
def find_three(bstring):
print bstring
dict = {}
lastone = -1
zerocount = 0
for i in range(len(bstring)):
if bstring[i] == '1':
print i, ': 1'
if lastone != -1:
if(zerocount in dict):
dict[zerocount].append(lastone)
if len(dict[zerocount]) == 2:
dict[zerocount].append(i)
return True, dict
else:
dict[zerocount] = [lastone]
lastone = i
zerocount = 0
else:
zerocount = zerocount + 1
#this is really just book keeping, as we have failed at this point
if lastone != -1:
if(zerocount in dict):
dict[zerocount].append(lastone)
else:
dict[zerocount] = [lastone]
return False, dict
初めての試みなので、もっときれいに書けると思います。この方法が失敗するケースを以下に挙げてください。
O(n^2) スペースを使用した単純な O(n) ソリューションはどうですか? (すべてのビット演算子が O(1) で機能するという仮定を使用します。)
このアルゴリズムは、基本的に次の 4 つの段階で機能します。
ステージ 1: 元の数値の各ビットについて、それらがどれだけ離れているかを調べます。ただし、1 つの方向のみを考慮してください。(最下位ビットの方向のすべてのビットを考慮しました。)
ステージ 2: 入力のビットの順序を逆にします。
ステージ 3: 逆の入力でステップ 1 を再実行します。
ステージ 4: ステージ 1 とステージ 3 の結果を比較します。いずれかのビットが上下に等間隔に配置されている場合は、ヒットしている必要があります。
上記のアルゴリズムでは、O(n) よりも時間がかかるステップはないことに注意してください。^_^
追加の利点として、このアルゴリズムはすべての数字からすべての等間隔のものを見つけます。たとえば、「0x0005」の結果が得られた場合、1 単位と 3 単位の両方に等間隔のものが存在します。
以下のコードを実際に最適化しようとはしませんでしたが、コンパイル可能な C# コードで動作しているようです。
using System;
namespace ThreeNumbers
{
class Program
{
const int uint32Length = 32;
static void Main(string[] args)
{
Console.Write("Please enter your integer: ");
uint input = UInt32.Parse(Console.ReadLine());
uint[] distancesLower = Distances(input);
uint[] distancesHigher = Distances(Reverse(input));
PrintHits(input, distancesLower, distancesHigher);
}
/// <summary>
/// Returns an array showing how far the ones away from each bit in the input. Only
/// considers ones at lower signifcant bits. Index 0 represents the least significant bit
/// in the input. Index 1 represents the second least significant bit in the input and so
/// on. If a one is 3 away from the bit in question, then the third least significant bit
/// of the value will be sit.
///
/// As programed this algorithm needs: O(n) time, and O(n*log(n)) space.
/// (Where n is the number of bits in the input.)
/// </summary>
public static uint[] Distances(uint input)
{
uint[] distanceToOnes = new uint[uint32Length];
uint result = 0;
//Sets how far each bit is from other ones. Going in the direction of LSB to MSB
for (uint bitIndex = 1, arrayIndex = 0; bitIndex != 0; bitIndex <<= 1, ++arrayIndex)
{
distanceToOnes[arrayIndex] = result;
result <<= 1;
if ((input & bitIndex) != 0)
{
result |= 1;
}
}
return distanceToOnes;
}
/// <summary>
/// Reverses the bits in the input.
///
/// As programmed this algorithm needs O(n) time and O(n) space.
/// (Where n is the number of bits in the input.)
/// </summary>
/// <param name="input"></param>
/// <returns></returns>
public static uint Reverse(uint input)
{
uint reversedInput = 0;
for (uint bitIndex = 1; bitIndex != 0; bitIndex <<= 1)
{
reversedInput <<= 1;
reversedInput |= (uint)((input & bitIndex) != 0 ? 1 : 0);
}
return reversedInput;
}
/// <summary>
/// Goes through each bit in the input, to check if there are any bits equally far away in
/// the distancesLower and distancesHigher
/// </summary>
public static void PrintHits(uint input, uint[] distancesLower, uint[] distancesHigher)
{
const int offset = uint32Length - 1;
for (uint bitIndex = 1, arrayIndex = 0; bitIndex != 0; bitIndex <<= 1, ++arrayIndex)
{
//hits checks if any bits are equally spaced away from our current value
bool isBitSet = (input & bitIndex) != 0;
uint hits = distancesLower[arrayIndex] & distancesHigher[offset - arrayIndex];
if (isBitSet && (hits != 0))
{
Console.WriteLine(String.Format("The {0}-th LSB has hits 0x{1:x4} away", arrayIndex + 1, hits));
}
}
}
}
}
十分に大きな数の場合、O(1) ではビット演算を実行できないとコメントする人もいるでしょう。あなたは正しいでしょう。ただし、加算、減算、乗算、または除算 (シフトでは実行できない) を使用するすべてのソリューションにもその問題があると思います。
問題を解決する方法を見つけたと思いますが、正式な証明を構築することはできません。私が作成したソリューションは Java で記述されており、カウンター 'n' を使用して、リスト/配列へのアクセス回数をカウントします。したがって、n が正しければ、stringLength*log(stringLength) 以下である必要があります。0 から 2^22 までの数値で試してみましたが、うまくいきました。
入力文字列を繰り返し処理し、1 を保持するすべてのインデックスのリストを作成することから始めます。これは単なる O(n) です。
次に、インデックスのリストから、firstIndex と、最初よりも大きい secondIndex を選択します。これらの 2 つのインデックスは、インデックスのリストにあるため、1 を保持する必要があります。そこから thirdIndex を計算できます。inputString[secondIndex] が 1 の場合、停止します。
public static int testString(String input){
//n is the number of array/list accesses in the algorithm
int n=0;
//Put the indices of all the ones into a list, O(n)
ArrayList<Integer> ones = new ArrayList<Integer>();
for(int i=0;i<input.length();i++){
if(input.charAt(i)=='1'){
ones.add(i);
}
}
//If less than three ones in list, just stop
if(ones.size()<3){
return n;
}
int firstIndex, secondIndex, thirdIndex;
for(int x=0;x<ones.size()-2;x++){
n++;
firstIndex = ones.get(x);
for(int y=x+1; y<ones.size()-1; y++){
n++;
secondIndex = ones.get(y);
thirdIndex = secondIndex*2 - firstIndex;
if(thirdIndex >= input.length()){
break;
}
n++;
if(input.charAt(thirdIndex) == '1'){
//This case is satisfied if it has found three evenly spaced ones
//System.out.println("This one => " + input);
return n;
}
}
}
return n;
}
追加の注意: カウンター n は、入力文字列を反復処理してインデックスのリストを作成するときにインクリメントされません。この操作は O(n) であるため、アルゴリズムの複雑さには影響しません。
明らかに、少なくともトリプレットの束を同時にチェックする必要があるため、何らかの形でチェックを圧縮する必要があります。候補となるアルゴリズムがありますが、時間の複雑さを分析することは、私の能力 * 時間のしきい値を超えています。
各ノードに 3 つの子があり、各ノードがその葉に 1 の総数を含むツリーを構築します。同様に、1 の上にリンクされたリストを作成します。各ノードに、カバーする範囲に比例する許容コストを割り当てます。各ノードで費やす時間が予算内である限り、O(n lg n) アルゴリズムを使用します。
--
ルートから始めます。それより下の 1 の合計数の 2 乗が許容コストよりも小さい場合は、単純なアルゴリズムを適用します。それ以外の場合は、その子に対して再帰します。
これで、予算内に戻ったか、子の 1 つに完全に含まれる有効なトリプレットがないことがわかりました。したがって、ノード間のトリプレットを確認する必要があります。
今、物事は信じられないほど乱雑になります。基本的に、範囲を制限しながら、潜在的な子のセットを再帰したいと考えています。単純なアルゴリズムが予算内で実行されるように範囲が十分に制限されるとすぐに、それを実行します。私はそれが退屈であることを保証するので、これを実装して楽しんでください。十数件のケースがあります。
--
アルゴリズムが機能すると私が考える理由は、有効なトリプレットを持たないシーケンスが 1 の束と多数の 0 の間で交互に表示されるためです。近くの検索スペースを効果的に分割し、ツリーはその分割をエミュレートします。
アルゴリズムの実行時間はまったく明らかではありません。これは、シーケンスの重要なプロパティに依存しています。1 が本当にまばらな場合、単純なアルゴリズムは予算内で機能します。1 が密集している場合は、一致がすぐに見つかるはずです。しかし、密度が「ちょうどいい」場合 (たとえば、基数 3 の「2」桁のない位置にすべてのビットを設定することで達成できる ~n^0.63 付近)、それが機能するかどうかはわかりません。分割効果が十分に強いことを証明する必要があります。
これが nlog(n) である理由は次のとおりだと思います。
したがって、n、log(n)、および 1 があります... O(nlogn)
編集：おっと、悪い。私の脳は、n/2 がログに記録されるように設定していました...明らかにそうではありません (アイテムの数を 2 倍にしても、内側のループの反復回数は 2 倍になります)。これはまだ n^2 であり、問題は解決していません。まあ、少なくとも私はいくつかのコードを書かなければなりません:)
Tcl での実装
proc get-triplet {input} {
for {set first 0} {$first < [string length $input]-2} {incr first} {
if {[string index $input $first] != 1} {
continue
}
set start [expr {$first + 1}]
set end [expr {1+ $first + (([string length $input] - $first) /2)}]
for {set second $start} {$second < $end} {incr second} {
if {[string index $input $second] != 1} {
continue
}
set last [expr {($second - $first) + $second}]
if {[string index $input $last] == 1} {
return [list $first $second $last]
}
}
}
return {}
}
get-triplet 10101 ;# 0 2 4
get-triplet 10111 ;# 0 2 4
get-triplet 11100000 ;# 0 1 2
get-triplet 0100100100 ;# 1 4 7
以下は解決策です。ところどころに小さな間違いがあるかもしれませんが、アイデアは健全です。
編集: n * log(n) ではありません
疑似コード:
foreach character in the string
if the character equals 1 {
if length cache > 0 { //we can skip the first one
foreach location in the cache { //last in first out kind of order
if ((currentlocation + (currentlocation - location)) < length string)
if (string[(currentlocation + (currentlocation - location))] equals 1)
return found evenly spaced string
else
break;
}
}
remember the location of this character in a some sort of cache.
}
return didn't find evenly spaced string
C# コード:
public static Boolean FindThreeEvenlySpacedOnes(String str) {
List<int> cache = new List<int>();
for (var x = 0; x < str.Length; x++) {
if (str[x] == '1') {
if (cache.Count > 0) {
for (var i = cache.Count - 1; i > 0; i--) {
if ((x + (x - cache[i])) >= str.Length)
break;
if (str[(x + (x - cache[i]))] == '1')
return true;
}
}
cache.Add(x);
}
}
return false;
}
使い方：
iteration 1:
x
|
101101001
// the location of this 1 is stored in the cache
iteration 2:
x
|
101101001
iteration 3:
a x b
| | |
101101001
//we retrieve location a out of the cache and then based on a
//we calculate b and check if te string contains a 1 on location b
//and of course we store x in the cache because it's a 1
iteration 4:
axb
|||
101101001
a x b
| | |
101101001
iteration 5:
x
|
101101001
iteration 6:
a x b
| | |
101101001
a x b
| | |
101101001
//return found evenly spaced string
予測：
ちょうど間違っている、log(n) 個の上限の数について話している
編集：
カントール数を使用すると (正しい場合)、セットの密度は (2/3)^Log_3(n) (奇妙な関数) であり、log(n)/n 密度が強すぎることに同意します。
これが上限であれば、少なくとも O(n*(3/2)^(log(n)/log(3))) 時間の複雑さと O((3/2)^( log(n)/log(3))) スペースの複雑さ。（アルゴリズムについては正義の答えを確認してください）
これは、O(n^2) よりもはるかに優れています。
この関数 ((3/2)^(log(n)/log(3))) は、一見 n*log(n) のように見えます。
どうやってこの式を得たのですか？
カントル数を弦にかける。
文字列の長さが 3^p == n
であるとします。 Cantor 文字列の生成の各ステップで、前の 1 の数の 2/3 を保持します。これを p 回適用します。
つまり、(n * ((2/3)^p)) -> (((3^p)) * ((2/3)^p)) 残りのもので、単純化後は 2^p になります。これは、3^p 文字列内の 2^p のものを意味します -> (3/2)^p のもの。p=log(n)/log(3) を代入して
((3/2)^(log(n)/log(3)))を取得します。
1 をスキャンしながら、それらの位置をリストに追加します。2 番目以降の 1 を追加するときは、これまでのリストの各位置と比較します。間隔は currentOne (中央) - previousOne (左) に等しくなります。右側のビットは currentOne + 間隔です。1なら終わり。
1 のリストは、それらの間のスペースに反比例して大きくなります。簡単に言うと、1 の間に 0 がたくさんある場合 (最悪の場合)、既知の 1 のリストは非常にゆっくりと増えます。
using System;
using System.Collections.Generic;
namespace spacedOnes
{
class Program
{
static int[] _bits = new int[8] {128, 64, 32, 16, 8, 4, 2, 1};
static void Main(string[] args)
{
var bytes = new byte[4];
var r = new Random();
r.NextBytes(bytes);
foreach (var b in bytes) {
Console.Write(getByteString(b));
}
Console.WriteLine();
var bitCount = bytes.Length * 8;
var done = false;
var onePositions = new List<int>();
for (var i = 0; i < bitCount; i++)
{
if (isOne(bytes, i)) {
if (onePositions.Count > 0) {
foreach (var knownOne in onePositions) {
var spacing = i - knownOne;
var k = i + spacing;
if (k < bitCount && isOne(bytes, k)) {
Console.WriteLine("^".PadLeft(knownOne + 1) + "^".PadLeft(spacing) + "^".PadLeft(spacing));
done = true;
break;
}
}
}
if (done) {
break;
}
onePositions.Add(i);
}
}
Console.ReadKey();
}
static String getByteString(byte b) {
var s = new char[8];
for (var i=0; i<s.Length; i++) {
s[i] = ((b & _bits[i]) > 0 ? '1' : '0');
}
return new String(s);
}
static bool isOne(byte[] bytes, int i)
{
var byteIndex = i / 8;
var bitIndex = i % 8;
return (bytes[byteIndex] & _bits[bitIndex]) > 0;
}
}
}
数学的アプローチを提示しようと思います。これは終わりというよりも始まりであるため、ヘルプ、コメント、または矛盾さえも歓迎します。ただし、このアプローチが証明されている場合、アルゴリズムは文字列内の単純な検索です。
固定数のスペースkと stringが与えられた場合S、k-spaced-triplet の検索には、すべてのifO(n)を単純にテストします。テストには時間がかかり、 が定数である回数実行するので、 がかかります。0<=i<=(n-2k)S[i]==S[i+k]==S[i+2k]O(1)n-kkO(n-k)=O(n)
1の数と、検索する必要がある最大スペースとの間に反比例があると仮定しましょう。つまり、1の数が多い場合は、トリプレットが存在する必要があり、非常に密集している必要があります。がほとんどない場合1、トリプレット (存在する場合) は非常にまばらになる可能性があります。言い換えると、十分な数1の がある場合、そのようなトリプレットが存在する必要があることを証明でき1ます。これはピジョンホールの原理で説明できます- これについては後で詳しく説明します。
k検索する必要があるスペースの可能な数に上限があるとします。ここで、 に1あるそれぞれについて、と、、... 、S[i]をチェックする必要があります。これは、 Gauss の Series Summation Formulaにより、for each in - かかります。これはセクション 1 とは異なることに注意してください。一定のスペースとしてではなく、スペース数の上限として使用しています。1S[i-1]S[i+1]S[i-2]S[i+2]S[i-k]S[i+k]O((k^2-k)/2)=O(k^2)1Sk
を証明する必要がありO(n*log(n))ます。つまり、が にk*(number of 1's)比例することを示す必要がありlog(n)ます。
それができれば、アルゴリズムは自明です。インデックス が1であるそれぞれについて、両側から距離 まで を探すだけです。2 つが同じ距離にある場合は、 と を返します。繰り返しますが、トリッキーな部分は、正確さを見つけて証明することです。Si1kikk
kここでコメントをいただければ幸いです。ホワイトボード上のと の数との関係を見つけようとしていますが1、これまでのところ成功していません。
Rabin-Karp アルゴリズムの適応が可能になる可能性があります。その複雑さは 0(n) なので、役に立ちます。
http://en.wikipedia.org/wiki/Rabin-Karp_string_search_algorithmをご覧ください
このアルゴリズムにはO（n log n）の複雑さがあります（C ++、DevStudio 2k5）。さて、アルゴリズムを分析してその複雑さを判断する方法の詳細がわからないので、コードにいくつかのメトリック収集情報を追加しました。このコードは、任意の入力に対して1と0のシーケンスで実行されたテストの数をカウントします（うまくいけば、私はアルゴリズムのボールを作成していません）。実際のテスト数をO値と比較して、相関関係があるかどうかを確認できます。
#include <iostream>
using namespace std;
bool HasEvenBits (string &sequence, int &num_compares)
{
bool
has_even_bits = false;
num_compares = 0;
for (unsigned i = 1 ; i <= (sequence.length () - 1) / 2 ; ++i)
{
for (unsigned j = 0 ; j < sequence.length () - 2 * i ; ++j)
{
++num_compares;
if (sequence [j] == '1' && sequence [j + i] == '1' && sequence [j + i * 2] == '1')
{
has_even_bits = true;
// we could 'break' here, but I want to know the worst case scenario so keep going to the end
}
}
}
return has_even_bits;
}
int main ()
{
int
count;
string
input = "111";
for (int i = 3 ; i < 32 ; ++i)
{
HasEvenBits (input, count);
cout << i << ", " << count << endl;
input += "0";
}
}
このプログラムは、最大32文字の文字列長ごとのテスト数を出力します。結果は次のとおりです。
n Tests n log (n)
=====================
3 1 1.43
4 2 2.41
5 4 3.49
6 6 4.67
7 9 5.92
8 12 7.22
9 16 8.59
10 20 10.00
11 25 11.46
12 30 12.95
13 36 14.48
14 42 16.05
15 49 17.64
16 56 19.27
17 64 20.92
18 72 22.59
19 81 24.30
20 90 26.02
21 100 27.77
22 110 29.53
23 121 31.32
24 132 33.13
25 144 34.95
26 156 36.79
27 169 38.65
28 182 40.52
29 196 42.41
30 210 44.31
31 225 46.23
'nlogn'の値も追加しました。選択したグラフ作成ツールを使用してこれらをプロットし、2つの結果の相関関係を確認します。この分析はnのすべての値に拡張されますか？知らない。
これは解決策になるでしょうか？O(nlogn) かどうかはわかりませんが、O(n²) よりも優れていると思います。なぜなら、トリプルを見つけられない唯一の方法は素数の分布だからです。
改善の余地があります。2 番目に見つかった 1 は、次の最初の 1 になる可能性があります。また、エラー チェックもありません。
#include <iostream>
#include <string>
int findIt(std::string toCheck) {
for (int i=0; i<toCheck.length(); i++) {
if (toCheck[i]=='1') {
std::cout << i << ": " << toCheck[i];
for (int j = i+1; j<toCheck.length(); j++) {
if (toCheck[j]=='1' && toCheck[(i+2*(j-i))] == '1') {
std::cout << ", " << j << ":" << toCheck[j] << ", " << (i+2*(j-i)) << ":" << toCheck[(i+2*(j-i))] << " found" << std::endl;
return 0;
}
}
}
}
return -1;
}
int main (int agrc, char* args[]) {
std::string toCheck("1001011");
findIt(toCheck);
std::cin.get();
return 0;
}
これは線形時間 O(n) で解くことができます
1つヒットしたらNumberOfZeros == PrevZerosをチェック
true の場合はカウンターを返します
それ以外の NumberOfZeros -> prev_zerosおよびgoto 4