Grouping consecutive numbers into ranges in Python 3.2

The following is a function that I wrote to display page numbers as they appear in books.

If you enter the list [1,2,3,6,7,10], for example, it would return:

1-3,6-7,10


This seemed like a nice example of how the dictionary data type can be used in Python.

Is there is an even more code-efficient way to do this?

def formatpagelist (numberlist):
tempdic={}
returnstring=''

for number in numberlist:
if number-1 in tempdic.keys():
tempdic[number-1]=number
elif number-1 in tempdic.values():
for key in tempdic.keys():
if number-1==tempdic[key]: foundkey=key
tempdic[foundkey]=number
else:
tempdic[number]=0

keylist=list(tempdic.keys())
keylist.sort()

for key in keylist:
if tempdic[key]>0:
returnstring+=(str(key)+'-'+str(tempdic[key])+',')
else: returnstring+=str(key)+','

return returnstring

-

You could use this one-liner to generate groups of consecutive integers in a list:

from itertools import groupby, count

groupby(numberlist, lambda n, c=count(): n-next(c))


Then to finish it off, generate the string from the groups.

def as_range(iterable): # not sure how to do this part elegantly
l = list(iterable)
if len(l) > 1:
return '{0}-{1}'.format(l[0], l[-1])
else:
return '{0}'.format(l[0])

','.join(as_range(g) for _, g in groupby(numberlist, key=lambda n, c=count(): n-next(c)))
# '1-3,6-7,10'


This assumes they are in sorted order and there are no duplicates. If not sorted, add a sorted() call on numberlist beforehand. If there's duplicates, make it a set beforehand.

