Matrice di indici per serie di intervalli

Question

Gli intervalli di rubino sono piuttosto interessanti. I finire con array come questo:

geneRanges = [(234..25), (500..510), (1640..1653)] 

e successivamente devono rimuovere frammenti di essi. Per quello I:

genePositions = geneRanges.collect {|range| range.entries }.flatten 
=> [500, 501, 502, 503, 504, 505, 506, 507, 508, 509, 510, 1640, 1641, 1642, 1643, 1644, 1645, 1646, 1647, 1648, 1649, 1650, 1651, 1652, 1653] 

Vengono manipolati, quindi alcuni numeri vengono esclusi e altri possono essere aggiunti. Potrei finire con questo:

[505, 506, 507, 600, 601, 602, 603, 1643, 1644, 1645, 1646, 1647, 1648, 1649, 1650, 1651, 1652, 1653, 1654] 

Come posso riconvertire questo in una gamma compatta di intervalli? Sembra che la funzione inversa dovrebbe esistere? Mi aspetto che restituisca qualcosa del genere:

[(505..507), (600..603), (1643..1654)] 

Grazie!

Answer 1

(Nuovo e migliorato rimane fresco nel frigorifero per un massimo di due settimane):

a = [1, 2, 3, 10, 11, 20, 20, 4] 

ranges = a.sort.uniq.inject([]) do |spans, n| 
    if spans.empty? || spans.last.last != n - 1 
    spans + [n..n] 
    else 
    spans[0..-2] + [spans.last.first..n] 
    end 
end 

p ranges # [1..4, 10..11, 20..20] 

Answer 2

Non ho mai visto nulla nel linguaggio Ruby che lo fa, ma qui è un codice che potrebbe aiutare a farlo da soli:.

http://snippets.dzone.com/posts/show/4677

Answer 3

ar=[505, 506, 507, 600, 1647, 1648, 1649, 1650, 1651, 1654] 
def to_range(a) 
    s=a[0] 
    a.each_cons(2) do |a| 
    if a[1]-a[0]!=1 
     p s .. a[0] 
     s=a[1] 
    end 
    end 
    left=a.index(s) 
    p a[left..-1][0]..a[left..-1][-1] 
end 
to_range(ar) 

Answer 4

soluzione funzionale, non molto leggibile:

(a[0,1]+a.each_cons(2).reject{|i,j| j-i==1}.flatten+a[-1,1]). 
    each_slice(2).map{|i,j| i..j} 

E una bella:

class Array 
    # splits array to sub-arrays wherever two adjacent elements satisfy a condition 
    def split_by 
    each_cons(2).inject([[first]]){|a, (i, j)| 
     a.push([]) if yield(i, j) 
     a.last.push j 
     a 
    } 
    end 

    # uses split_by to split array to subarrays with consecutive elements, then convert to range 
    def to_range 
    split_by{|i,j| j-i!=1}.map{|a| a.first..a.last} 
    end 
end 

[505, 506, 507, 600, 1647, 1648, 1649, 1650, 1651, 1654].split_by{|i,j| j-i!=1} 
#=> [[505, 506, 507], [600], [1647, 1648, 1649, 1650, 1651], [1654]] 
[505, 506, 507, 600, 1647, 1648, 1649, 1650, 1651, 1654].to_range 
#=> [505..507, 600..600, 1647..1651, 1654..1654] 

Answer 5

Si tratta di un presepe rettilineo di algoritmo di Wayne Conrads con un piccolo tweak per farlo funzionare per altri tipi di gamme, per esempio alfabetico

def array_to_ranges(a) 
ranges = a.sort.uniq.inject([]) do |spans, n| 
    if spans.empty? || spans.last.last.succ != n 
    spans + [n..n] 
    else 
    spans[0..-2] + [spans.last.first..n] 
    end 
end 
ranges 
end 

[ 
    [1..3, 10..11, 20..20, 4..4], 
    [ "a".."c", "f".."h", "x".."z"], 
    ["aa".."af"] 
].each do |arange| 
    p arange 
    p array = arange.collect {|range| range.to_a}.flatten 
    p array_to_ranges(array) 
end 

E i risultati di esecuzione di questo sono

 
[1..3, 10..11, 20..20, 4..4] 
[1, 2, 3, 10, 11, 20, 4] 
[1..4, 10..11, 20..20] 
["a".."c", "f".."h", "x".."z"] 
["a", "b", "c", "f", "g", "h", "x", "y", "z"] 
["a".."c", "f".."h", "x".."z"] 
["aa".."af"] 
["aa", "ab", "ac", "ad", "ae", "af"] 
["aa".."af"] 

Answer 6

Ecco una risposta (adattato da this code), che è più di due volte più veloce l'altro codice postato qui. Inoltre, solo questa risposta e the one by @Steve gestiscono le matrici di non interi.

class Array 
    def to_ranges 
    return [] if empty? 
    [].tap do |ranges| 
     init,last = first 
     each do |o| 
     if last && o != last.succ 
      ranges << (init..last) 
      init = o 
     end 
     last = o 
     end 
     ranges << (init..last) 
    end 
    end 
end 

Ecco i risultati dei benchmark:

    user  system  total  real 
steve  1.107000 0.000000 1.107000 ( 1.106221) 
wayne  1.092000 0.000000 1.092000 ( 1.099220) 
user229426 0.531000 0.000000 0.531000 ( 0.523104) 
mladen1  0.780000 0.000000 0.780000 ( 0.774154) 
mladen2  0.780000 0.000000 0.780000 ( 0.792159) 
phrogz  0.218000 0.000000 0.218000 ( 0.220044) 

Tutto il codice benchmark è stato adattato per rimuovere sort.uniq per un confronto equo.

Answer 7

array = [505, 506, 507, 600, 601, 602, 603, 1643, 1644, 1645, 1646, 1647, 1648, 1649, 1650, 1651, 1652, 1653, 1654] 
array.inject([]){ |a, e| a[-1] && a[-1].last && a[-1].last == e-1 ? a[-1] = (a[-1].first..e) : a << (e..e); a } 
#=> [505..507, 600..603, 1643..1654] 

e per gli array non ordinati si può presort esso:

array.sort!.uniq!