Выберите элементы в последовательности

Question

Рассмотрим следующую проблему:

У меня есть последовательность с 2q элементы {a[1], ..., a[2q]}, который был отсортирован. Тогда мне нужно получить две подпоследовательности b[i] а также c[i], которые удовлетворяют:

1. И то и другое b[i] а также c[i] иметь q элементы и Join({b[i]}, {c[i]}) = {a[i]}
2. b[1] < b[2] <... < b[q]
3. b[i] < c[i] для всех i = 1...q

Сложность в том, что я хочу получить все последовательности, которые удовлетворяют условиям. Как я могу это сделать?

Answer 1

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

Переберите ввод от малого до большого; для каждого элемента выберите, входит ли он в подпоследовательность b или c, используя следующие правила:

• Если b и c имеют одинаковую длину, добавьте элемент в b.
• если b длиннее, чем c, добавьте элемент один раз к b и один раз к c и выполните возврат с обоими вариантами.
• Если b заполнен, добавьте все элементы в c.

Это даст нам номер, если разные разделы, например, для ввода [1,2,3,4,5,6] будут:

[1,2,3],[4,5,6]
[1,2,4],[3,5,6]
[1,2,5],[3,4,6]
[1,3,4],[2,5,6]
[1,3,5],[2,4,6]

Затем для каждого из этих разбиений мы должны найти перестановки c, которые удовлетворяют условиям. Опять же, простой рекурсивный метод сделает свое дело:

Переберите b справа налево. Для каждого элемента найдите элементы в c, которые больше. Если есть только один, поместите его в соответствующее место в c. Если есть суровые, поместите каждый из элементов в соответствующее место в c один раз, и повторите с каждым вариантом.

Для раздела [1,2,4],[3,5,6] в примере это привело бы к:

[1,2,4],[x,x,x] <- (3,5,6) ... [1,2,4],[x,x,6] <- (3,5) ... [1,2,4],[3,5,6]
     ^       ^          ^         ^       ^          ^
                           ... [1,2,4],[x,x,6] <- (3,5) ... [1,2,4],[5,3,6]
                                  ^       ^        ^
[1,2,4],[x,x,x] <- (3,5,6) ... [1,2,4],[x,x,5] <- (3,6) ... [1,2,4],[3,6,5]
     ^       ^        ^           ^       ^          ^
                           ... [1,2,4],[x,x,5] <- (3,6) ... [1,2,4],[6,3,5]
                                  ^       ^        ^

Этот пример кода является простой реализацией алгоритма, описанного выше:

function subsequences(a) {
    var q = a.length / 2;
    partition(0, [], []);

    function partition(pos, part1, part2) {
        var b = part1.slice();                  // create copy
        var c = part2.slice();                  // create copy
        if (b.length == c.length) {
            b.push(a[pos++]);
        }
        while (b.length < q) {
            c.push(a[pos++]);
            partition(pos, b, c);
            b.push(c.pop());
        }
        while (c.length < q) {
            c.push(a[pos++]);
        }
        permute(b, [], c);
    }

    function permute(b, part, set) {
        var pos = set.length - 1;
        for (var i = pos; i >= 0 && set[i] > b[pos]; i--) {
            var c = part.slice();               // create copy
            var s = set.slice();                // create copy
            c[pos] = s.splice(i, 1);
            if (pos == 0) {   // store or process subsequences
                document.write("{" + b + "},{" + c + "}<br>");
            }
            else permute(b, c, s);
        }
    }
}
subsequences([1,2,3,4,5,6,7,8,9,10,11,12]); // ascending order

Алгоритм находит следующее количество допустимых разделов и допустимых перестановок c. (Для сравнения я добавил количество всех разделов и всех перестановок, которые потребуется сгенерировать наивному решению, а затем проверить.)

 q  partitions     permutations     |   all part.        all perm.
                                    |
 1           1                1     |          1                1
 2           2                3     |          3                6
 3           5               15     |         10               60
 4          14              105     |         35              840
 5          42              945     |        126           15,120
 6         132           10,395     |        462          332,640
 7         429          135,135     |      1,716        8,648,640
 8       1,430        2,027,025     |      6,435      259,459,200
 9       4,862       34,459,425     |     24,310    8,821,612,800
10      16,796      654,729,075     |     92,378  335,221,286,400

Запустив только первую часть алгоритма, мы обнаружим, что для q=20 число допустимых разделов составляет 6 564 120 420, а число допустимых перестановок, вероятно, составляет около 10 ²².

---

ЗАМЕТКИ:

Для правильной работы функции разделения входная последовательность должна быть в порядке возрастания. В функции перестановки набор неиспользуемых значений в подпоследовательности c также сохраняется в порядке возрастания, чтобы упростить поиск самых больших значений.

Результаты для любой входной последовательности из n чисел будут одинаковыми. Фактически, вы можете заменить входную последовательность на [0,1,2,3 ... n-1], а затем использовать значения в результатах в качестве индексов в исходной входной последовательности. Это означает, что если вам нужны результаты для разных последовательностей из n чисел, вам нужно будет запустить алгоритм только один раз.