Алгоритм смежных чисел

Question

Под этим я подразумеваю:

При заданном наборе чисел:

1,2,3,4,5 становится "1-5".

1,2,3,5,7,9,10,11,12,14 становится "1-3, 5, 7, 9-12, 14"

Это лучшее, что мне удалось придумать: [C #]

Что кажется мне немного неаккуратным, поэтому вопрос в том, есть ли более удобочитаемое и / или элегантное решение для этого?

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

Perl

С проверкой ввода / предварительной сортировкой

Вы можете легко получить результат в виде LoL, если вам нужно сделать что-то более необычное, чем просто верните строку.

#!/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";

Выход:

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

И хорошее рекурсивное решение:

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 2

Мне ясно и понятно. Вы можете немного упростить ситуацию, если предположите, что входной массив отсортирован, или сортируйте его самостоятельно перед дальнейшей обработкой.

Единственный твик, который я бы предложил, - это отменить вычитание:

int difference = (current - lastNumber);

... просто потому, что мне легче работать с положительными различиями. Но ваш код приятно читать!

Answer 3

1001 * 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")
Возврат: "1-3,7-9,11-12,99-101"