¿Cómo mostrarías una matriz de números enteros como un conjunto de rangos?(algoritmo)

Question

Dada una serie de números enteros, ¿cuál es la forma más sencilla de iterar sobre ella y calcular todos los rangos que cubre?por ejemplo, para una matriz como:

$numbers = array(1,3,4,5,6,8,11,12,14,15,16);

Los rangos serían:

 1,3-6,8,11-12,14-16

Answer 1

Si la matriz está ordenada en orden ascendente, entonces el problema es fácil.Definir un Range Estructura o clase, que tiene un principio y un fin.Luego revise la matriz.Si el elemento actual es uno más que el anterior, actualice Range.end, de lo contrario cree un nuevo rango con este elemento como Range.begin.Almacene los rangos en una matriz dinámica o una lista vinculada.O simplemente imprímalos sobre la marcha.

Si es posible que la matriz no esté ordenada, ordénela primero.

Answer 2

Aquí hay una forma de hacerlo en C# 3.0:

Puntos de interés:

• propiedades automáticas (propiedad pública int { get;colocar;})
• usando nuevos inicializadores de objetos (nuevo Rango { Begin = xxx;...}
• usando el rendimiento para la evaluación perezosa
• usando métodos de extensión de linq (First() y Skip())

-

class Demo
{
    private class Range
    {
        public int Begin { get; set; }
        public int End { get; set; }

        public override string ToString()
        {
            if (Begin == End)
                return string.Format("{0}", Begin);
            else
                return string.Format("{0}-{1}", Begin, End);
        }
    }

    static void Main(string[] args)
    {
        var list = new List<int> { 1, 3, 4, 5, 6, 8, 11, 12, 14, 15, 16 };
        // list.Sort();
        var ranges = GetRangesForSortedList(list);

        PrintRange(ranges);

        Console.Read();
    }

    private static void PrintRange(IEnumerable<Range> ranges)
    {
        if (ranges.Count() == 0)
            return;

        Console.Write("[{0}", ranges.First());

        foreach (Range range in ranges.Skip(1))
        {
            Console.Write(", {0}", range);
        }

        Console.WriteLine("]");
    }

    private static IEnumerable<Range> GetRangesForSortedList(IList<int> sortedList)
    {
        if (sortedList.Count < 1) 
            yield break;

        int firstItem = sortedList.First();
        Range currentRange = new Range { Begin = firstItem, End = firstItem };

        foreach (int item in sortedList.Skip(1))
        {
            if (item == currentRange.End + 1)
            {
                currentRange.End = item;
            }
            else
            {
                yield return currentRange;
                currentRange = new Range { Begin = item, End = item };
            }
        }

        yield return currentRange;
    }
}

Saludos, david

Answer 3

Aquí hay una implementación de Python, debería ser bastante fácil de seguir.

numbers = [1,3,4,5,6,8,11,12,14,15,16];

def is_predecessor(i1, i2):
    if i1 == i2 - 1:
        return True;
    else:
        return False;

def make_range(i1, i2):
    if i1 == i2:
        return str(i1);
    else:
        return str(i1) + "-" + str(i2);

previous_element = None;
current_start_element = None;

for number in numbers:
    if not is_predecessor(previous_element, number):
        if current_start_element is not None:
            print make_range(current_start_element, previous_element);
        current_start_element = number;
    previous_element = number;

# handle last pair
if current_start_element is not None:
    print make_range(current_start_element, previous_element);

Esto produce:

1
3-6
8
11-12
14-16

Lo sé, lo sé, no es un algoritmo, pero me resultó más difícil explicarlo sin tener problemas de sangría que simplemente implementar una solución.

Answer 4

primero:Ordenar segundo:Tokenise entonces:imprima el primer valor y recorra los siguientes.Si el valor 'actual' es igual al último valor +1, omítalo.De lo contrario, si omitió el valor, imprima el guión y el valor; de lo contrario, imprima una coma y repita.

Eso debería bastar.¿A menos que quisieras que codificara tu tarea por ti?:)

Answer 5

Si la matriz está ordenada, como en su ejemplo, definiría depósitos que contengan un mínimo y un máximo.

Inicializar:Cree un depósito con un mínimo y un máximo iguales al primer valor.

Bucle:Compare cada valor con el máximo del depósito actual.Si es igual o 1 más que el máximo actual, actualice el máximo.Si es más de 1 mayor que el máximo, guarde el depósito en una lista de depósitos e inicie un nuevo depósito.