-
You'll never hit that IndexError. If len(l) == 1 then l[0] == l[-1] and you'll never get IndexError –  Winston Ewert Oct 6 '11 at 0:11
Ah, thanks for pointing that out. That was a last minute change and I mixed up one idea for another. –  Jeff Mercado Oct 6 '11 at 1:05
+1 for the enumerate + groupby pattern to group consecutive elements (I think to recall it's somewhere in the docs) –  tokland Dec 24 '11 at 0:38
FWIW, the output feature of intspan uses this technique. –  Jonathan Eunice Jan 12 '13 at 15:59

A bit shorter version without using a dictionary:

def formatpagelist(numberlist):
prev_number = min(numberlist) if numberlist else None
pagelist = list()

for number in sorted(numberlist):
if number != prev_number+1:
pagelist.append([number])
elif len(pagelist[-1]) > 1:
pagelist[-1][-1] = number
else:
pagelist[-1].append(number)
prev_number = number

return ','.join(['-'.join(map(str,page)) for page in pagelist])

-
def formatpagelist (numberlist):


The python style guide recommends words_with_underscores for function names.

    tempdic={}


This is a really bad variable name. It tells me nothing about what the variable is used for. It tells me the variable is temporary (like all variables) and that its a dict, which obvious given the {}

    returnstring=''


This doesn't show up until way later... Why is it here?

    for number in numberlist:
if number-1 in tempdic.keys():


This is the same as number - 1 in tempdic:

            tempdic[number-1]=number
elif number-1 in tempdic.values():
for key in tempdic.keys():
if number-1==tempdic[key]: foundkey=key


If you've got scan over the keys of a dictionary, that is a sign you probably shouldn't be using a dictionary.

            tempdic[foundkey]=number
else:
tempdic[number]=0

keylist=list(tempdic.keys())
keylist.sort()


This the same thing as keylist = sorted(tempdic)

    for key in keylist:
if tempdic[key]>0:
returnstring+=(str(key)+'-'+str(tempdic[key])+',')
else: returnstring+=str(key)+','


I think putting those on one line makes it harder to read. You are usually better off building a list and then joining the list.

    return returnstring


Here is another approach: I stole parts from @Jeff, but I wanted to try a different approach.

import collections

pages = [1,2,5,6,7,9]
starts = collections.OrderedDict()
ends = collections.OrderedDict()
for idx, page in enumerate(pages):
section = page - idx
starts.setdefault(section, page)
ends[section] = page
page_parts = []
for section, start in starts.items():
end = ends[section]
if start == end:
page_parts.append("{0}".format(start))
else:
page_parts.append("{0}-{1}".format(start, end))
print(','.join(page_parts))

-
all good points! I really have to learn python naming conventions...And I think you are basically right that using a dictionary is kind of pointless when you have to reverse-search on the values. It is also probably a waste of memory here, since you are storing information when there is actually no need to. –  Anthony Curtis Adler Oct 6 '11 at 4:03

Your use of the dictionary seems to be a way to allow the numbers to arrive out-of-order. Rather than sort them, you seem to be trying to use a dictionary (and associated hashing) to maximize efficiency.

This doesn't really work out perfectly, since you wind up doing sequential searches for a given value.

Hashing a low:high range (a dictionary key:value pair) to avoid a search doesn't help much. Only they key gets hashed. It does help in the case where you're extending a range at the low end. But for extending a range at the high end, you have to resort to searches of the dictionary values.

What you're really creating is a collection of "partitions". Each partition is bounded by a low and high value. Rather than a dictionary, you can also use a trivial tuple of (low, high). To be most Pythonic, the (low,high) pair includes the low, but does not include the high. It's a "half-open interval".

Here's a version using a simple set of tuples, relying on hashes instead of bisection.

A binary search (using the bisect module) may perform well, also. It would slightly simplify adjacent range merging, since the two ranges would actually be adjacent. However, this leads to a cost in restructuring the sequence.

You start with an empty set of partitions, the first number creates a trivial partition of just that number.

Each next number can lead to one of three things.

1. It extends an existing partition on the low end or high end. The number is adjacent to exactly one range.

2. It creates a new partition. The number is not adjacent to any range.

3. It "bridges" two adjacent partitions, combining them into one. The number is adjacent to two ranges.

It's something like this.

def make_ranges(numberlist):
ranges=set()
for number in numberlist:
print ranges, number
adjacent_to = set( r for r in ranges if r[0]-1 == number or r[1] == number )
r = (number,number+1)
assert r[0] <= number < r[1] # Trivial, right?
# Extend this partition, build a new range.
if r[0]-1 == number: # Extend low end
r= (number,r[1])
else:
r= (r[0],number+1) # Extend high end
assert r[0] <= number < r[1]
r = ( min(r0[0],r1[0]), max(r0[1],r1[1]) )
assert r[0] <= number < r[1]
return ranges


This is a pretty radical rethinking of your algorithm, so it's not a proper code review.

Assembling a string with separators is simpler in Python. For your example of ","-separated strings, always think of doing it this way.

final = ",".join( details )


Once you have that, you're simply making a sequence of details. In this case, each detail is either "x-y" or "x" as the two forms that a range can take.

So it has to be something like

details = [ format_a_range(r) for r in ranges ]


In this example, I've shown the format as an in-line def. It can be done as an if-else expression, also.

Given your ranges, the overall function is this.

def formatpagelist (numberlist):
ranges= make_ranges( numberlist )
def format_a_range( low, high ):
if low == high-1: return "{0}".format( low )
return "{0}-{1}".format( low, high-1 )
strings = [ format_a_range(r) for r in sorted(ranges) ]
return ",".join( strings )

-
thank you. this is a very interesting approach... I think I have to study it to see how it really works. But I like the idea of tuples. Your remark about the advantages of using a dictionary got me to think of another way of doing it without having to sort. I added the new version above. –  Anthony Curtis Adler Oct 7 '11 at 13:30
@AnthonyCurtisAdler: It's very, very hard to comment on two pieces of code. Please post the second one separately. Also, your algorithm does not appear to handle the [ 1, 2, 4, 5, 3 ] case correctly. It might -- I didn't test it -- but it's an easy case to miss. –  S.Lott Oct 7 '11 at 14:40
I posted a new version. I tested it with a long set, and included the test call. –  Anthony Curtis Adler Oct 7 '11 at 15:10
@AnthonyCurtisAdler: "a long set"? Large is not a good thing for test cases. Small and specific is a good thing. –  S.Lott Oct 7 '11 at 15:20
thank you! --- i really appreciate your comments. I've been learning a lot. I posted a new version which addresses the specific criticisms, and also slightly changes the algorithm to avoid the inefficiency. Though now it converts the set into a list, which means that it will run a sorting procedure. I am also curious if there would be a more efficient way to iterate over the set, such as using an iter() instead of listing the set. –  Anthony Curtis Adler Oct 7 '11 at 23:04