•  12-09-2019
  •  | 
  •  

题

给定两个有限的字符串序列， 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. 。在这个例子中只有两个角色，但是已经非常困难了。事实上，找到一个字符的最短解决方案并不是一件容易的事！

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

编辑：显然，这就是 帖子通信问题

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

有帮助吗？

解决方案

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

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

以伪代码形式编写，但方式与 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

其他提示

非常棘手的问题，但我给它一个镜头。这是更意识比回答的流的，道歉提前。

如果我明白这个正确，你给出的字符串，A和B，从1..N索引的2组相等尺寸的序列，比方说。然后，你必须找到索引的序列，使得字符串的连接A（1）.. A（M）等于字符串的连接B（1）.. B（m），其中m为索引的序列的长度

我将观察到的第一件事是，有可能是解决方案的无穷数。例如，给定：

  

A {的 “x”， “XX”}，点击   B { “XX”， “×”}

可能的解决方案是：

  

{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个等于字符串。然后，您可以重复这一过程，下一个规模达的字符串。例如，如果第一组分别具有长度为1，2和3个的字符串，而第二组分别具有长度为1,3和3的字符串，你会采取3.长度的字符串，直到你有没有更多的字符串你会做到这一点。如果你找到了，那么你有一个解决问题的办法。

然后获取困难时，你必须开始几串结合如上面我的例子。天真，蛮力的方法是开始从置换两套是，当串联，导致相同长度的字符串的所有字符串，然后对它们进行比较。因此，在下面的例子：

  

A { “GA”， “包”， “AC”， “一个”}，点击   B { “BA”， “G”， “股份公司”， “GAC”}

您将开始与长度为2的序列：

  

A { “GA”， “AC”}，B { “BA”， “股份公司”}（索引1，3），点击   A { “袋”， “一个”}，B { “克”， “GAC”}（索引2,4）

比较这些给出“GAAC”与“baag”和“巴加”与“GGAC”，这两者都不相等，所以没有解决方案存在。接下来，我们将去长度为3的序列：

  

A { “GA”， “包”， “一个”}，B { “BA”， “G”， “GAC”}（索引1，2，4），点击   A { “袋”， “AC”， “一个”}，B { “克”， “股份公司”， “GAC”}（指数2，3，4）

同样，没有解决方案，使然后我们最终大小为4的序列，其中我们没有解决方案。

现在它变得更加棘手，因为我们不得不开始思考或许是重复一些指标，现在我的大脑正在融化。

我想寻找的字符串的常见子序列可能是有益的，然后在不匹配的字符串中使用的剩余部分。但是我不太知道怎么办。

有一个非常简单的方式就是使用类似广度优先搜索。这还具有以下优点，即第一溶液中发现将具有最小尺寸。

下面是一个蛮力搜索的建议。第一产生一定到您的列表的长度数序列：

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

但无法找到任何解决方案，但它似乎对简单的测试工作。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top