znaleźć pozycję początkową najdłuższej sekwencji 1-

Question

Chcę znaleźć pozycję początkową najdłuższej sekwencji 1 w moim tablicy:

a1=[0,0,1,1,1,1,0,0,1,1] 
#2 

śledzę ten answer znaleźć długość najdłuższej sekwencji . Jednak nie byłem w stanie określić pozycji.

Answer 1

Zainspirowany this solution, oto wektorowy podejście, aby go rozwiązać -

# Get start, stop index pairs for islands/seq. of 1s 
idx_pairs = np.where(np.diff(np.hstack(([False],a1==1,[False]))))[0].reshape(-1,2) 

# Get the island lengths, whose argmax would give us the ID of longest island. 
# Start index of that island would be the desired output 
start_longest_seq = idx_pairs[np.diff(idx_pairs,axis=1).argmax(),0] 

run

Sample -

In [89]: a1 # Input array 
Out[89]: array([0, 0, 1, 1, 1, 1, 0, 0, 1, 1]) 

In [90]: idx_pairs # Start, stop+1 index pairs 
Out[90]: 
array([[ 2, 6], 
     [ 8, 10]]) 

In [91]: np.diff(idx_pairs,axis=1) # Island lengths 
Out[91]: 
array([[4], 
     [2]]) 

In [92]: np.diff(idx_pairs,axis=1).argmax() # Longest island ID 
Out[92]: 0 

In [93]: idx_pairs[np.diff(idx_pairs,axis=1).argmax(),0] # Longest island start 
Out[93]: 2 

Answer 2

Można użyć pętli for i sprawdzić, czy w najbliższych przedmioty (o długości m gdzie m jest długość max) są takie same jak maksymalna długość:

# Using your list and the answer from the post you referred 
from itertools import groupby 
L = [0,0,1,1,1,1,0,0,1,1] 
m = max(sum(1 for i in g) for k, g in groupby(L)) 
# Here is the for loop 
for i, s in enumerate(L): 
    if len(L) - i + 2 < len(L) - m: 
     break 
    if s == 1 and 0 not in L[i:i+m]: 
     print i 
     break 

To da:

2 

Answer 3

To wydaje się działać, wykorzystując groupby od itertools, to tylko przechodzi listy raz:

from itertools import groupby 

pos, max_len, cum_pos = 0, 0, 0 

for k, g in groupby(a1): 
    if k == 1: 
     pat_size = len(list(g)) 
     pos, max_len = (pos, max_len) if pat_size < max_len else (cum_pos, pat_size) 
     cum_pos += pat_size 
    else: 
     cum_pos += len(list(g)) 

pos 
# 2 
max_len 
# 4 

Answer 4

Innym sposobem robi w pojedynczej pętli, ale bez uciekania się do itertool 's groupby.

max_start = 0 
max_reps = 0 
start = 0 
reps = 0 
for (pos, val) in enumerate(a1): 
    start = pos if reps == 0 else start 
    reps = reps + 1 if val == 1 else 0 
    max_reps = max(reps, max_reps) 
    max_start = start if reps == max_reps else max_start 

To może być również wykonane w sposób jedno-liner użyciu reduce:

max_start = reduce(lambda (max_start, max_reps, start, reps), (pos, val): (start if reps == max(reps, max_reps) else max_start, max(reps, max_reps), pos if reps == 0 else start, reps + 1 if val == 1 else 0), enumerate(a1), (0, 0, 0, 0))[0] 

W Pythonie 3, nie można rozpakować krotki wewnątrz definicji lambda argumenty, więc lepiej jest zdefiniować funkcję używając def pierwszy:

def func(acc, x): 
    max_start, max_reps, start, reps = acc 
    pos, val = x 
    return (start if reps == max(reps, max_reps) else max_start, 
      max(reps, max_reps), 
      pos if reps == 0 else start, 
      reps + 1 if val == 1 else 0) 

max_start = reduce(func, enumerate(a1), (0, 0, 0, 0))[0] 

W każdym z trzech przypadków max_start daje odpowiedź (tj 2).

Answer 5

Bardziej kompaktowa jednopanelowa przy użyciu groupby(). Używa enumerate() na surowych danych, aby utrzymać pozycje początkowe przez potok analizy, nawet kończąc na liście krotek [(2, 4), (8, 2)] każdej krotce zawierającej pozycję początkową i długość niezerowych przebiegów :

from itertools import groupby 

L = [0,0,1,1,1,1,0,0,1,1] 

print max(((lambda y: (y[0][0], len(y)))(list(g)) for k, g in groupby(enumerate(L), lambda x: x[1]) if k), key=lambda z: z[1])[0] 

lambda: x jest funkcyjny dla groupby() ponieważ wyliczone L

lambda: y paczek wyniki musimy ponieważ możemy tylko ocenić g raz, bez zapisywania

lambda: z jest klawisz funkcyjny dla max(), aby wyciągnąć długości

Drukuje "2" zgodnie z oczekiwaniami.

Answer 6

Korzystanie more_itertools, biblioteki innych firm:

Biorąc

import itertools as it 

import more_itertools as mit 


lst = [0, 0, 1, 1, 1, 1, 0, 0, 1, 1] 

Kod

longest_contiguous = max([tuple(g) for _, g in it.groupby(lst)], key=len) 
longest_contiguous  
# (1, 1, 1, 1) 

pred = lambda w: w == longest_contiguous 
next(mit.locate(mit.windowed(lst, len(longest_contiguous)), pred=pred)) 
# 2 

Patrz także more_itertools.locate docstring Szczegółowe informacje na temat pracy tych narzędzi.