4

それぞれの長さの文字列 と の 2 つの有限シーケンスが与えられAた場合、たとえば、次のようになります。Bn

A1: "kk", A2: "ka", A3: "kkk", A4: "a"

B1: "ka", B2: "kakk", B3: "ak", B4: "k"

A と B の濃度が同じ文字列になるように、インデックスの有限シーケンスを指定します。繰り返しが許可されています。

この例では解決策を見つけることができませんが、たとえば、リスト(1,2,2,4)が解決策である場合はA1 + A2 + A2 + A4 = B1 + B2 + B2 + B4. この例では 2 人のキャラクターしかいませんが、すでに非常に困難です。実際、1 つの文字で最短の解決策を見つけることは簡単なことではありません。

私は物事を考えようとしました..たとえば、文字列の長さの合計は等しくなければならず、最初と最後の文字列には対応する文字が必要です。しかし、他には何もありません。いくつかの文字列のセットでは、それは単に不可能だと思います。誰でも良いアルゴリズムを思いつくことができますか?

編集：どうやら、これは通信後の問題です

そのようなインスタンスに解があるかどうかを判断できるアルゴリズムはありません。もしあれば、停止の問題は解決できます。汚い手口...

4

4 に答える 4

2

非常に難しい質問ですが、試してみます。これは答えというよりも意識の流れであり、事前に謝罪します。

私がこれを正しく理解していれば、1..nからインデックス付けされた、AとBの2つの等しいサイズの文字列シーケンスが与えられます。次に、文字列A（1）.. A（m）の連結が文字列B（1）.. B（m）の連結と等しくなるように、インデックスのシーケンスを見つける必要があります。ここで、mはインデックスのシーケンスの長さです。 。

私が最初に観察することは、ソリューションが無限に存在する可能性があるということです。たとえば、次のようになります。

A {"x"、 "xx"}
B {"xx"、 "x"}

考えられる解決策は次のとおりです。

{1、2}
{2、1 } {
1、2、1、2 } {1、2、2、1} {2、1、1、2} { 2、1、2、1} {1、2 、1、2、1、2} ..。




では、いつ停止するかをどうやって知るのでしょうか？解決策が1つあるとすぐに？ソリューションの1つが別のソリューションのスーパーセットになるとすぐに？

開始できる1つの場所は、両方のセットから最小の共通の長さのすべての文字列を取得することです（上記の例では、両方から「x」を取得し、共通のインデックスを共有する2つの等しい文字列を検索します。次のサイズの文字列に対してこれを繰り返します。たとえば、最初のセットにそれぞれ長さ1、2、3の3つの文字列があり、2番目のセットにそれぞれ長さ1、3、3の文字列がある場合、次の文字列を取得します。長さ3。文字列がなくなるまでこれを行います。文字列が見つかった場合は、問題の解決策があります。

上記の例のように、複数の文字列を組み合わせ始める必要がある場合は、さらに難しくなります。素朴で力ずくのアプローチは、両方のセットのすべての文字列の並べ替えを開始し、連結すると同じ長さの文字列になり、それらを比較することです。したがって、以下の例では：

A {"ga"、 "bag"、 "ac"、 "a"}
B {"ba"、 "g"、 "ag"、 "gac"}

長さ2のシーケンスから始めます。

A {"ga"、 "ac"}、B {"ba"、 "ag"}（インデックス1、3）
A {"bag"、 "a"}、B {"g"、 "gac"}（インデックス2、4）

これらを比較すると、「gaac」と「baag」および「baga」と「ggac」が得られますが、どちらも等しくないため、解決策はありません。次に、長さ3のシーケンスに進みます。

A {"ga"、 "bag"、 "a"}、B {"ba"、 "g"、 "gac"}（インデックス1、2、4）
A {"bag"、 "ac"、 "a" }、B {"g"、 "ag"、 "gac"}（インデックス2、3、4）

繰り返しますが、解決策がないため、サイズ4のシーケンスになり、その解決策はありません。

おそらくいくつかのインデックスを繰り返すことを考え始めなければならないので、今ではさらにトリッキーになり、今では私の脳が溶けています。

文字列内の一般的なサブシーケンスを探して、一致しなかった文字列内の残りの部分を使用すると役立つと思います。しかし、私はその方法がよくわかりません。

于 2009-07-11T11:52:56.913 に答える
2

非常に簡単な方法は、幅優先探索のようなものを使用することです。これには、最初に見つかったソリューションのサイズが最小になるという利点もあります。

于 2009-07-11T12:00:23.047 に答える
0

ブルートフォース検索の提案は次のとおりです。最初に、リストの長さに制限された数列を生成します。

[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();
            }
    }

簡単なテストではうまくいくように見えましたが、解決策は見つかりませんでした。

于 2009-07-11T14:19:26.043 に答える