Al final tendrás un conjunto de cubos con un mínimo y un máximo en cada uno.Si el mínimo es el mismo que el máximo, imprima un solo número (es decir:en su ejemplo, el primer depósito tendría un mínimo y un máximo de 1).Si son diferentes, imprima como un rango.

Implementación de ejemplo en lisp:

CL-USER> (defun print-ranges (integer-list)
           (let ((sorted-list (sort integer-list #'<)))
             (loop with buckets = ()
                   with current-bucket
                   for int in sorted-list
                     initially (setf current-bucket (cons (first sorted-list) (first sorted-list)))
                   do (cond ((= int (cdr current-bucket))) ; do nothing, this number is already in range
                            ((= (1- int) (cdr current-bucket)) ; number is 1 higher--update bucket's max
                             (setf (cdr current-bucket) int))
                            (t
                             (push current-bucket buckets)
                             (setf current-bucket (cons int int)))) ; set up a new bucket
                   finally (push current-bucket buckets)
                           (loop for firstp = t then nil
                                 for bucket in (nreverse buckets) do
                                   (cond ((= (car bucket) (cdr bucket))
                                          (format t "~:[,~;~]~D" firstp (car bucket)))
                                         (t
                                          (format t "~:[,~;~]~D-~D" firstp (car bucket) (cdr bucket))))))))
PRINT-RANGES
CL-USER> (print-ranges (list 1 3 4 5 6 8 11 12 14 15 16))
1,3-6,8,11-12,14-16
NIL
CL-USER> 

Básicamente, terminas con una lista de cosas, donde cada cosa tiene (la más baja del grupo, la más alta del grupo).Esos son tus rangos.

Si la lista aún no está ordenada, ordénela primero.

Answer 6

C (ccg)

Esto es similar a la versión de Python.

void ranges(int n; int a[n], int n)
{
  qsort(a, n, sizeof(*a), intcmp);
  for (int i = 0; i < n; ++i) {
    const int start = i;
    while(i < n-1 and a[i] >= a[i+1]-1)
      ++i;
    printf("%d", a[start]);
    if (a[start] != a[i])
      printf("-%d", a[i]);
    if (i < n-1)
      printf(",");
  }
  printf("\n");
}

Ejemplo:

/**
 * $ gcc -std=c99 -Wall ranges.c -o ranges && ./ranges
 */
#include <iso646.h> // and
#include <stdio.h>
#include <stdlib.h>

#define T(args...)                                              \
  {                                                             \
    int array[] = {args};                                       \
    ranges(array, sizeof(array) / sizeof(*array));              \
  }

int intcmp(const void* a, const void* b)
{
  const int *ai = a;
  const int *bi = b;

  if (*ai < *bi)
    return -1;
  else if (*ai > *bi)
    return 1;
  else
    return 0;
}

int main(void)
{
  T(1,3,4,5,6,8,11,12,14,15,16);
  T();
  T(1);
  T(1, 2);
  T(3, 1);
  T(1, 3, 4);
  T(1, 2, 4);
  T(1, 1, 2, 4);
  T(1, 2, 2, 4);
  T(1, 2, 2, 3, 5, 5);
}

Producción:

1,3-6,8,11-12,14-16

1
1-2
1,3
1,3-4
1-2,4
1-2,4
1-2,4
1-3,5

Answer 7

Suponiendo que la lista esté ordenada, puede comenzar por el final y seguir restando el siguiente.Si bien la diferencia es 1, estás en un rango.Cuando no es así, comienzas un nuevo rango.

es decir

16-15 = 1

15-14 = 1

14-12 = 2, el rango es 16-14: comienza un nuevo rango.

Answer 8

startRange = array[0];    
for(i=0;i<array.length;i++)
{
   if (array[i + 1] - array[i] > 1)
   {
     endRange = array[i];
     pushRangeOntoArray(startRange,endRange);
     i++;
     startRange = array[i]
     // need to check for end of array here
   }
}

Answer 9

Aquí está mi solución Perl.Podría ser más limpio y rápido, pero muestra cómo funciona:

# Just in case it's not sorted...
my @list = sort { $a <=> $b } ( 1, 3, 4, 5, 6, 8, 11, 12, 14, 15, 16 );

my $range = [ $list[0] ];

for(@list[1 .. $#list]) {
    if($_ == $range->[-1] + 1) {
        push @$range, $_;
    }
    else {
        print $#$range ? $range->[0] . '-' . $range->[-1] : $range->[0], "\n";
        $range = [ $_ ];
    }
}

Answer 10

Mi solución en Java 1.5 sería:

public static List<String> getRanges(int... in) {
    List<String> result = new ArrayList<String>();
    int last = -1;
    for (int i : in) {
        if (i != (last + 1)) {
            if (!result.isEmpty()) {
                addRange(result, last);
            }
            result.add(String.valueOf(i));
        } 
        last = i;
    }
    addRange(result, last);
    return result;
}

private static void addRange(List<String> result, int last) {
    int lastPosition = result.size() - 1;
    String lastResult = result.get(lastPosition);
    if (!lastResult.equals(String.valueOf(last))) {
        result.set(lastPosition, lastResult + "-" + last);
    }
}

public static void main(String[] args) {
    List<String> ranges = getRanges(1, 3, 4, 5, 6, 8, 11, 12, 14, 15, 16);
    System.out.println(ranges);
}

que produce:

[1, 3-6, 8, 11-12, 14-16]

Greetz, G Had

Answer 11

Creo que la propiedad mergeinfo que se introdujo en Subversion en la versión 1.5 tiene un formato que es el mismo que estás solicitando, por lo que podrías consultar la fuente de Subversion para descubrir cómo lo hacen.Me sorprendería que fuera diferente a las otras sugerencias que ya se han publicado aquí.

Answer 12

Asumiré que la matriz X() está preordenada (y si no, ordene la matriz de antemano).

for each element of X() as $element (with $i as current array posistion)
    add $element to end of array Y()
    if (X($i) + 1 is less than X($i + 1)) AND ($i + 1 is not greater than sizeof(X())) then
        append Y(1)."-".Y(sizeof(Y())) to end of Z()
        unset Y()
    end if    
next
if anything remains in Y() append to end of Z()

Bueno, así es como lo haría.

Answer 13

Cree un tipo de rango simple que contenga valores de inicio/fin de rango.Agregue un constructor que tome solo un valor y establezca inicio = fin = valor.Mantenga una pila de objetos de rango, avance a través de una copia ordenada de la matriz, extienda el rango superior o agregue un nuevo rango según corresponda.Más específicamente, cuando el valor en la matriz es 1 + el valor final para el objeto de rango en la parte superior de la pila, incremente el valor final para ese rango, cuando no lo sea, inserte un nuevo rango (con inicio = fin = valor en index in array) en la pila.

Answer 14

module Main where

ranges :: [Int] -> [[Int]]
ranges [] = []
ranges list@(x:xs) = let adj = adjacent list in
             let len = length adj in
                 if length adj == 1
                then [[x]] ++ ranges xs
                else [[x,(last adj)]] ++ ranges (drop ((length adj) - 1) xs)
    where adjacent [] = []
          adjacent (x:xs) = if (xs /= []) && (x + 1) == head xs
             then [x] ++ adjacent (xs)
             else [x]

main = do putStrLn $ show $ ranges [1,2,3,4,5,6,8,11,12,14,15,16]

-- Output: [[1,6],[8],[11,12],[14,16]]

Aquí está mi mejor oportunidad en Haskell.

Answer 15

Perla 6

sub to_ranges( Int *@data ){
  my @ranges;

  OUTER: for @data -> $item {
    for @ranges -> $range {
      # short circuit if the $item is in a range
      next OUTER if $range[0] <= $item <= $range[1];

      given( $item ){
        when( $range[0]-1 ){ $range[0] = $item }
        when( $range[1]+1 ){ $range[1] = $item }
      }
    }

    push @ranges, [$item,$item];
  }

  return @ranges;
}

Answer 16

Pitón (>= 2,6)

Esta versión también maneja duplicados y secuencias sin clasificar.

from __future__ import print_function

def ranges(a):
    a.sort()
    i = 0
    while i < len(a):
        start = i
        while i < len(a)-1 and a[i] >= a[i+1]-1:
            i += 1
        print(a[start] if a[start] == a[i] else "%d-%d" % (a[start], a[i]),
              end="," if i < len(a)-1 else "\n")
        i += 1

Ejemplo:

import random
r = range(10)
random.shuffle(r)
ranges(r)
ranges([1,3,4,5,6,8,11,12,14,15,16]);
ranges([])
ranges([1])
ranges([1, 2])
ranges([1, 3])
ranges([1, 3, 4])
ranges([1, 2, 4])
ranges([1, 1, 2, 4])
ranges([1, 2, 2, 4])
ranges([1, 2, 2, 3, 5, 5])

Producción:

0-9
1,3-6,8,11-12,14-16
1
1-2
1,3
1,3-4
1-2,4
1-2,4
1-2,4
1-3,5