5

私は乱数の配列を持っています：

[ 10,11,12,14,15,16,17,18,19,20,11,12,14,25,25,26,27,28,29 ] _ _ _ _

繰り返されるシーケンスを検出する必要があります (魔女は実際にはエラーです)

長さが特定の数値 (2) より大きい場合。

これに適したアルゴリズムはありますか?

私が今持っているもの：

int minLenght = 3;
int[] data = {1,2,3};

for(int i = 0; i < data.length; i++){
    for(int j = 0; j < data.length; j++){
        if ( data[i] == data[j]){
            int l = 0;
            int ii = i;
            int jj = j;
            while(data[ii] == data[jj]){
                ii++;
                jj++;
                l++;
            }
            if(l >= minLenght){
                print('['+i+'-'+ii+'] same as ['+j+'-'+jj+']');
            }
        }
    }
}
4

3 に答える 3

4

1 つの方法は、長さ L (特定の長さより 1 つ大きい) のシーケンスをハッシュ テーブルに格納することです。

シーケンスが既にハッシュ テーブルにある場合は、長さ >= L の繰り返しが見つかりました。

例: Python コード

A=[10,11,12,14,15,16,17,18,19,20,11,12,14,25,25,26,27,28,29]
S=set()
L=2+1
for i in xrange(len(A)-L+1):
    key=tuple(A[i:i+L])
    if key in S:
        print i
    else:
        S.add(key)

これにより、長さが 2 を超える繰り返しシーケンスの位置が出力されます。

于 2012-11-27T21:29:38.397 に答える
0

これに特別なアルゴリズムがあるかどうかはわかりませんが、私の提案は次のようになります。

loop1 over array[i]:
  loop2 over array[j] starting with i+1:
    dist=array[j]-array[i];
    if dist==specific_number:
      array_result.append(array[i] +""+""+array[j])

これは私の単純な論理です。

于 2012-11-27T21:30:03.543 に答える
0

示されているリスト形式が不規則であることを除いて、正規表現を使用できます。以下のPythonを使用し、リスト形式を「正規化」して文字列に変換してから、正規表現を適用して、数字/非数字の重複シーケンスを探します。

>>> import re
>>> numbers = [10,11,12,14,15,16,17,18,19,20, 11, 12, 14,25,25,26,27,28,29]
>>> sep = ', '
>>> txt = sep + sep.join(str(x) for x in numbers) + sep
>>> txt
', 10, 11, 12, 14, 15, 16, 17, 18, 19, 20, 11, 12, 14, 25, 25, 26, 27, 28, 29, '
>>> re.search(r'\D((?:\d+\D+){2,}).*\1', txt).groups()
('11, 12, 14, ',)

私は通常、正規表現の使用を最小限に抑えようとしますが、これにより重複が検出されます。

于 2012-11-28T07:03:54.307 に答える