Pythonセット内の最小N個の連続した整数のリストを取得する最良の方法は何ですか？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)
[]
編集：回答ありがとうございます。
スヴェンは正しい考えを持っています。先に番号N - 1をチェックするだけで、スーパーセットをチェックする必要がなくなります。
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 []
これは常に入力としてセットについて正しいこととセットが整数のみが含まれていることを知っているだろう。
Nice :) 'xrange（len（lst） - Nm）'にする必要があります。 –
@スヴェーン、あなたは大丈夫です。良い発見。 –
これはいかがですか？
def smallest_contiguous(s, N):
lst = sorted(s)
for i in lst:
t = range(i, i+N)
if s.issuperset(t):
return t
return []
これは最も効率的な解決策ではないかもしれませんが、簡潔です。
編集：ジャスティンのアプローチは、より簡潔に行うことができます。
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 []
これはすべきです...並べ替えられたリストのlength - 1のステップを先に見てください。整数だけが含まれており、ソートされているので、差はlength - 1でなければなりません。
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 []
それは副作用として設定された入力を変更します。
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)
このコードは、実際にジャスティンのコードが元々持っていたものと同じoff-by-oneエラーを持っています。 'idxの範囲（0、len（myset） - length + 1）'でなければなりません。 –
あなたは正しい、thx。編集されました。とにかくコードに+/- 1の数が多すぎる...もう1つ。 –
は、ここで私が思いついた一つです。
これは、各反復で残りのセット全体を反復するので、O（n^2）です。もちろん、それは動作します。 –
@スヴェン、私はあなたが何を意味するか分かりません。それは、十分な長さの連続したブロックが見つかると停止します。 – user483263
はい、うまくいきます。私は[アルゴリズムの複雑さ]（http://en.wikipedia.org/wiki/Algorithmic_complexity）について話しています。大きなセットの場合、このアルゴリズムは他のどのアルゴリズムよりもはるかに効率が悪いです。 –
救助者へのitertools。 GROUPBYは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)
ソートするための呼び出しのアルゴリズムはO（nはLOGN）で、ここで すべての面倒な作業を行い、n個の項目に1となるように差分を確認してください。 – khachik
宿題に関する質問？ – troynt