Comment trouver l'ensemble maximal d'éléments

14

J'ai un problème algorithmique.

Soit un tableau (ou un ensemble) de entiers non négatifs. Trouver l'ensemble maximal de tel que pour tout ,.TnSTuneSune|S|

Par exemple:

  1. Si T = [1, 3, 4, 1, 3, 6], alors S peut être [3, 3, 6] ou [3, 4, 6] ou [4, 3, 6].
  2. Dans = [7, 5, 1, 1, 7, 4], alors est [7, 5, 7, 4].STS

J'ai essayé cette fonction récursive.

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

Existe-t-il un algorithme non récursif. (Je n'ai pas vérifié mon algorithme récursif, donc il pourrait avoir un défaut.)

drzbir
la source

Réponses:

14

Triez T. Prenez ensuite des éléments tout en T[i] >= i+1.

Par exemple sorted(T)=[6,4,3,3,1,1]. Puis, T[0] = 6 > 1, T[1] = 4 > 2, T[2] = 3 <= 3et enfin, T[3] = 3 < 4nous avons donc S = [T[0], T[1], T[2]].

Karolis Juodelė
la source
3
Cela, bien sûr, manque l'autre solution , mais il semble que l'OP recherchait une solution, plutôt que toutes les solutions. {6,3,3}
Rick Decker
2
Il obtient le bon nombre d'éléments. Nous savons que nous avons des solutions à 3 éléments mais pas à 4; dans ce cas, nous avons 4 éléments ≥ 3, nous savons donc que nous pouvons en choisir 3 pour une solution.
gnasher729
3
J'apprécierais un argument de justesse.
Raphael
Je pense que vous pourriez probablement le faire en temps O (n) avec une variante d'introsélection.
user2357112 prend en charge Monica
8

D'après mon commentaire à l'origine: Ceci est étroitement lié à une quantité omniprésente dans l'évaluation de la productivité académique, l'indice de Hirsh, mieux connu sous le nom d' index h . En bref , il est défini comme le nombre de publications on a de telle sorte que chacun d'entre eux a au moins h citations (le plus grand tel h ).hhh

La seule façon dont votre problème diffère est que vous seriez intéressé non seulement par le nombre de publications qui satisfont au critère, mais également par leur nombre de citations , mais c'est une modification triviale. Les données sont déjà là, l'algorithme d'origine les supprime.

Le calcul généralement mis en œuvre est assez simple et correspond à la réponse de Karolis Juodelė .

Mise à jour: selon la taille et le caractère de vos données, il peut être utile d'explorer des méthodes qui trient partiellement le tableau en filtrant les données au-dessus et en dessous d'un point pivot (quicksort me vient à l'esprit). Ensuite, selon qu'il y en a trop ou trop peu, ajustez le pivot et refaites le sous-ensemble qui le contient et ainsi de suite. Vous n'avez pas besoin d'un ordre entre les éléments supérieurs à , et certainement pas entre ceux inférieurs à cela. Ainsi, par exemple, une fois que vous avez trouvé tous les éléments supérieurs ou égaux à h 1 et qu'il y en a moins de h 1 , vous n'avez plus besoin de toucher à ce sous-ensemble, il suffit de l'ajouter. Cela convertit la récursivité inhérente au tri rapide en une récursion de queue et peut donc être réécrite sous forme de boucle.hh1h1

Mon Haskell est un peu rouillé mais cela devrait faire ce que j'ai décrit ci-dessus et semble fonctionner. J'espère que cela peut être compris dans une certaine mesure, je suis heureux de fournir des explications supplémentaires.

-- 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 []

L'idée est de collecter grantedce que vous savez certainement participer au résultat, et de ne plus le trier. Si greateravec des xajustements, nous avons de la chance, sinon nous devons essayer avec un sous-ensemble plus petit. (Le pivot xest simplement ce qui s'est avéré être le premier élément de la sous-liste qui est actuellement considéré.) Notez que l'avantage significatif contre la prise d'éléments les plus grands un par un est que nous le faisons sur des blocs de taille moyenne et vous n'avez pas besoin de les trier davantage.remunejenjeng/2

Exemple:

Prenons votre ensemble [1,3,4,1,3,6].

  1. x = 1, granted = [], greater = [3,4,1,3,6]. Aïe, nous avons touché un cas pathologique lorsque le pivot est trop petit (en fait si petit qu'il smallerest vide) dès la première étape. Heureusement, notre algo est prêt pour cela. Il se défait xet essaie à nouveau avec greaterseul.

  2. x = 3, granted = [], greater = [4,3,6]. Ensemble, ils forment un tableau de longueur 4 mais nous n'avons que cela limité d'en bas par 3, c'est trop. Répétez greaterseul.

  3. x = 4, granted = [], greater = [6]. Cela donne un tableau de 2 éléments ≥ 4 chacun, semble que nous pourrions avoir besoin pour certains d'entre eux. Gardez cela et répétez smaller = [3].

  4. x = 3, granted = [4,6], greater = []. Cela donne ensemble un tableau de 3 éléments ≥ 3 chacun, nous avons donc notre solution [3,4,6]et nous pouvons revenir. (Notez que la permutation peut varier en fonction de l'ordre de l'entrée, mais contiendra toujours les termes les plus élevés possibles, jamais [3,3,6]ou [3,3,4]pour votre exemple.)

(En fait, notez que la récursivité s'est en effet effondrée en un cycle.) La complexité est légèrement meilleure que le tri rapide en raison des nombreuses comparaisons enregistrées:

n-1

O(Journaln)O(n)

nO(n2)

Il y a quelques comparaisons inutiles dans le code ci-dessus, comme calculer smallersi nous en avons besoin ou non, elles peuvent être facilement supprimées. (Je pense que l'évaluation paresseuse s'en occupera cependant.)

The Vee
la source
6

Il n'y a rien de mal avec votre algorithme, et bien sûr la plupart des algorithmes récursifs peuvent être convertis en boucles, voici une version en boucle de votre code récursif:

function(T):
    while minimum(T) <= lenght(T):
         remove minimum(T) from T
    loop
fernando.reyes
la source
6
Tous les algorithmes récursifs peuvent être convertis en boucles. Après tout, une machine de Turing ne sait rien de la récursivité.
David Richerby
4

Tout algorithme récursif peut être réécrit pour utiliser l'itération. Après tout, une machine de Turing ne sait rien de la récursivité mais peut implémenter n'importe quel algorithme. En principe, vous pouvez réécrire votre fonction récursive en écrivant votre propre code de manipulation de pile pour vous souvenir des valeurs des paramètres de la fonction et de toutes les variables locales qu'elle pourrait avoir. Dans ce cas particulier, votre fonction est récursive de queue (une fois qu'un appel récursif revient, la chose qui l'a appelée revient immédiatement aussi), vous n'avez donc même pas besoin de maintenir la pile.

David Richerby
la source
3

Utilisez un min-tas pour effectuer un tri partiel, car vous n'avez pas besoin de trier l'ensemble du tableau.

Continuez à faire sauter les éléments avec avidité jusqu'à ce que vous dépassiez le seuil indiqué.

user541686
la source
2
Ici aussi, j'apprécierais une idée de l'exactitude.
Raphael