-3

値のシーケンス [1,2,3,4,1,5,1,6,7] があり、長さが増加する最長のサブシーケンスを見つける必要があります。ただし、関数は、前の数値よりも低い数値に達したらカウントを停止する必要があります。その場合のこのシーケンスの答えは [1,2,3,4] です。リセットされる前に4つの値があるため。このための Python コードをどのように記述すればよいでしょうか?

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

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

前もって感謝します。

4

3 に答える 3

1

可能なすべての昇順のサブシーケンスを生成する関数を考えてみましょう。空のリストから始めて、1 つの要素が前の要素よりも小さくなる (または等しくなる) までアイテムを追加し、その時点でサブシーケンスを保存 ( yield) し、新しいサブシーケンスで再開します。

ジェネレーターを使用した 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 []空のリストが渡されたときに空のリストを生成するには、自由にコメントを外してください。

max次に、次のように結果を呼び出すことで、最長を取得できます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))
于 2016-11-18T23:08:57.367 に答える
0 
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)
于 2016-11-18T01:16:36.520 に答える
0

次のことを行う必要があります。

  1. Wリストを指定して、リストの先頭から厳密に増加していない最後の項目のインデックスを返す関数を作成します。

    • たとえば、次のリストが与えられた場合: 、各リストに対してそれぞれ、、[1,2,3,4,1,2,3], [4,2,1], [5,6,7,8]を返す必要があります。414

  2. 変数maximを作成し、値を0

  3. リストが空になるまで、次の操作を繰り返します
    • リストで関数Wを呼び出し、戻り値を呼び出しましょうx
    • xより大きい場合maxim
      • maximに設定x
      • この時点で、このシーケンスを保存したい場合は、リスト スライス表記を使用して、シーケンスを含むリストの部分を取得できます。
    • あなたのリストのその部分をリストから削除してください

最後にmaxim、最も長いシーケンスを含むリストの部分を保存していた場合は、最後に取得したものを印刷します

于 2016-11-18T01:58:44.880 に答える