Javaの与えられた最大ハミング距離（不一致の数）ですべての文字列の組み合わせを取得

Question

アルゴリズムがありますか？文字列（DNAシーケンス）の可能なすべての文字列の組み合わせを、 、最大ハミング距離）？

アルファベットは{A、C、T、G}です。不一致2の文字列AGCCと最大数の

例：

Hamming distance is 0 
    {AGCC} 
Hamming distance is 1 
    {CGCC, TGCC, GGCC, AACC, ACCC, ATCC, AGAC, AGTC, ..., AGCG} 
Hamming distance is 2 
    {?} 

一つの可能​​なアプローチは、与えられた文字列のすべての順列とのセットを生成し、それらを反復し、より大きなハミングですべての文字列を削除することですそれがあるはずの距離。アプローチは5

の20文字の指定したStringと最大のハミング距離によって、非常にressource食いであること

は、そのための別の、より効率的なapprocahes /実装はありますか？

Answer 1

通常のパーミュテーション生成アルゴリズムを使用します。ただし、距離を渡して別の文字があるときに減分する点が異なります。

static void permute(char[] arr, int pos, int distance, char[] candidates) 
{ 
    if (pos == arr.length) 
    { 
     System.out.println(new String(arr)); 
     return; 
    } 
    // distance > 0 means we can change the current character, 
    // so go through the candidates 
    if (distance > 0) 
    { 
     char temp = arr[pos]; 
     for (int i = 0; i < candidates.length; i++) 
     { 
     arr[pos] = candidates[i]; 
     int distanceOffset = 0; 
     // different character, thus decrement distance 
     if (temp != arr[pos]) 
      distanceOffset = -1; 
     permute(arr, pos+1, distance + distanceOffset, candidates); 
     } 
     arr[pos] = temp; 
    } 
    // otherwise just stick to the same character 
    else 
     permute(arr, pos+1, distance, candidates); 
} 

コールと：

permute("AGCC".toCharArray(), 0, 1, "ACTG".toCharArray()); 

パフォーマンスノート：20の文字列の長さについては

、5の距離と5文字のアルファベット、1700万候補の上に既に存在しています（私のコードが正しいと仮定して）。

私のマシン上では（印刷せずに）これらのコードを実行するのに1秒もかかりませんが、ジェネレータがそれ以上の時間を生成することは期待できません。単にあまりにも多くの可能性。