ブルートフォース検索の提案は次のとおりです。最初に、リストの長さに制限された数列を生成します。
[0,0,..] [1,0,..] [2,0,..] [3,0,..] [0,1,..] ...
数列の長さによって、見つかった解に含まれる文字列の数が決まります。次に、数値を文字列リストのインデックスとして使用して、A および B 文字列を生成します。
public class FitSequence
{
private readonly string[] a;
private readonly string[] b;
public FitSequence(string[] a, string[] b)
{
this.a = a;
this.b = b;
}
private static string BuildString(string[] source, int[] indexes)
{
var s = new StringBuilder();
for (int i = 0; i < indexes.Length; ++i)
{
s.Append(source[indexes[i]]);
}
return s.ToString();
}
public IEnumerable<int[]> GetSequences(int length)
{
foreach (var numberSequence in new NumberSequence(length).GetNumbers(a.Length - 1))
{
string a1 = BuildString(a, numberSequence);
string b1 = BuildString(b, numberSequence);
if (a1 == b1)
yield return numberSequence;
}
}
}
このアルゴリズムは、A と B の長さが等しいことを前提としています。
static void Main(string[] args)
{
var a = new[] {"kk", "ka", "kkk", "a"};
var b = new[] {"ka", "kakk", "ak", "k"};
for (int i = 0; i < 100; ++i)
foreach (var sequence in new FitSequence(a, b).GetSequences(i))
{
foreach (int x in sequence)
Console.Write("{0} ", x);
Console.WriteLine();
}
}
簡単なテストではうまくいくように見えましたが、解決策は見つかりませんでした。