代码之家 › 专栏 › 技术社区 › arul

相邻数算法分组器

language-agnostic algorithm

arul · 技术社区 · 16 年前

我的意思是:

给定输入的数字集:

1、2、3、4、5变为“1-5”。

1、2、3、5、7、9、10、11、12、14变为“1-3、5、7、9-12、14”

这是我所能想到的最好的办法。

我觉得这有点草率,所以问题是,是否有更可读和/或优雅的解决方案?

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

13 回复 | 直到 10 年前

cjm 16 年前

我这样重写了你的代码:

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

然后:

/////////////////
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"

Community CDub 8 年前

见 How would you display an array of integers as a set of ranges? (algorithm)

My answer 对于上述问题:

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

Deestan 16 年前

纯功能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"

Geert Baeyaert 15 年前

我参加聚会有点晚了,但无论如何,这是我使用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();
}

Adam Liss 16 年前

在我看来很清楚和直截了当。如果假定输入数组已排序,或者在进一步处理之前自己排序,则可以简化一点。

我建议的唯一的调整是反转减法:

int difference = (current - lastNumber);

…仅仅因为我发现积极的差异更容易工作。但你的代码是一个愉快的阅读!

PhiLho 16 年前

正如我在评论中所写,我不喜欢使用值0作为标志,使firstnumber同时成为一个值和一个标志。

我在Java中快速实现了该算法,大胆跳过了您已经正确覆盖的有效性测试…

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

当然,我不会说它比你的算法更优雅/高效……只是一些不同的东西。

请注意,1,5,6,9可以写为1,5-6,9或1,5,6,9,不确定哪种更好(如果有的话)。

我记得我做过类似的事情(在C中),将消息编号分组到IMAP范围,因为它更有效。一种有用的算法。

Robert Krimen 16 年前

珀尔

带输入验证/预排序

如果你需要做一些比这更有趣的事情,你可以很容易地得到一个棒棒糖的结果。只需返回一个字符串。

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

}

madlep 16 年前

短而甜的红宝石

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

ephemient 16 年前

我的第一个想法,在巨蟒:

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))

可能更干净,但还是很容易的。

简单翻译为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

差不多一样。

ephemient 16 年前

互动的抄本 J 会话(用户输入缩进3个空格,ASCII框中的文本为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      |
+-----------------------------------------------------------+

在旁观者的眼中,可读性和优雅性:d

那是个很好的练习!它建议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;
}

补遗

在纯英语中,该算法查找前一项不少于一项的所有项,并将其用于下限;查找下一项不大于一项的所有项,并将其用于上限;并将两个列表逐项组合在一起。

由于j非常模糊,下面简单解释一下代码是如何工作的:

x /: y 排序数组 x 在 y . ~ 能使二元动词变成反身单子,所以 /:~ 表示“对数组本身进行排序”。

3 : '...' 声明一个单态动词(j表示“函数接受一个参数”的方式)。 @ 表示函数组成,所以 g =: 3 : '...' @ /:~ 意味着“ g 设置为我们定义的函数,但首先对其参数排序”。 "1 说我们是在数组上操作的,而不是表或任何更高维度的。

注: Y 总是一元动词的唯一参数名。

{. 获取数组(head)的第一个元素并 }: 只接受最后一个(限功率)。 ({.,}:)y 有效地复制 Y 去掉最后一个元素。 1+({.,}:)y 全部添加1,并且 ~: 比较两个数组,无论它们是不同的是真的,还是相同的是假的,所以 y~:1+({.,}:)y 是一个数组,它在 Y 其中一个元素不等于它前面的元素多一个。 (y~:1+({.,}:)y)#y 选择的所有元素 Y 前句所述财产为真的。

同样地, }. 获取数组(behead)的第一个元素以外的所有元素, {: 最后一个(尾巴),所以 }.y,{:y 除了第一个元素 Y ,最后一个元素重复。 (}.y,{:y)-1 全部减去1,然后再次 ~ 比较两个数组的不相等项,同时 # 挑选。

,. 将两个数组压缩到一个由两个元素数组组成的数组中。 ~. nubs一个列表(消除重复项),并给出 “1 排名,因此它在内部的两个元素数组上操作,而不是顶级数组。这是 @ 组成 < 将每个子数组放入一个框中(否则J将再次扩展每个子数组以形成一个二维表)。

g2 是一团糟的拳击和拆箱(否则J将垫字符串等长),是相当无趣的。

ja. 16 年前

这是我的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)

以及一个样本运行:

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

["1-3","5","7","9-12","14"]

emaxt6 14 年前

Erlang还可以对输入进行排序和唯一性,并且可以生成可编程的可重用对以及字符串表示。

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)].

测试获取可编程重用对:

Shell>测试:组([343415,56,58,57,11,12,13,1,2,3,3,4,5])。

结果>[1,5,11,13,34,34,56,58,34153415]

测试获取“漂亮”字符串:

Shell>测试:组“到”字符串([343415,56,58,57,11,12,13,1,2,3,3,4,5])。

结果>[“1-5”,“11-13”,“34”,“56-58”,“3415”]

希望它有帮助再见

Christopher Thomas Nicodemus 10 年前

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,99100101”)。
返回:“1-3,7-9,11-12,99-101”