Алгоритм интересных строк

Question

Учитывая две конечные последовательности строк, 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. В этом примере только два символа, но это уже очень сложно. На самом деле, найти кратчайшее решение с одним символом даже не тривиально!

Я пытался думать о вещах ... например, общая сумма длины строк должна быть равна, а для первой и последней строки нам нужны соответствующие символы. Но больше ничего. Я предполагаю, что для некоторого набора строк это просто невозможно. Кто-нибудь может придумать хороший алгоритм?

РЕДАКТИРОВАТЬ: По-видимому, это Проблема переписки

Нет алгоритма, который мог бы решить, есть ли у такого экземпляра решение или нет. Если бы они были, проблема остановки могла бы быть решена. Грязный трюк ...

Answer 1

Очень простой способ - просто использовать что-то вроде поиска в ширину. Это также имеет то преимущество, что первое найденное решение будет иметь минимальный размер.

Answer 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, из которых у нас нет решений.

Теперь это становится еще сложнее, так как мы должны начать думать о возможном повторении некоторых показателей, и теперь мой мозг тает.

Я думаю, что поиск общих подпоследовательностей в строках может быть полезным, а затем использование оставшихся частей в строках, которые не были сопоставлены. Но я не совсем знаю как.

Answer 3

Не ясно, какое «решение» вы ищете, самое длинное решение? кратчайший? все решения?
Поскольку вы разрешаете повторение, для некоторых входов будет бесконечное количество решений, поэтому я буду работать над:

Найти все последовательности с фиксированной длиной.

Написано как псевдокод, но очень похоже на выражения последовательности 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

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

но не смог найти никаких решений, хотя казалось, что он работает для простых тестов.