Поиск всех возможных длинных возрастающих подпоследовательностей

Question

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

Например: заданная строка qapbso

Здесь длина самой длинной увеличивающейся подпоследовательности равна 3. Я хочу найти всю возможную самую длинную подпоследовательность длины 3. Т.е. «abs», «aps», «abo».

Я использую динамическое программирование, но получаю только одну LIS. Я хочу перечислить все из них.

Answer 1

Таким образом, типичное решение DP для этого будет производить массив, в котором вы знаете, какая самая длинная возможная подпоследовательность начинается с заданной позиции, скажем, у вас есть, и массив с длиной n, в котором dp [i] хранит длину самый длинный неубывающий подпоследовательность, начинающийся с элемента с индексом i.

Теперь распечатать все LNDSS (самые длинные неубывающие подпоследовательности) проще всего с помощью рекурсии. Сначала найдите фактическую длину LNDSS, выбрав значение смазки в dp. Затем запустите рекурсию для каждого элемента в dp, который имеет максимальное значение в dp (это может быть больше одного). Рекурсия по данному индексу должна печатать все последовательности, начиная с текущего индекса, длина которых равна значению dp [i]:

int st[1000];
int st_index
void rec(int index) {
  if (dp[index] == 1) {
    cout << "Another sequence:\n";
    for (int i = 0; i < st_index; ++i) {
      cout << st[i] << endl;
    }
  }
  for (int j = index + 1; j < n; ++j) {
    if (dp[j] == dp[index] - 1 && a[j] >= a[index]) {
      st[st_index++] = a[j];
      rec(j);
      st_index--;
    }
  }
}

Это пример кода на c ++ (надеюсь, он понятен и на других языках). У меня есть глобальный стек, называемый стеком, в котором хранятся элементы, которые мы уже добавили. Его размер 1000 предполагает, что в LNDSS никогда не будет более 1000 элементов, но это можно увеличить. Решение не имеет наилучшего возможного дизайна, но я сосредоточился на том, чтобы сделать его простым, а не хорошо спроектированным.

Надеюсь, это поможет.

Answer 2

В 2000 году Сергей Беспамятных и Майкл Сигал предложили алгоритм для нахождения всех наиболее длинных возрастающих подпоследовательностей данной перестановки. Алгоритм использует дерево Ван-Эмде Боаса и имеет временную сложность O (n + Kl (p)) и пространственную сложность O (n) , где n - длина перестановки p , l (p) - длина самой длинной увеличивающейся подпоследовательности, а K - это количество таких подпоследовательностей.

См. Документ в Цифровой библиотеке ACM или найдите в Интернете «Перечисление самых длинных увеличивающихся подпоследовательностей и сортировку терпения», чтобы получить бесплатный PDF.

Answer 3

Учитывая этот график, где все узлы связаны с узлами, которые имеют более высокое значение и появляются позже в последовательности букв вашей входной строки:

Вы хотитенайдите самый длинный путь от СТАРТА до КОНЦА.Это эквивалентно кратчайшему пути, если все сегменты имеют отрицательную длину -1.

Ссылка на проблему самого длинного пути: http://en.wikipedia.org/wiki/Longest_path_problem

Answer 4

Вы можете использовать возврат к списку всех подпоследовательностей.

Проверьте функцию printLIS, надеюсь, это поможет.

public class LIS {

    private static int[] count;

    public int longestIncreaseSubsequence(char[] seq) {
        int n = seq.length;

        for (int i = 0; i < n; i++) {
            count[i] = 1;
        }

        for (int i = 1; i < n; i++) {
            int max = 0;
            for (int j = i-1; j >= 0; j--) {
                if (seq[j] < seq[i]) max = Math.max(max, count[j]);
            }
            count[i] = max + 1;
        }

        int max = Integer.MIN_VALUE;
        for (int i = 0; i < count.length; i++) {
            if (count[i] > max) max = count[i];
        }

        return max;
    }

    public void printLIS(int[] a, int k, int[] count, char[] arr, int max) {
        if (k == max) {
            for (int i = max; i >= 1; i--) {
                System.out.printf("%c ", arr[a[i]]);
            }
            System.out.println();
        } else {
            k++;

            int[] candidates = new int[arr.length];
            int ncandidate = 0;

            for (int i = a[k-1]; i >= 0; i--) {
                if (count[i] == max-k+1 && (arr[i] < arr[a[k-1]] || count[i] == max)) {
                    candidates[ncandidate] = i;
                    ncandidate++;
                }
            }

            for (int i = 0; i < ncandidate; i++) {
                a[k] = candidates[i];
                printLIS(a, k, count, arr, max);
            }
        }
    }

    public static void main(String[] args) {
        char[] input = {'q','a','p','b','s','o','a'};
        LIS lis = new LIS();

        count = new int[input.length];  

        int max = lis.longestIncreaseSubsequence(input);
        int[] a = new int[max+1];
        a[0] = input.length-1; 

        lis.printLIS(a, 0, count, input, max);
    }
}