tuple di intervalli continui chiusi

Question

Dire che ho il seguente elenco di numeri:

my_array = [0, 3, 4, 7, 8, 9, 10, 20, 21, 22, 70] 

mi piacerebbe trovare ogni intervallo chiuso contenente interi consecutivi senza lacune in questo elenco. Se per qualsiasi numero nell'elenco ci sono più intervalli di questo tipo, abbiamo il che conserva solo il massimo di tali intervalli. La risposta corretta sopra dovrebbe essere:

[0, 0] 
[3, 4] 
[7, 10] 
[20, 22] 
[70, 70] 

Per vedere questo, si noti ad esempio:

• l'intervallo chiuso [0,0] contiene l'intero 0, non contiene lacune, e nessuno dei suoi componenti sono contenuti in qualsiasi altro intervallo chiuso.

• L'intervallo chiuso [3,4] non contiene spazi vuoti e i suoi membri non sono contenuti in nessun altro intervallo chiuso senza spazi più grandi di se stessi.

Come posso fare questo in numpy? Ho iniziato a scrivere un algoritmo che utilizza np.diff(my_array) per rilevare le transizioni nell'array, ma non riesce su casi d'angolo come intervalli contenenti solo un elemento.

Answer 1

Non ho un'installazione numpy a portata di mano, ma questo è l'approccio che vorrei adottare. Per prima cosa gestisci separatamente il caso di un array vuoto. Ordinare l'array se non è già ordinato e utilizzare np.diff per calcolare le differenze.

0, 3, 4, 7, 8, 9, 10, 20, 21, 22, 70 
    3 1 3 1 1 1 10 1 1 48 

Verificare le differenze per essere > 1.

1 0 1 0 0 0 1 0 0 1 

Per ottenere inizi degli intervalli messo un 1 all'inizio e selezionare gli elementi di matrice corrispondente. Per ottenere i fini, inserisci un 1 alla fine e seleziona gli elementi dell'array corrispondente.

0, 3, 4, 7, 8, 9, 10, 20, 21, 22, 70 
1 1 0 1 0 0 0 1 0 0 1 
0 3  7    20   70 

0, 3, 4, 7, 8, 9, 10, 20, 21, 22, 70 
1 0 1 0 0 0 1 0 0 1 1 
0  4   10   22 70 

attuazione (in gran parte da user815423426):

def get_intervals(my_array): 
    my_diff = np.diff(my_array)>1 
    begins = np.insert(my_diff, 0, 1) 
    ends = np.insert(my_diff, -1, 1) 
    return np.array(np.dstack((my_array[begins], my_array[ends]))) 

my_array = np.array([0, 3, 4, 7, 8, 9, 10, 20, 21, 22, 70]) 
> get_intervals(my_array) 
array([[ 0, 0], 
     [ 3, 4], 
     [ 7, 10], 
     [20, 22], 
     [70, 70]]) 

Answer 2

implementazione di Python puro:

def findContinuousIntervals(numbers): 
    if not numbers: 
     return [] 

    sortedNumbers = sorted(numbers) 

    result = [(sortedNumbers[0], sortedNumbers[0])] 
    for n in sortedNumbers: 
     a, b = result[-1] 
     if abs(b - n) <= 1: 
      result[-1] = (a, n) 
     else: 
      result.append((n, n)) 
    return result