Quel est le meilleur moyen d'obtenir une liste des N entiers contigus les plus petits dans un ensemble Python?Recherche des plus petits entiers contigus dans un ensemble Python
>>> s=set([5,6,10,12,13,15,30,40,41,42,43,44,55,56,90,300,500])
>>> s
set([42, 43, 44, 5, 6, 90, 300, 30, 10, 12, 13, 55, 56, 15, 500, 40, 41])
>>> smallest_contiguous(s,5)
[40,41,42,43,44]
>>> smallest_contiguous(s,6)
[]
Modifier: Merci pour les réponses, tout le monde.
Sven a la bonne idée. Vous pouvez éviter de devoir vérifier les supersets en vérifiant simplement le nombre N - 1 devant.
def smallest_contiguous(s, N):
lst = list(s)
lst.sort()
Nm = N-1
for i in xrange(len(lst) - Nm):
if lst[i] + Nm == lst[i + Nm]:
return range(lst[i], lst[i]+N)
return []
Ceci ne sera toujours correct que pour un ensemble en entrée et sachant que l'ensemble ne contient que des entiers.
Nice :) Devrait être 'xrange (len (lst) - Nm)' Je pense. –
@Sven, vous avez raison. Bonne trouvaille. –
Que pensez-vous de cela?
def smallest_contiguous(s, N):
lst = sorted(s)
for i in lst:
t = range(i, i+N)
if s.issuperset(t):
return t
return []
Ce n'est peut-être pas la solution la plus efficace, mais elle est concise.
Edit: l'approche de Justin pourrait aussi être plus concise:
def smallest_contiguous(s, N):
lst = sorted(s)
for a, b in zip(lst, lst[N - 1:]):
if b - a == N - 1:
return range(a, b + 1)
return []
Cela devrait le faire ... regarder en avant length - 1 étapes dans la liste triée. Comme il ne contient que des entiers et qu'il est trié, la différence doit également être length - 1.
def smallest_contiguous(myset, length):
if len(myset) < length:
return []
s = sorted(myset)
for idx in range(0, len(myset) - length + 1):
if s[idx+length-1] - s[idx] == length - 1:
return s[idx:idx+length]
return []
s=set([5,6,10,12,13,15,30,40,41,42,43,44,55,56,90,300,500])
print smallest_contiguous(s, 5)
print smallest_contiguous(s, 6)
Ce code a en fait la même erreur off-one que le code de Justin à l'origine. Devrait être 'pour idx dans la gamme (0, len (myset) - longueur + 1)'. –
Vous avez raison, merci. Édité. Trop de +/- 1 dans le code de toute façon ... un de plus maintenant. –
est ici que je suis venu avec:
def smallest_contiguous(s,N):
try:
result = []
while len(result) < N:
min_value = min(s)
s.remove(min_value)
if result == [] or min_value == result[-1] + 1:
result.append(min_value)
else:
result = [min_value]
return result
except ValueError:
return []
Il modifie l'ensemble d'entrée comme un effet secondaire.
Ceci réitérera l'entier restant dans chaque itération, donc c'est O (n^2). Mais bien sûr, cela fonctionne. –
@Sven, je ne suis pas sûr de ce que vous voulez dire. Il s'arrête quand il trouve le bloc contigu de longueur suffisante. – user483263
Oui, cela fonctionne très bien. Je parle de [complexité algorithmique] (http://en.wikipedia.org/wiki/Algorithmic_complexity): pour les grands ensembles, cet algorithme est beaucoup moins efficace que les autres. –
itertools à la rescousse. groupby fait tout le travail de grognement ici L'algorithme est O (n log n) en raison de l'appel à sorted()
>>> from itertools import groupby, count
>>> def smallest_contiguous(s, N):
... for i,j in groupby(sorted(s), key=lambda i,c=count().next: i-c()):
... res = list(j)
... if len(res) == N:
... return res
... return []
...
>>> smallest_contiguous(s,5)
[40, 41, 42, 43, 44]
>>> smallest_contiguous(s,6)
[]
def smallest_contiguous(s, n):
xs = sorted(s)
return next(x for i, x in enumerate(xs) if xs[i + n - 1] == x + n - 1)
tri et de vérifier diff à 1 sur les points n. – khachik
Question de devoirs? – troynt