Первый шаг - разделить входные данные на две половины, убедившись, что каждый раздел приведет к решению.Мы можем сделать это с помощью простого рекурсивного метода:
Перебирать ввод от малого до большого;для каждого элемента выберите, входит ли он в подпоследовательность 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 22 * 1034 *.
ПРИМЕЧАНИЯ:
Чтобы функция разделения работала правильно, последовательность ввода должна быть в порядке возрастания.В функции перестановки набор неиспользуемых значений в подпоследовательности c также сохраняется в порядке возрастания, чтобы упростить поиск самых больших значений.
Результаты для любой входной последовательности из n чисел будут аналогичными.Фактически, вы можете заменить входную последовательность на [0,1,2,3 ... n-1], а затем использовать значения в результатах в качестве индексов в исходной входной последовательности.Это означает, что если вам нужны результаты для разных последовательностей из n чисел, вам нужно всего лишь один раз запустить алгоритм.