4

给定两个有限的字符串序列A和B，每个序列的长度n，例如：

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. 在这个例子中只有两个字符，但已经非常困难了。实际上，找到一个字符的最短解决方案甚至都不是一件容易的事！

我试着想一些事情..例如，字符串长度的总和必须相等，并且对于第一个和最后一个字符串，我们需要相应的字符。但没有别的。我想对于某些字符串来说这是不可能的。任何人都可以想到一个好的算法？

编辑：显然，这是邮政通信问题

没有算法可以决定这样的实例是否有解决方案。如果有，就可以解决停机问题。肮脏的伎俩...

4

4 回答 4

2

非常棘手的问题，但我会试一试。这更像是一种意识流而不是答案，提前道歉。

如果我理解正确，你会得到 2 个大小相等的字符串序列，A 和 B，从 1..n 开始索引，比如说。然后，您必须找到一个索引序列，使得字符串 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}
...

那么你怎么知道什么时候停止呢？只要你有一个解决方案？一旦一个解决方案是另一个解决方案的超集？

您可以开始的一个地方是从两组中获取所有最小公共长度的字符串（在我上面的示例中，您将从两者中获取“x”，并搜索 2 个共享公共索引的相等字符串。然后您可以对下一个大小的字符串重复此操作。例如，如果第一组有 3 个长度分别为 1、2 和 3 的字符串，而第二组分别有长度为 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 回答
0

目前尚不清楚您正在寻找的“解决方案”是什么，最长的解决方案？最短的？所有解决方案？
由于您允许重复，因此某些输入将有无限数量的解决方案，因此我将继续：

查找固定长度下的所有序列。

以伪代码形式编写，但与 f# 序列表达式非常相似

// assumed true/false functions

let Eq aList bList =  
// eg Eq "ab"::"c" "a" :: "bc" -> true
// Eq {} {} is _false_

let EitherStartsWith aList bList =  
// eg "ab"::"c" "a" :: "b" -> true
// eg "a" "ab" -> true
// {} {} is _true_    

let rec FindMatches A B aList bList level
    = seq {
        if level > 0
            if Eq aList bList
                yield aList
            else if EitherStartsWith aList bList
                Seq.zip3 A B seq {1..} 
                |> Seq.iter (func (a,b,i) -> 
                    yield! FindMatches A B aList::(a,i) bList::(b,i) level - 1) }

let solution (A:seq<string>) (B:seq<string>) length =
    FindMatches A B {} {} length

一些减少问题的简单约束：

  1. 第一个选择对必须有一个共同的开始部分。
  2. 最终选择对必须有一个共同的结束部分。

基于此我们可以快速消除许多无解的输入

let solution (A:seq<string>) (B:seq<string>) length =
    let starts = {}
    let ends = {}
    Seq.zip3 A B seq {1..} 
    |> Seq.iter(fun (a,b,i) -> 
        if (a.StartsWith(b) or b.StartsWith(a))
            start = starts :: (a,b,i)
        if (a.EndsWith(b) or b.EndsWith(a))
            ends = ends :: (a,b,i))

    if List.is_empty starts || List.is_empty ends
        Seq.empty // no solution
    else
        Seq.map (fun (a,b,i) -> 
            FindMatches A B {} :: (a,i) {} :: (b,i) length - 1)
        starts 
        |> Seq.concat
于 2009-07-11T16:37:48.303 回答