كيف يمكنك عرض مجموعة من الأعداد الصحيحة كمجموعة من النطاقات؟(خوارزمية)

Question

بالنظر إلى مجموعة من الأعداد الصحيحة، ما هي أبسط طريقة للتكرار عليها ومعرفة جميع النطاقات التي تغطيها؟على سبيل المثال، لمصفوفة مثل:

$numbers = array(1,3,4,5,6,8,11,12,14,15,16);

النطاقات ستكون:

 1,3-6,8,11-12,14-16

Answer 1

إذا تم فرز المصفوفة بترتيب تصاعدي، فستكون المشكلة سهلة.تعريف أ Range هيكل أو فئة، والتي لها بداية ونهاية.ثم انتقل من خلال المصفوفة.إذا كان العنصر الحالي أكثر من العنصر السابق، فقم بالتحديث Range.end, وإلا قم بإنشاء نطاق جديد بهذا العنصر كـ Range.begin.قم بتخزين النطاقات في مصفوفة ديناميكية أو قائمة مرتبطة.أو قم فقط بطباعتها كما تذهب.

إذا لم يتم فرز المصفوفة، فقم بفرزها أولاً.

Answer 2

إليك طريقة C# 3.0 للقيام بذلك:

النقاط المثيرة للاهتمام:

• الخصائص التلقائية ( public int Property { get;تعيين؛})
• استخدام مُهيئات الكائنات الجديدة (new Range { Begin = xxx;...}
• باستخدام العائد للتقييم كسول
• باستخدام طرق ملحق linq (First() و 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;
    }
}

في صحتك، ديفيد

Answer 3

إليك تطبيق بايثون، يجب أن يكون من السهل متابعته

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

هذه المخرجات:

1
3-6
8
11-12
14-16

أعلم، أعلم، أنها ليست خوارزمية, ، لكنني وجدت أنه من الصعب شرح ذلك دون وجود مشاكل في المسافة البادئة بدلاً من مجرد تنفيذ حل له.

Answer 4

أولاً:فرز ثانية:رمز ثم:اطبع القيمة الأولى ثم كررها فوق القيم اللاحقة.إذا كانت القيمة "الحالية" تساوي القيمة الأخيرة +1، فتخطاها.بخلاف ذلك، إذا تخطيت القيمة، فاطبع الشرطة والقيمة، وإلا فاطبع فاصلة وكرر الأمر.

يجب أن تفعل ذلك.إلا إذا كنت تريد مني أن أقوم بترميز واجباتك المنزلية لك؟:)

Answer 5

إذا تم فرز المصفوفة، كما في المثال الخاص بك، فسأحدد مجموعات تحتوي على الحد الأدنى والحد الأقصى.

التهيئة:قم بإنشاء مجموعة تحتوي على الحد الأدنى والحد الأقصى يساوي القيمة الأولى.

حلقة:قارن كل قيمة مع الحد الأقصى للمجموعة الحالية.إذا كان يساوي أو 1 أكثر من الحد الأقصى الحالي، قم بتحديث الحد الأقصى.إذا كان أكبر من الحد الأقصى بأكثر من 1، فاحفظ المجموعة في قائمة المجموعات وابدأ مجموعة جديدة.

في النهاية سيكون لديك مجموعة من الدلاء تحتوي كل منها على حد أدنى وحد أقصى.إذا كان الحد الأدنى هو نفس الحد الأقصى، فاطبع رقمًا واحدًا (على سبيل المثال:في المثال الخاص بك، سيكون للمجموعة الأولى الحد الأدنى والحد الأقصى 1).إذا كانت مختلفة، طباعة كنطاق.

مثال على التنفيذ في 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> 

في الأساس، ينتهي بك الأمر بقائمة من الأشياء، حيث يحتوي كل شيء على (الأقل في المجموعة، والأعلى في المجموعة).تلك هي النطاقات الخاصة بك.

إذا لم تكن القائمة قد تم فرزها بالفعل، فقم بفرزها أولاً.

Answer 6

ج (دول مجلس التعاون الخليجي)

انه ايضا مشابه نسخة بايثون.

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

مثال:

/**
 * $ 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);
}

انتاج:

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

Answer 7

بافتراض أن القائمة مرتبة، يمكنك البدء من النهاية والاستمرار في طرح القائمة التالية لأسفل.بينما الفرق هو 1، أنت في نطاق.عندما لا يكون الأمر كذلك، تبدأ مجموعة جديدة.

أي

16-15 = 1

15-14 = 1

14-12 = 2، النطاق هو 16-14 - ابدأ نطاقًا جديدًا.

Answer 8

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

Answer 9

هذا هو حل بيرل الخاص بي.يمكن أن يكون أنظف وأسرع، لكنه يوضح كيفية عمله:

# 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 = [ $_ ];
    }
}

Answer 10

الحل الخاص بي في Java 1.5 سيكون:

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

الذي يخرج:

[1, 3-6, 8, 11-12, 14-16]

غريتز، غاد

Answer 11

أعتقد أن خاصية mergeinfo التي تم تقديمها إلى Subversion في الإصدار 1.5 لها تنسيق مماثل لما تطلبه، لذلك من المحتمل أن تتمكن من البحث في مصدر Subversion لمعرفة كيفية القيام بذلك.سأكون مندهشًا إذا كان الأمر مختلفًا عن الاقتراحات الأخرى التي تم نشرها هنا بالفعل.

Answer 12

سأفترض أن المصفوفة X() تم فرزها مسبقًا (وإذا لم تكن كذلك، فقم بفرز المصفوفة مسبقًا).

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

حسنًا، هذه هي الطريقة التي سأفعل بها ذلك.

Answer 13

قم بإنشاء نوع نطاق بسيط يحتوي على قيم بداية/نهاية النطاق.أضف مُنشئًا يأخذ قيمة واحدة فقط ويحدد قيمة البداية = النهاية = القيمة.احتفظ بمجموعة من كائنات النطاق، أو شق طريقك من خلال نسخة مرتبة من المصفوفة، أو قم بتوسيع النطاق العلوي أو أضف نطاقًا جديدًا حسب الاقتضاء.وبشكل أكثر تحديدًا، عندما تكون القيمة في المصفوفة هي 1 + القيمة النهائية لكائن النطاق الموجود في المكدس، قم بزيادة القيمة النهائية لهذا النطاق، وعندما لا تكون كذلك، ادفع نطاقًا جديدًا (بقيمة start = end = at الفهرس في الصفيف) على المكدس.

Answer 14

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

هذه أفضل لقطة لي في هاسكل.

Answer 15

بيرل 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;
}

Answer 16

بايثون (>= 2.6)

يعالج هذا الإصدار أيضًا التكرارات والتسلسلات غير المصنفة.

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

مثال:

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

انتاج:

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