Comment voudriez-vous afficher un tableau d'entiers comme un ensemble de plages? (algorithme)
https://stackoverflow.com/questions/117691
-
02-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Étant donné un tableau d’entiers, quel est le moyen le plus simple d’itérer sur celui-ci et de calculer toutes les plages qu’il couvre? par exemple, pour un tableau tel que:
$numbers = array(1,3,4,5,6,8,11,12,14,15,16);
Les plages seraient les suivantes:
1,3-6,8,11-12,14-16
La solution
Si le tableau est trié par ordre croissant, le problème est simple. Définissez une structure ou une classe Range , qui a un début et une fin. Puis parcourez le tableau. Si l'élément en cours est un de plus que le précédent, mettez à jour Range.end , sinon créez une nouvelle plage avec cet élément sous la forme Range.begin . Stockez les plages dans un tableau dynamique ou une liste liée. Ou simplement les imprimer au fur et à mesure.
Si le tableau ne peut pas être trié, triez-le d'abord.
Autres conseils
Voici une façon de le faire en C # 3.0:
Points d'intérêt:
- propriétés automatiques (public int Property {get; set;})
- utilisation de nouveaux initialiseurs d'objet (nouvelle plage {Begin = xxx; ...}
- utiliser le rendement pour une évaluation paresseuse
- utilisant les méthodes d'extension linq (First () et 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;
}
}
À la vôtre David
Voici une implémentation en python, il devrait être assez facile à suivre
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);
Cette sortie:
1
3-6
8
11-12
14-16
Je sais, je sais, ce n'est pas un algorithme , mais j'ai trouvé plus difficile de l'expliquer réellement sans problèmes d'indentation que de simplement mettre en œuvre une solution.
premier: trier deuxième: tokenise then: affiche la première valeur et passe en boucle sur les suivantes. Si la valeur "actuelle" est égale à la dernière valeur +1, ignorez-la. Sinon, si vous avez ignoré la valeur du tiret d'impression et de la valeur, sinon imprimez une virgule et répétez.
Cela devrait faire. A moins que tu ne veuilles que je te confie tes devoirs? :)
Si le tableau est trié, comme dans votre exemple, je définirais des compartiments contenant un minimum et un maximum.
Initialiser: créez un compartiment avec un minimum et un maximum égaux à la première valeur.
Loop: Compare chaque valeur avec le maximum du compartiment actuel. S'il est égal ou supérieur de 1 au maximum actuel, mettez à jour le max. S'il est supérieur à 1 au maximum, enregistrez le compartiment dans une liste de compartiments et démarrez-en un nouveau.
À la fin, vous aurez un ensemble de seaux avec un minimum et un maximum dans chacun. Si le min est identique au max, imprimez un nombre unique (par exemple, dans votre exemple, le premier compartiment aurait un min et un maximum de 1). S'ils sont différents, imprimez-les sous la forme d'une plage.
Exemple d'implémentation dans 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>
En gros, vous vous retrouvez avec une liste de choses, où chaque chose a (plus bas dans le compartiment, plus haut dans le compartiment). Ce sont vos gammes.
Si la liste n'est pas déjà triée, commencez par la trier.
C (gcc)
Il est similaire à version 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");
}
Exemple:
/**
* $ 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);
}
Sortie:
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
En supposant que la liste soit ordonnée, vous pouvez commencer à la fin et continuer à soustraire la suivante. Alors que la différence est 1, vous êtes dans une plage. Quand ce n'est pas le cas, vous commencez une nouvelle gamme.
c'est-à-dire
16-15 = 1
15-14 = 1
14-12 = 2, la plage est 16-14 - commencez une nouvelle plage.
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
}
}
Voici ma solution Perl. Pourrait être plus propre et plus rapide, mais cela montre comment cela fonctionne:
# 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( Voici ma solution Perl. Pourrait être plus propre et plus rapide, mais cela montre comment cela fonctionne:
<*> == $range->[-1] + 1) {
push @$range, Voici ma solution Perl. Pourrait être plus propre et plus rapide, mais cela montre comment cela fonctionne:
<*>;
}
else {
print $#$range ? $range->[0] . '-' . $range->[-1] : $range->[0], "\n";
$range = [ Voici ma solution Perl. Pourrait être plus propre et plus rapide, mais cela montre comment cela fonctionne:
<*> ];
}
}
Ma solution dans Java 1.5 serait:
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);
}
quelles sorties:
[1, 3-6, 8, 11-12, 14-16]
Greetz, GHad
Je pense que la propriété mergeinfo introduite dans Subversion dans la version 1.5 a un format identique à celui que vous demandez. Vous pouvez donc éventuellement consulter la source de Subversion pour savoir comment procéder. . Je serais surpris qu’il soit différent des autres suggestions déjà publiées ici.
Je supposerai que le tableau X () est pré-trié (et si ce n'est pas le cas, triez le tableau à l'avance).
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()
bon, c'est comme ça que je le ferais.
Créez un type de plage simple contenant les valeurs de début / fin de plage. Ajoutez un constructeur qui prend une seule valeur et définit start = end = value. Conservez une pile d'objets de plage, naviguez dans une copie triée du tableau, élargissez la plage supérieure ou ajoutez une nouvelle plage, le cas échéant. Plus précisément, lorsque la valeur dans le tableau est 1 + la valeur finale de l’objet intervalle situé sur le à de la pile, incrémentez la valeur finale de cette étendue; si ce n’est pas le cas, poussez une nouvelle plage (avec start = end = valeur à index in array) sur la pile.
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]]
Voici mon meilleur coup à 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)
Cette version gère en outre les doublons et les séquences non triées.
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
Exemple:
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])
Sortie:
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
