Como você exibir um array de inteiros como um conjunto de intervalos? (algoritmo)
https://stackoverflow.com/questions/117691
-
02-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Dado um array de inteiros, o que é a maneira mais simples de iterar sobre ele e descobrir todos os intervalos que abrange? por exemplo, para uma matriz tal como:
$numbers = array(1,3,4,5,6,8,11,12,14,15,16);
Os intervalos seria:
1,3-6,8,11-12,14-16
Solução
Se a matriz é classificada em ordem ascendente, então o problema é fácil. Definir uma estrutura Range ou classe, que tem um princípio e um fim. Em seguida, passar a matriz. Se o elemento atual é mais um do que o, Range.end anterior atualização, caso contrário, criar uma nova gama com esse elemento como Range.begin. Armazenar os intervalos para uma matriz dinâmica ou uma lista ligada. Ou apenas imprimi-los como você vai.
Se a matriz não podem ser classificadas, em seguida, classificá-lo pela primeira vez.
Outras dicas
Aqui está uma maneira C # 3.0'y de fazê-lo:
Pontos de interesse:
- propriedades automáticas (int pública Property {get; set;})
- usando novas inicializadores de objeto (novo Range {Comece = xxx; ...}
- Utilizando o rendimento para avaliação lenta
- usando métodos de extensão LINQ (First () e 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;
}
}
Cheers, David
Aqui está uma implementação python, ele deve ser fácil o suficiente para 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);
Esta saídas:
1
3-6
8
11-12
14-16
Eu sei, eu sei, não é uma algoritmo , mas eu achei mais difícil de realmente explicá-lo sem ter problemas de recuo do que apenas implementar uma solução para ele.
primeira: sort segunda: tokenise então: imprimir o primeiro valor e loop sobre as subseqüentes. Se o valor 'atual' é igual ao último valor +1, ignorá-lo. Caso contrário, se você tem ignorado traço valor de impressão e o valor, caso contrário imprimir uma vírgula e repita.
Isso deve fazer. A menos que você me queria código até a sua casa para você? :)
Se a matriz é classificada, como no seu exemplo, eu poderia definir baldes contendo um min e um max.
Inicializar:. Criar um balde com um min e um máximo igual ao primeiro valor
Loop: Compare cada valor com o máximo do balde atual. Se for igual ou mais 1 do que o máximo atual, atualizar o max. Se for mais de 1 maior do que o máximo, salvar o balde para uma lista de baldes e iniciar um novo balde.
No final você terá um conjunto de baldes com um min e um máximo em cada um. Se o min é o mesmo que o máximo, imprimir um número único (ou seja: no seu exemplo, o primeiro bloco teria um min e um máximo de 1). Se forem diferentes, imprima como um intervalo.
Exemplo implementação em 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>
Basicamente você acaba com uma lista de coisas, onde cada coisa tem (mais baixo-in-balde, mais alto-in-bucket). Esses são os seus intervalos.
Se a lista não estiver classificada, classificá-lo pela primeira vez.
C (gcc)
É semelhante a do Python versão .
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");
}
Exemplo:
/**
* $ 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);
}
Output:
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
Assumindo que a lista é ordenada você poderia começar no final e manter subtraindo a próxima para baixo. Embora a diferença é de 1, você está em um intervalo. Quando não é, você começa uma nova gama.
i
16-15 = 1
15-14 = 1
14-12 = 2, o intervalo é de 16-14 -. Iniciar uma nova gama
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
}
}
Aqui está a minha solução Perl. Poderia ser mais limpo e mais rápido, mas mostra como 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 = [ $_ ];
}
}
A minha solução em Java 1.5 seria:
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 saídas:
[1, 3-6, 8, 11-12, 14-16]
Greetz, Ghad
Eu acredito que a propriedade mergeinfo que foi introduzido no Subversion na versão 1.5 tem um formato que é o mesmo que o que você está pedindo, então você poderia ir olhar através da fonte do Subversion para descobrir como eles fazem isso . Eu ficaria surpreso se a sua diferente do que as outras sugestões que já foram publicados aqui.
Vou assumir a matriz X () é pré-ordenada (e se não, classificar a matriz antes de mão).
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()
bem, é assim que eu iria fazê-lo.
Criar um tipo simples faixa que contém início / fim de valores do intervalo. Adicione um construtor que leva apenas um valor e conjuntos start = end = valor. Manter uma pilha de objetos alcance, trabalhar o seu caminho através de uma cópia ordenada do array, estender a gama superior ou adicionar uma nova linha, conforme apropriado. Mais especificamente, quando o valor da matriz é 1 + o valor final para o objecto intervalo no a da pilha, incrementar o valor final para esse intervalo, quando não é, enviar uma nova gama (com início = final = valor em índice na matriz) para a pilha.
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]]
Aqui está o meu melhor tiro em Haskell.
Perl 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;
}
Python (> = 2.6)
Esta versão também lida com duplicatas e seqüências indiferenciados.
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
Exemplo:
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])
Output:
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
