シーケンスから最大長のサブシーケンスを抽出する[PYTHON]

Question

値のシーケンス[1,2,3,4,1,5,1,6,7]があります。長さが長くなる。しかし、関数は以前の数よりも低い数に達するとカウントを停止する必要があります。この場合の答えは[1,2,3,4]です。それはリセットされる前に4つの値を持っています。このためにPythonコードを書くにはどうすればいいですか？

注：「最も長くなる部分配列」を見つけることは一般的な課題であると思われます。オンラインで検索すると、配列全体の長さを数える数多くの解決策が見つかり、この場合、[1,2,3,4,5,6,7]が返されます。それは私が探しているものではありません。

各サブシーケンスを数え、以前の数よりも小さい数に達するとカウントをリセットする必要があります。カウントされたすべてのサブシーケンスを比較し、最も長いシーケンスを返す必要があります。

ありがとうございます。

Answer 1

b = [4,1,6,3,4,5,6,7,3,9,1,0] 

def findsub(a): 
    start = -1 
    count = 0 
    cur = a[0] 
    for i, n in enumerate(a): 
    if n is cur+1: 
     if start is -1: 
     start = i - 2 
     count=1 
     count+=1 
     cur = n 
    if n < cur and count > 1: 
     return [a[j] for j in range(start,start+count+1)] 


print findsub(b) 

これはやや汚いアルゴリズムですが、私はそれがあなたの望むことを信じています。通常、私は単にあなたにコードを示しただけではありませんでしたが、それがあなたが望むものだと思われます。あなたがそれから学び、あなたが学んだことからあなた自身のものを作り出せることを願っています。

わずかに良い探し方法私は好きではなかったので：あなたは次の操作を行う必要があり

b = [1,2,0,1,2,3,4,5] 

def findsub(a): 
    answer = [a[0]] 
    for i in a[1:]: 
    if answer[-1] + 1 is i: 
     answer.append(i) 
    if not len(answer) > 1: 
     answer = [i] 
    elif i < answer[-1] and len(answer) > 1: 
     return answer 
    return answer 



print findsub(b) 

Answer 2

：

1. リストを与えられた機能Wを作成し、インデックスを返します。リストの先頭から厳密には増加していない最後の項目の例えば

   • 、次のリスト与えられた：[1,2,3,4,1,2,3], [4,2,1], [5,6,7,8]、それは

2. が変数maximを作成し、各リストについては、それぞれ、4、1、4を返し、0

3. に値を設定する必要がありますあなたのリストが空になるまで、繰り返し以下を実行してください。
   • あなたのリストにあなたの関数Wを呼び出し、xはmaxim
     • あなたはこのシーケンスを保存したい場合は、あなたが使用することができます。この時点でx
     • にmaximを設定するよりも大きい場合のはx
     • 戻り値を呼びましょうlist-slice notationは、シーケンスを含むリストのその部分を取得します。
   • リストから最後

、印刷maximをあなたのリストのその部分を削除し、あなたが最も長い配列を含むあなたのリストの一部を格納した場合、その後、あなたが得た最後のものを印刷

Answer 3

すべての可能な昇順サブシーケンスを生成する関数を考えてください。空のリストから始め、1つの要素がより少なくなるまで（または？に等しい）アイテムを追加します。新しいサブシーケンスを持つエスタット。

発電機を使用して一つの実装は、この可能性が

：空のシーケンスの取扱いに関する

def all_ascending_subsequences(sequence): 
    #use an iterator so we can pull out the first element without slicing 
    seq = iter(sequence) 

    try: #NOTE 1 
     last = next(seq) # grab the first element from the sequence 
    except StopIteration: # or if there are none just return 
     #yield [] #NOTE 2 
     return 

    sub = [last] 
    for value in seq: 
     if value > last: #or check if their difference is exactly 1 etc. 
      sub.append(value) 
     else: #end of the subsequence, yield it and reset sub 
      yield sub 
      sub = [value] 
     last = value 

    #after the loop we send the final subsequence 
    yield sub 

2つのノート：

1. たちはちょうどことができるように上げることが発電機にStopIterationニーズを完了するためにnext(seq)の報奨を控除してください。from __future__ import generator_stopが の場合、それはRuntimeErrorとなりますので、将来的には互換性があります。 が必要ですそれをキャッチして明示的にreturn。
2. 私が書いたように、空リストを all_ascending_subsequencesに渡すと、値が生成されず、 が望ましい動作になることがあります。 yield []〜 のコメントを解除すると、空のリストが渡されたときに空のリストが生成されます。

次に、あなただけの、あなたはそれを解決しようとしましたが、これは非常に簡単なアルゴリズムワイズ思わkey=len

b = [1,2,3,4,1,5,1,6,7] 

result = max(all_ascending_subsequences(b),key=len) 
print("longest is", result) 

#print(*all_ascending_subsequences(b))