Разделение на возрастающие подпоследовательности

16

Спецификация

Эта задача проста в утверждении: ваш ввод представляет собой непустой массив неотрицательных целых чисел, и ваша задача состоит в том, чтобы разбить его на как можно меньшее число увеличивающихся подпоследовательностей. Более формально, если входной массив есть A, то выходной это массив массивов, Bтакой что:

  • Каждый массив Bобразует разбиение Aна непересекающиеся (не обязательно смежные) подпоследовательности. Индуктивно это означает, что либо Bмассив синглтона содержит A, либо первый элемент Bявляется подпоследовательностью, Aа остальные образуют раздел Aс удаленной этой подпоследовательностью.
  • Каждый массив в B(не обязательно строго) увеличивается.
  • Количество массивов в Bминимально.

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

пример

Рассмотрим входной массив A = [1,2,1,2,5,4,7,1]. Одним из возможных выходных данных является B = [[1],[1,2,4,7],[1,2,5]]. Состояние раздела видно из этой диаграммы:

A    1 2 1 2 5 4 7 1
B[0]               1
B[1] 1 2       4 7
B[2]     1 2 5

Кроме того, каждый массив в Bувеличивается. Наконец, Aнельзя разбить на две возрастающие подпоследовательности, поэтому длина Bтакже минимальна. Таким образом, это действительный вывод.

Правила и оценки

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

Контрольные примеры

Отображается только один возможный вывод, но может быть несколько допустимых параметров. В частности, порядок массивов в результате не имеет значения (но каждый отдельный массив должен быть в порядке возрастания).

[0] -> [[0]]
[3,5,8] -> [[3,5,8]]
[2,2,2,2] -> [[2,2,2,2]]
[1154,1012,976,845] -> [[845],[976],[1012],[1154]]
[6,32,1,2,34,8] -> [[1,2,8],[6,32,34]]
[1,12,1,12,1,13] -> [[1,1,1,13],[12,12]]
[6,4,6,13,18,0,3] -> [[0,3],[4,6,13,18],[6]]
[1,2,3,2,3,4,7,1] -> [[1,1],[2,2,3,4,7],[3]]
[0,9,2,7,4,5,6,3,8] -> [[0,2,3,8],[4,5,6],[7],[9]]
[7,1,17,15,17,2,15,1,6] -> [[1,1,6],[2,15],[7,15,17],[17]]
[4,12,2,10,15,2,2,19,16,12] -> [[2,2,2,12],[4,10,15,16],[12,19]]
[10,13,9,2,11,1,10,17,19,1] -> [[1,1],[2,10,17,19],[9,11],[10,13]]
[3,7,3,8,14,16,19,15,16,2] -> [[2],[3,3,8,14,15,16],[7,16,19]]
[15,5,13,13,15,9,4,2,2,17] -> [[2,2,17],[4],[5,9],[13,13,15],[15]]
Zgarb
источник
3
Кажется, что правила разрешают подобные решения [0,5,2,0] -> [[0,5],[0,2]](т. Е. Рециркулируют первый ноль вместо того, чтобы использовать каждый из них один раз). Это намеренно?
feersum
@feersum Это было не намеренно, хороший улов. Я переписал условия B, надеюсь, теперь они понятнее.
Згарб

Ответы:

3

Haskell, 54 байта

n#[]=[[n]]
n#(l:c)|[n]<=l=(n:l):c|1<2=l:n#c
foldr(#)[]

Пример использования: foldr(#)[] [4,12,2,10,15,2,2,19,16,12]->[[2,2,2,12],[4,10,15,16],[12,19]]

Как это работает: просмотрите список ввода, начиная с правого конца. Создайте выходной список (списков), добавив текущий элемент nк первому подсписку, lгде nон меньше или равен заголовку l. Если их нет, создайте новый одноэлементный список nв конце списка вывода.

Ними
источник
1

Pyth, 20 байтов

fTu&ahfSI+THGHGQm[)Q

Попробуйте онлайн: демонстрация или тестовый набор

Жадный подход. Я создаю len(input)пустые списки. Затем я перебираю каждое число в inputсписке «Выбрать первый», который все еще сортируется после добавления номера.

Объяснение:

fTu&ahfSI+THGHGQm[)Q   implicit: Q = input list
                m[)Q   create a list of empty lists and assign to G
  u            Q       iterate over all numbers H in input:
      f     G             filter for lists T in G, which satisfy:
         +TH                 create a new list out of T and H
       SI                    and check if it is sorted
     h                    take the first such list T
    a        H            and append H
   &          G           logical and with G (so that u doesn't overwrite G)
fT                     remove all empty lists
Jakube
источник
@ThomasKwa В настоящее время протестировано немало дополнительных тестовых случаев. Не могу найти ни одного, который дает неправильный результат. Я совершенно уверен, что Жадность всегда возвращает правильный результат.
Якуб
@ThomasKwa О, этот контрпример был к другой жадной стратегии (найдите самую длинную увеличивающуюся подпоследовательность, удалите ее и рекурсивно). Я также не могу найти тестовый случай, для которого это представление не удается ...
Згарб
Ну, я думаю, что бремя лежит на ответчике, чтобы доказать, что это работает. Я буду голосовать, если это окажется действительным.
lirtosiast