algorithm - busqueda - Mero de algoritmo de número adyacente

busqueda en profundidad c++

Question

Por lo que quiero decir esto:

Dado el conjunto de entrada de números:

1,2,3,4,5 se convierte en "1-5".

1,2,3,5,7,9,10,11,12,14 se convierte en "1-3, 5, 7, 9-12, 14"

Esto es lo mejor que logré: [C #]

Lo cual me parece un poco descuidado, así que la pregunta es, ¿de alguna manera hay una solución más legible y / o elegante para esto?

public static string[] FormatInts(int[] ints)
{
if (ints == null)
throw new ArgumentNullException("ints"); // hey what are you doing?
if (ints.Length == 0)
return new string[] { "" }; // nothing to process
if (ints.Length == 1)
return new string[] { ints[0].ToString() }; // nothing to process
Array.Sort<int>(ints); // need to sort these lil'' babies
List<string> values = new List<string>();
int lastNumber = ints[0]; // start with the first number
int firstNumber = ints[0]; // same as above
for (int i = 1; i < ints.Length; i++)
{
int current = ints[i];
int difference = (lastNumber - current ); // compute difference between last number and current number
if (difference == -1) // the numbers are adjacent
{
if (firstNumber == 0) // this is the first of the adjacent numbers
{
firstNumber = lastNumber;
}
else // we''re somehow in the middle or at the end of the adjacent number set
{
lastNumber = current;
continue;
}
}
else
{
if (firstNumber > 0 && firstNumber != lastNumber) // get ready to print a set of numbers
{
values.Add(string.Format("{0}-{1}", firstNumber, lastNumber));
firstNumber = 0; // reset
}
else // print a single value
{
values.Add(string.Format("{0}", lastNumber));
}
}
lastNumber = current;
}
if (firstNumber > 0) // if theres anything left, print it out
{
values.Add(string.Format("{0}-{1}", firstNumber, lastNumber));
}
return values.ToArray();
}

Answer 1

VBA

Public Function convertListToRange(lst As String) As String
Dim splLst() As String
splLst = Split(lst, ",")
Dim x As Long
For x = 0 To UBound(splLst)
Dim groupStart As Integer
groupStart = splLst(x)
Dim groupEnd As Integer
groupEnd = groupStart
Do While (x <= UBound(splLst) - 1)
If splLst(x) - splLst(x + 1) <> -1 Then Exit Do
groupEnd = splLst(x + 1)
x = x + 1
Loop
convertListToRange = convertListToRange & IIf(groupStart = groupEnd, groupStart & ",", groupStart & "-" & groupEnd & ",")
Next x
convertListToRange = Left(convertListToRange, Len(convertListToRange) - 1)
End Function

convertListToRange ("1,2,3,7,8,9,11,12,99,100,101")
Regreso: "1-3,7-9,11-12,99-101"

Answer 2

Perl

Con validación de entrada / clasificación previa

Puede obtener fácilmente el resultado como un LoL si necesita hacer algo más elegante que simplemente devolver una cadena.

#!/usr/bin/perl -w
use strict;
use warnings;
use Scalar::Util qw/looks_like_number/;
sub adjacenify {
my @input = @_;
# Validate and sort
looks_like_number $_ or
die "Saw ''$_'' which doesn''t look like a number" for @input;
@input = sort { $a <=> $b } @input;
my (@output, @range);
@range = (shift @input);
for (@input) {
if ($_ - $range[-1] <= 1) {
push @range, $_ unless $range[-1] == $_; # Prevent repetition
}
else {
push @output, [ @range ];
@range = ($_);
}
}
push @output, [ @range ] if @range;
# Return the result as a string. If a sequence is size 1, then it''s just that number.
# Otherwise, it''s the first and last number joined by ''-''
return join '', '', map { 1 == @$_ ? @$_ : join '' - '', $_->[0], $_->[-1] } @output;
}
print adjacenify( qw/1 2 3 5 7 9 10 11 12 14/ ), "/n";
print adjacenify( 1 .. 5 ), "/n";
print adjacenify( qw/-10 -9 -8 -1 0 1 2 3 5 7 9 10 11 12 14/ ), "/n";
print adjacenify( qw/1 2 4 5 6 7 100 101/), "/n";
print adjacenify( qw/1 62/), "/n";
print adjacenify( qw/1/), "/n";
print adjacenify( qw/1 2/), "/n";
print adjacenify( qw/1 62 63/), "/n";
print adjacenify( qw/-2 0 0 2/), "/n";
print adjacenify( qw/-2 0 0 1/), "/n";
print adjacenify( qw/-2 0 0 1 2/), "/n";

Salida:

1 - 3, 5, 7, 9 - 12, 14
1 - 5
-10 - -8, -1 - 3, 5, 7, 9 - 12, 14
1 - 2, 4 - 7, 100 - 101
1, 62
1
1 - 2
1, 62 - 63
-2, 0, 2
-2, 0 - 1
-2, 0 - 2
-2, 0 - 2

Y una buena solución recursiva:

sub _recursive_adjacenify($$);
sub _recursive_adjacenify($$) {
my ($input, $range) = @_;
return $range if ! @$input;
my $number = shift @$input;
if ($number - $range->[-1] <= 1) {
return _recursive_adjacenify $input, [ @$range, $number ];
}
else {
return $range, _recursive_adjacenify $input, [ $number ];
}
}
sub recursive_adjacenify {
my @input = @_;
# Validate and sort
looks_like_number $_ or
die "Saw ''$_'' which doesn''t look like a number" for @input;
@input = sort { $a <=> $b } @input;
my @output = _recursive_adjacenify /@input, [ shift @input ];
# Return the result as a string. If a sequence is size 1,
# then it''s just that number.
# Otherwise, it''s the first and last number joined by ''-''
return join '', '', map { 2 == @$_ && $_->[0] == $_->[1] ? $_->[0] :
1 == @$_ ? @$_ :
join '' - '', $_->[0], $_->[-1] } @output;
}

Answer 3

Como escribí en el comentario, no soy partidario del uso del valor 0 como indicador, haciendo que firstNumber sea un valor y un indicador.

Hice una implementación rápida del algoritmo en Java, omitiendo audazmente las pruebas de validez que ya cubriste correctamente ...

public class IntListToRanges
{
// Assumes all numbers are above 0
public static String[] MakeRanges(int[] numbers)
{
ArrayList<String> ranges = new ArrayList<String>();
Arrays.sort(numbers);
int rangeStart = 0;
boolean bInRange = false;
for (int i = 1; i <= numbers.length; i++)
{
if (i < numbers.length && numbers[i] - numbers[i - 1] == 1)
{
if (!bInRange)
{
rangeStart = numbers[i - 1];
bInRange = true;
}
}
else
{
if (bInRange)
{
ranges.add(rangeStart + "-" + numbers[i - 1]);
bInRange = false;
}
else
{
ranges.add(String.valueOf(numbers[i - 1]));
}
}
}
return ranges.toArray(new String[ranges.size()]);
}
public static void ShowRanges(String[] ranges)
{
for (String range : ranges)
{
System.out.print(range + ","); // Inelegant but quickly coded...
}
System.out.println();
}
/**
* @param args
*/
public static void main(String[] args)
{
int[] an1 = { 1,2,3,5,7,9,10,11,12,14,15,16,22,23,27 };
int[] an2 = { 1,2 };
int[] an3 = { 1,3,5,7,8,9,11,12,13,14,15 };
ShowRanges(MakeRanges(an1));
ShowRanges(MakeRanges(an2));
ShowRanges(MakeRanges(an3));
int L = 100;
int[] anr = new int[L];
for (int i = 0, c = 1; i < L; i++)
{
int incr = Math.random() > 0.2 ? 1 : (int) Math.random() * 3 + 2;
c += incr;
anr[i] = c;
}
ShowRanges(MakeRanges(anr));
}
}

No diré que es más elegante / eficiente que tu algoritmo, por supuesto ... Solo algo diferente.

Tenga en cuenta que 1,5,6,9 se puede escribir ya sea 1,5-6,9 o 1,5,6,9, no estoy seguro de qué es mejor (si lo hay).

Recuerdo haber hecho algo similar (en C) para agrupar números de mensajes en rangos de Imap, ya que es más eficiente. Un algoritmo útil.

Answer 4

He reescrito tu código así:

 public static string[] FormatInts(int[] ints)
{
Array.Sort<int>(ints);
List<string> values = new List<string>();
for (int i = 0; i < ints.Length; i++)
{
int groupStart = ints[i];
int groupEnd = groupStart;
while (i < ints.Length - 1 && ints[i] - ints[i + 1] == -1)
{
groupEnd = ints[i + 1];
i++;
}
values.Add(string.Format(groupEnd == groupStart ? "{0}":"{0} - {1}", groupStart, groupEnd));
}
return values.ToArray();
}

Y entonces:

/////////////////
int[] myInts = { 1,2,3,5,7,9,10,11,12,14 };
string[] result = FormatInts(myInts); // now result haves "1-3", "5", "7", "9-12", "14"

Answer 5

Me parece claro y directo. Puede simplificar un poco si asume que la matriz de entrada está ordenada o la ordena usted mismo antes de continuar con el procesamiento.

El único truco que sugeriría sería revertir la resta:

int difference = (current - lastNumber);

... simplemente porque me resulta más fácil trabajar con diferencias positivas. ¡Pero su código es un placer de leer!

Answer 6

Mi primer pensamiento, en Python:

def seq_to_ranges(seq):
first, last = None, None
for x in sorted(seq):
if last != None and last + 1 != x:
yield (first, last)
first = x
if first == None: first = x
last = x
if last != None: yield (first, last)
def seq_to_ranges_str(seq):
return ", ".join("%d-%d" % (first, last) if first != last else str(first) for (first, last) in seq_to_ranges(seq))

Posiblemente podría ser más limpio, pero aún así es más fácil.

Traducción simple a Haskell:

import Data.List
seq_to_ranges :: (Enum a, Ord a) => [a] -> [(a, a)]
seq_to_ranges = merge . foldl accum (id, Nothing) . sort where
accum (k, Nothing) x = (k, Just (x, x))
accum (k, Just (a, b)) x | succ b == x = (k, Just (a, x))
| otherwise = (k . ((a, b):), Just (x, x))
merge (k, m) = k $ maybe [] (:[]) m
seq_to_ranges_str :: (Enum a, Ord a, Show a) => [a] -> String
seq_to_ranges_str = drop 2 . concatMap r2s . seq_to_ranges where
r2s (a, b) | a /= b = ", " ++ show a ++ "-" ++ show b
| otherwise = ", " ++ show a

Sobre lo mismo.

Answer 7

Puro funcional Python:

#!/bin/env python
def group(nums):
def collect((acc, i_s, i_e), n):
if n == i_e + 1: return acc, i_s, n
return acc + ["%d"%i_s + ("-%d"%i_e)*(i_s!=i_e)], n, n
s = sorted(nums)+[None]
acc, _, __ = reduce(collect, s[1:], ([], s[0], s[0]))
return ", ".join(acc)
assert group([1,2,3,5,7,9,10,11,12,14]) == "1-3, 5, 7, 9-12, 14"

Answer 8

Ruby corto y dulce

def range_to_s(range)
return range.first.to_s if range.size == 1
return range.first.to_s + "-" + range.last.to_s
end
def format_ints(ints)
range = []
0.upto(ints.size-1) do |i|
range << ints[i]
unless (range.first..range.last).to_a == range
return range_to_s(range[0,range.length-1]) + "," + format_ints(ints[i,ints.length-1])
end
end
range_to_s(range)
end

Answer 9

Aquí está mi entrada de Haskell:

runs lst = map showRun $ runs'' lst
runs'' l = reverse $ map reverse $ foldl newOrGlue [[]] l
showRun [s] = show s
showRun lst = show (head lst) ++ "-" ++ (show $ last lst)
newOrGlue [[]] e = [[e]]
newOrGlue (curr:other) e | e == (1 + (head curr)) = ((e:curr):other)
newOrGlue (curr:other) e | otherwise = [e]:(curr:other)

y una ejecución de muestra:

T> runs [1,2,3,5,7,9,10,11,12,14]
["1-3","5","7","9-12","14"]

Answer 10

Transcripción de una sesión J interactiva (la entrada del usuario tiene una sangría de 3 espacios, el texto en cuadros ASCII es una salida J):

 g =: 3 : ''<@~."1((y~:1+({.,}:)y)#y),.(y~:(}.y,{:y)-1)#y''@/:~"1
g 1 2 3 4 5
+---+
|1 5|
+---+
g 1 2 3 5 7 9 10 11 12 14
+---+-+-+----+--+
|1 3|5|7|9 12|14|
+---+-+-+----+--+
g 12 2 14 9 1 3 10 5 11 7
+---+-+-+----+--+
|1 3|5|7|9 12|14|
+---+-+-+----+--+
g2 =: 4 : ''<(>x),'''' '''',>y''/@:>@:(4 :''<(>x),''''-'''',>y''/&.>)@((<@":)"0&.>@g)
g2 12 2 14 9 1 3 10 5 11 7
+---------------+
|1-3 5 7 9-12 14|
+---------------+
(;g2) 5 1 20 $ (i.100) /: ? 100 $ 100
+-----------------------------------------------------------+
|20 39 82 33 72 93 15 30 85 24 97 60 87 44 77 29 58 69 78 43|
| |
|67 89 17 63 34 41 53 37 61 18 88 70 91 13 19 65 99 81 3 62|
| |
|31 32 6 11 23 94 16 73 76 7 0 75 98 27 66 28 50 9 22 38|
| |
|25 42 86 5 55 64 79 35 36 14 52 2 57 12 46 80 83 84 90 56|
| |
| 8 96 4 10 49 71 21 54 48 51 26 40 95 1 68 47 59 74 92 45|
+-----------------------------------------------------------+
|15 20 24 29-30 33 39 43-44 58 60 69 72 77-78 82 85 87 93 97|
+-----------------------------------------------------------+
|3 13 17-19 34 37 41 53 61-63 65 67 70 81 88-89 91 99 |
+-----------------------------------------------------------+
|0 6-7 9 11 16 22-23 27-28 31-32 38 50 66 73 75-76 94 98 |
+-----------------------------------------------------------+
|2 5 12 14 25 35-36 42 46 52 55-57 64 79-80 83-84 86 90 |
+-----------------------------------------------------------+
|1 4 8 10 21 26 40 45 47-49 51 54 59 68 71 74 92 95-96 |
+-----------------------------------------------------------+

Legible y elegante están en el ojo del espectador: D

¡Fue un buen ejercicio! Sugiere el siguiente segmento de Perl:

sub g {
my ($i, @r, @s) = 0, local @_ = sort {$a<=>$b} @_;
$_ && $_[$_-1]+1 == $_[$_] || push(@r, $_[$_]),
$_<$#_ && $_[$_+1]-1 == $_[$_] || push(@s, $_[$_]) for 0..$#_;
join '' '', map {$_ == $s[$i++] ? $_ : "$_-$s[$i-1]"} @r;
}

Apéndice

En inglés simple, este algoritmo encuentra todos los elementos donde el artículo anterior no es uno menos, los usa para los límites inferiores; encuentra todos los artículos donde el próximo artículo no es uno mayor, los usa para los límites superiores; y combina las dos listas juntas elemento por elemento.

Como J es bastante oscuro, aquí hay una breve explicación de cómo funciona ese código:

x /: y ordena la matriz x en y . ~ puede hacer un verbo diádico en una mónada reflexiva, entonces /:~ significa "ordenar una matriz en sí mismo".

3 : ''...'' declara un verbo monádico (la forma de J de decir "función tomando un argumento"). @ significa composición de función, por lo que g =: 3 : ''...'' @ /:~ significa que " g se establece en la función que estamos definiendo, pero con su argumento ordenado primero". "1 dice que operamos en matrices, no en tablas ni nada de mayor dimensionalidad.

Nota: y es siempre el nombre del único argumento para un verbo monádico.

{. toma el primer elemento de una matriz (cabeza) y }: toma todo menos la última (reducción). ({.,}:)y efectivamente duplica el primer elemento de y y corta el último elemento. 1+({.,}:)y agrega 1 a todo, y ~: compara dos matrices, verdaderas donde sean diferentes y falsas donde sean iguales, entonces y~:1+({.,}:)y es una matriz que es verdadera en todos los índices de y donde un elemento no es igual a uno más que el elemento que lo precedió. (y~:1+({.,}:)y)#y selecciona todos los elementos de y donde la propiedad indicada en la oración anterior es verdadera.

Del mismo modo, }. toma todos menos el primer elemento de una matriz (descabezado) y {: toma la última (cola), por lo que }.y,{:y es todo menos el primer elemento de y , con el último elemento duplicado. (}.y,{:y)-1 resta 1 a todo, y de nuevo ~: compara dos matrices en función del elemento para la no igualdad, mientras que # selecciones.

,. comprime las dos matrices juntas, en una matriz de matrices de dos elementos. ~. coloca una lista (elimina duplicados) y recibe el "1 rango "1 , por lo que opera en las matrices internas de dos elementos en lugar de la matriz de nivel superior. Esto se compone @ con < , que coloca cada subcampo en una casilla (de lo contrario J ampliará cada subcampo nuevamente para formar una tabla 2D).

g2 es un desastre de boxeo y desempaquetado (de lo contrario, J rellenará cadenas de igual duración), y es bastante poco interesante.

Answer 11

Llego un poco tarde a la fiesta, pero de todos modos, aquí está mi versión usando Linq:

public static string[] FormatInts(IEnumerable<int> ints)
{
var intGroups = ints
.OrderBy(i => i)
.Aggregate(new List<List<int>>(), (acc, i) =>
{
if (acc.Count > 0 && acc.Last().Last() == i - 1) acc.Last().Add(i);
else acc.Add(new List<int> { i });
return acc;
});
return intGroups
.Select(g => g.First().ToString() + (g.Count == 1 ? "" : "-" + g.Last().ToString()))
.ToArray();
}

Answer 12

Erlang, también realiza una clasificación y una entrada única y puede generar un par reutilizable mediante programación y también una representación de cadena.

group(List) ->
[First|_] = USList = lists:usort(List),
getnext(USList, First, 0).
getnext([Head|Tail] = List, First, N) when First+N == Head ->
getnext(Tail, First, N+1);
getnext([Head|Tail] = List, First, N) ->
[ {First, First+N-1} | getnext(List, Head, 0) ];
getnext([], First, N) -> [{First, First+N-1}].
%%%%%% pretty printer
group_to_string({X,X}) -> integer_to_list(X);
group_to_string({X,Y}) -> integer_to_list(X) ++ "-" ++ integer_to_list(Y);
group_to_string(List) -> [group_to_string(X) || X <- group(List)].

Prueba para obtener pares reutilizables por programa:

shell> testing: group ([34,3415,56,58,57,11,12,13,1,2,3,3,4,5]).

resultado> [{1,5}, {11,13}, {34,34}, {56,58}, {3415,3415}]

Prueba de obtener una secuencia "bonita":

shell> testing: group_to_string ([34,3415,56,58,57,11,12,13,1,2,3,3,4,5]).

resultado> ["1-5", "11-13", "34", "56-58", "3415"]

espero que ayude adiós

Answer 13

Consulte ¿Cómo mostraría una matriz de enteros como un conjunto de rangos? (algoritmo)

Mi respuesta a la pregunta anterior:

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");
}