Jak znaleźć maksymalny zestaw elementów tablicy tak, że każdy element w jest większy lub równy liczności ?

Mam problem z algorytmem.

Biorąc pod uwagę macierz (lub zestaw) o nieujemne liczby całkowite. Znajdź maksymalny zestaw z tak że dla wszystkich ,.$T$$n$$S$$T$$a\in S$$a\geqslant |S|$

Na przykład:

1. Jeśli $T$ = [1, 3, 4, 1, 3, 6], wówczas $S$ może być [3, 3, 6] lub [3, 4, 6] lub [4, 3, 6].
2. W = [7, 5, 1, 1, 7, 4], wówczas wynosi [7, 5, 7, 4].$T$$S$

Próbowałem tej funkcji rekurencyjnej.

function(T):
    if minimum(T) >= length(T): 
        return T
    else: 
        return function(T\minimum(T))

Czy istnieje jakiś algorytm nierekurencyjny. (Nie sprawdziłem mojego algorytmu rekurencyjnego, więc może mieć pewną wadę).

Sortuj T. Następnie weź elementy podczas T[i] >= i+1.

Na przykład sorted(T)=[6,4,3,3,1,1]. Następnie T[0] = 6 > 1, T[1] = 4 > 2, T[2] = 3 <= 3a na końcu, T[3] = 3 < 4więc mamy S = [T[0], T[1], T[2]].

Z mojego komentarza pierwotnie: Jest to ściśle związane z wszechobecnym ilość w akademickiego oceny produktywności, indeks Hirsh, lepiej znany jako -index$h$ . W skrócie jest zdefiniowany jako liczba publikacji ma się tak, że każdy z nich ma co najmniej h cytowań (największy taki h ).$h$$h$$h$

Twój problem różni się tylko tym, że interesowałbyś się nie tylko liczbą publikacji spełniających to kryterium, ale także liczbą ich cytowań , ale to banalna modyfikacja. Dane już tam są, oryginalny algorytm po prostu je upuszcza.

Ogólnie stosowane obliczenia są dość proste i zgadzają się z odpowiedzią Karolis Juodelė .

Aktualizacja: W zależności od wielkości i charakteru danych warto zbadać metody, które częściowo sortują tablicę, filtrując dane powyżej i poniżej punktu kluczowego (przychodzi na myśl szybkie sortowanie). Następnie w zależności od tego, czy jest za mało, czy za dużo, dostosuj oś obrotu i ponów w podzbiorze, który ją zawiera i tak dalej. Nie potrzebujesz kolejności między elementami wyższymi niż , a na pewno nie między tymi niższymi. Na przykład, gdy znajdziesz wszystkie elementy większe lub równe h 1 i jest ich mniej niż h 1 , nie musisz ponownie dotykać tego podzbioru, po prostu dodaj go. Konwertuje to rekurencję związaną z Quicksort na rekurencję ogona, a zatem może być przepisana jako pętla.$h$$h_1$$h_1$

Mój Haskell jest trochę zardzewiały, ale powinno to zrobić to, co opisałem powyżej i wydaje się działać. Mam nadzieję, że do pewnego stopnia można to zrozumieć, chętnie udzielę dalszych wyjaśnień.

-- just a utility function
merge :: [a] -> [a] -> [a]
merge [] ys = ys
merge (x:xs) ys = x : merge xs ys

-- the actual implementation
topImpl :: [Int] -> [Int] -> [Int]
topImpl [] granted = granted
topImpl (x:xs) granted
  | x == (1 + lGreater + lGranted) = x : merge greater granted
  | x > (1 + lGreater + lGranted) = topImpl smaller (x : merge greater granted)
  | otherwise = topImpl greater granted
  where smaller = [y | y <- xs, y < x]
        greater = [y | y <- xs, y >= x]
        lGreater = length greater
        lGranted = length granted

-- starting point is: top of whole array, granted is empty
top :: [Int] -> [Int]
top arr = topImpl arr []

Chodzi o to, aby zebrać grantedto, co wiesz, na pewno będzie uczestniczyć w wyniku, a nie sortować go dalej. Jeśli greaterrazem z xpasowaniem mamy szczęście, w przeciwnym razie musimy spróbować z mniejszym podzbiorem. (Czop xjest po prostu cokolwiek stało się pierwsza pozycja w podmenu, który jest aktualnie rozpatrywana.) Należy zauważyć, że znacząca zaleta przed sobą największe elementy jeden po drugim jest to, że robimy to na blokach średniej wielkości i nie trzeba ich dalej sortować.$remaining/2$

Przykład:

Weźmy twój zestaw [1,3,4,1,3,6].

1. x = 1, granted = [], greater = [3,4,1,3,6]. Ojej, trafiliśmy na przypadek patologiczny, gdy oś jest za mała (właściwie tak mała, że smallerjest pusta) już na pierwszym etapie. Na szczęście nasze algo jest na to gotowe. Odrzuca xi próbuje ponownie greatersam.

2. x = 3, granted = [], greater = [4,3,6]. Razem tworzą tablicę o długości 4, ale ograniczamy ją tylko od dołu o 3, więc to za dużo. Powtórz greatersam.

3. x = 4, granted = [], greater = [6]. Daje to tablicę zawierającą 2 elementy ≥ 4 każdy, wydaje się, że moglibyśmy użyć trochę więcej. Zachowaj to i powtarzaj dalej smaller = [3].

4. x = 3, granted = [4,6], greater = []. To razem daje tablicę 3 elementów ≥ 3 każdy, więc mamy nasze rozwiązanie [3,4,6]i możemy wrócić. (Pamiętaj, że permutacja może się różnić w zależności od kolejności wprowadzania danych, ale zawsze będzie zawierać najwyższe możliwe warunki, nigdy [3,3,6]lub [3,3,4]w twoim przykładzie).

(Przy okazji zauważmy, że rekurencja rzeczywiście po prostu zapadła się w cykl.) Złożoność jest nieco lepsza niż szybkie sortowanie z powodu wielu zapisanych porównań:

$n-1$

$O(\log n)$$O(n)$

$n$$O(n^2)$

W powyższym kodzie znajduje się kilka niepotrzebnych porównań, takich jak obliczenie, smallerczy jest to potrzebne, czy nie, można je łatwo usunąć. (Myślę, że leniwa ocena to załatwi.)

Nie ma nic złego w twoim algorytmie i oczywiście większość algorytmów rekurencyjnych można przekształcić w pętle, tutaj wersja pętli twojego kodu rekurencyjnego:

function(T):
    while minimum(T) <= lenght(T):
         remove minimum(T) from T
    loop

Każdy algorytm rekurencyjny można przepisać, aby użyć iteracji. W końcu maszyna Turinga nic nie wie o rekurencji, ale może zaimplementować dowolny algorytm. Zasadniczo możesz przepisać swoją funkcję rekurencyjną, pisząc własny kod manipulacji stosem, aby zapamiętać wartości parametrów funkcji i wszelkich lokalnych zmiennych, które może mieć. W tym konkretnym przypadku twoja funkcja jest rekurencyjna (po powrocie wywołania rekurencyjnego wraca też rzecz, która go wywołała), więc nie musisz nawet utrzymywać stosu.

Użyj mini-sterty, aby wykonać częściowy rozsypisko, ponieważ nie potrzebujesz sortować całej tablicy.

Trzymaj łapczywie elementy, dopóki nie przekroczysz podanego progu.