Минимизировать количество последовательных разделов списка
Имея список целых чисел, я пытаюсь подсчитать, на сколько разделов должен быть разделен список, чтобы каждый подсписок следовал последовательному порядку +1 или -1 (или состоял только из 1 элемента). Примеры допустимых подсписков: [1], [1,2,3,4], [9,8,7]. Примеры недопустимых подсписков: [1,3], [5,4,5]. Очевидно, что список всегда можно разделить на разделы, содержащие только одно значение в каждом, но цель состоит в том, чтобы свести к минимуму количество разделов.
Например:
Мы можем разделить [2,1,2,3,3,2,6,7,8] на эти подсписки: [2,1], [2,3], [3,2], [6,7,8], всего 4 подсписка. Обратите внимание, что деление также могло быть [2], [1,2,3], [3,2], [6,7,8], но это не имеет значения для ожидаемого результата: 4.
Вот еще несколько примеров:
[1,2,3,2,1,6,8][1,2,3],[2,1],[6],[8] или [1,2],[3,2,1],[6],[8]
4
[1,2,1,1][1,2],[1],[1] или [1],[2,1],[1]
3
[1,2,1][1,2],[1] или [1],[2,1]
2
[1,1,1][1],[1],[1]
3
[1,2,3,5,2,3][1,2,3],[5],[2,3]
3
[1,2,3,2,3,2,1][1,2,3],[2,3],[2,1] или [1,2],[3,2],[3,2,1]
3
[]
-
0
[5][5]
1
[5,5,6,6][5],[5,6],[6]
3
Итак, я посмотрел на различия между двумя последовательными элементами в списке:
mylist = [2,1,2,3,3,2,6,7,8]
diff = []
for i in range(len(mylist)-1):
diff.append(mylist[i+1]- mylist[i])
# diff = [-1, 1, 1, 0, -1, 4, 1, 1]
Есть точки поворота, такие как от -1 до 1, или от 1 до 0, или от 0 до -1 (этот не считается), от -1 до 4, от 4 до 1 (этот не считается), так что всего 5 поворотных точек, а две не надо считать: итак 3 поворотных, значит 4 перегородки.
Мне нужно считать поворотные моменты, но явно не все. Как я могу различать поворотные точки, чтобы учитывать только те, которые необходимы для минимизации количества действительных разделов?
А перекрытия? Каким будет результат для [1,2,1]? Согласно вашим примерам (которые не учитывают перекрытия), результатом будет [1,2], общее число 1. Но не будет ли [1,2],[2,1], общее число 2 более точным?
@treuss, общее число должно быть 2; [1,2], [1] или [1], [2,1]
Было бы очень полезно иметь все ваши примеры в виде кода для тестирования функции, которая выполняет эту работу (вот так).
Ответы 1
Самый простой способ сделать это и убедиться, что это работает, — это динамическое программирование.
Для каждого элемента x вы вычисляете минимальное количество разделов списка до x так, чтобы:
- вы можете добавить
x+1к последнему разделу - вы можете добавить
x-1к последнему разделу
Их легко вычислить для каждого x, если вы знаете значения для предыдущего:
def partitionCount(list):
if len(list) < 2:
return len(list)
# minimum # of partitions such that you can append increasing
partup = 1
# minimum # of partitions such that you can append decreasing
partdown = 1
for i in range(1, len(list)):
diff = list[i] - list[i-1]
if diff == 1:
# partup is unchanged
partdown = min(partdown,partup) + 1
elif diff == -1:
# partdown is unchanged
partup = min(partdown,partup) + 1
else:
partdown = min(partdown,partup) + 1
partup = partdown
return min(partup, partdown)
Может быть, это только я, но я нахожу это довольно загадочным :-). Я думаю, что у меня проще, но, возможно, это тоже DP (еще не опубликовано, все еще жду, пока они добавят тестовый код).
@KellyBundy Я подозреваю, что в вашем решении используются две переменные состояния: count и direction, где direction — по возрастанию, по убыванию или не указано. Этот код также использует две переменные состояния: partup и partdown. Это работает, потому что в конце каждой итерации цикла: count = min(partup, partdown) и direction = partup - partdown. Этот код менее загадочен, если вы понимаете, что partup - partdown всегда находится в {-1, 0, 1} и, таким образом, эквивалентен переменной состояния direction. Так что это на самом деле ничем не отличается от (как я предполагаю) вашего решения, и это не DP.
Это почти так, да. И да, я согласен, что ваш вариант похож, но два отдельных подсчета, не то чтобы явно связанные, и один из них несколько «предварительно подсчитывает» будущие события, затрудняют понимание для меня. И да, я бы скорее назвал свой жадным, а не DP, хотя я нахожу различие размытым.
Преимущество оформления решения как решения DP состоит в том, что вам не нужно доказывать, что жадное решение работает... или, скорее, решение DP является доказательством того, что оно работает.
Хм, я не согласен. Если я поменяю ваш + 1 на + 2, это все равно будет DP, но неправильно, поэтому наличие DP не является доказательством.
Справедливо. Доказательство есть доказательство только для тех, кто это понимает :)
Что вы пробовали до сих пор, что не работает?