У меня есть алгоритмическая проблема.
Дан массив (или набор) из неотрицательных целых чисел. Найти максимальное множество из , что для всех ,,н S
Например:
- Если = [1, 3, 4, 1, 3, 6], то может быть [3, 3, 6] или [3, 4, 6] или [4, 3, 6].
- В = [7, 5, 1, 1, 7, 4], тогда равно [7, 5, 7, 4].
Я пробовал эту рекурсивную функцию.
function(T):
if minimum(T) >= length(T):
return T
else:
return function(T\minimum(T))
Есть ли какой-нибудь нерекурсивный алгоритм. (Я не проверял свой рекурсивный алгоритм, поэтому он может иметь некоторые недостатки.)
algorithms
optimization
sets
drzbir
источник
источник
Из моего комментария: «Это тесно связано с количеством, повсеместным в оценке академической производительности, индексом Хирша, более известным как -индексчас . Вкратце она определяется как число публикаций приходится таким образом, что каждый из них имеет по крайней мере час цитат (самый большой такой час ).час час час
Единственное, чем отличается ваша проблема, это то, что вас будет интересовать не только количество публикаций, удовлетворяющих этому критерию, но и количество их цитирований , но это тривиальная модификация. Данные уже есть, оригинальный алгоритм просто сбрасывает их.
Общепринятый расчет довольно прост и согласуется с ответом Каролис Юоделе .
Обновление: в зависимости от размера и характера ваших данных, возможно, стоит изучить методы, которые частично сортируют массив путем фильтрации данных выше и ниже центральной точки (на ум приходит быстрая сортировка). Затем, в зависимости от того, слишком мало или слишком много, отрегулируйте опору и повтор на подмножестве, которое его содержит, и так далее. Вам не нужен порядок между элементами выше , и уж точно не между элементами ниже этого. Так, например, как только вы нашли все элементы, большие или равные h 1 и их меньше h 1 , вам не нужно снова прикасаться к этому подмножеству, просто добавьте к нему. Это преобразует рекурсию, присущую быстрой сортировке, в хвостовую рекурсию и, таким образом, может быть переписано как цикл.час час1 час1
Мой Haskell немного заржавел, но это должно сделать то, что я описал выше, и, кажется, работает. Надеюсь, что это может быть понято до некоторой степени, я рад предоставить дополнительные объяснения.
Идея состоит вг е м а я п я п г/ 2
granted
том, чтобы собрать то, что, как вы знаете, обязательно примет участие в результате, а не сортировать его дальше. Еслиgreater
вместе сx
припадками нам повезло, в противном случае нам нужно попробовать с меньшим подмножеством. (Стерженьx
просто все , что случилось с первым пунктом подсписка , который в настоящее время рассматривается.) Следует отметить , что значительное преимущество против принятия крупнейших элементов , один за другим, что мы делаем это на блоках среднего размера и не нужно сортировать их дальше.Пример:
Давайте возьмем ваш набор
[1,3,4,1,3,6]
.x = 1
,granted = []
,greater = [3,4,1,3,6]
. Ой, мы встречаемся с патологическим случаем, когда стержень слишком мал (на самом деле настолько мал, чтоsmaller
пуст) прямо на первом шаге. К счастью, наш алгоритм готов к этому. Он сбрасываетx
и пытается снова сgreater
одним.x = 3
,granted = []
,greater = [4,3,6]
. Вместе они образуют массив длиной 4, но у нас только это ограничено снизу 3, так что это слишком много. Повторите вgreater
одиночку.x = 4
,granted = []
,greater = [6]
. Это дает массив из 2 элементов ≥ 4 каждый, кажется, мы могли бы использовать еще для некоторых из них. Сохраните это и повторитеsmaller = [3]
.x = 3
,granted = [4,6]
,greater = []
. Это вместе дает массив из 3 элементов ≥ 3 каждый, поэтому у нас есть решение,[3,4,6]
и мы можем вернуться. (Обратите внимание, что перестановка может варьироваться в зависимости от порядка ввода, но всегда будет содержать максимально возможные термины, никогда[3,3,6]
или[3,3,4]
для вашего примера.)(Кстати, обратите внимание, что рекурсия действительно просто свернулась в цикл.) Сложность несколько лучше, чем быстрая сортировка из-за многих сохраненных сравнений:
В приведенном выше коде есть несколько ненужных сравнений, например, вычисление
smaller
того, нужен он нам или нет, их можно легко удалить. (Я думаю, что ленивая оценка позаботится об этом, хотя.)источник
В вашем алгоритме нет ничего плохого, и, конечно, большинство рекурсивных алгоритмов могут быть преобразованы в циклы, вот версия цикла вашего рекурсивного кода:
источник
Любой рекурсивный алгоритм может быть переписан для использования итерации. В конце концов, машина Тьюринга ничего не знает о рекурсии, но может реализовать любой алгоритм. В принципе, вы можете переписать свою рекурсивную функцию, написав свой собственный код манипулирования стеком, чтобы запомнить значения параметров функции и любые локальные переменные, которые она может иметь. В этом конкретном случае ваша функция является хвост-рекурсивной (когда возвращается рекурсивный вызов, то, что вызвало ее, тоже немедленно возвращается), так что вам даже не нужно поддерживать стек.
источник
Используйте минимальную кучу, чтобы выполнить частичную сортировку, так как вам не нужно сортировать весь массив.
Продолжайте жадно высовывать элементы, пока не превысите указанный порог.
источник