Group Consecutive Integers Together

Have the following code: import sys ints = [1,2,3,4,5,6,8,9,10,11,14,34,14,35,16,18,39,10,29,30,14,26,64,27,48,65] ints.sort() ints = list(set(ints)) c = {} for i,v in enumerat

Solution 1:

As you have lists of consecutive numbers, I suggest you to use range objects instead of lists:

d, head = {}, None
for x in l:
    ifhead is None or x != d[head].stop:
        head = x
    d[head] = range(head, x+1)

Solution 2:

The solution is simple if you use a for loop and just keep track of your current list. Don't forget to make a new list when you find a gap:

result = {}
cl = Nonefor i in ints:
    if cl isNoneor i - 1 != cl[-1]:
        cl = result.setdefault(i, [])
    cl.append(i)

Solution 3:

There is a great library called more_itertools which has a method called: consecutive_groups():

import more_itertools as mit
x = [1,2,3,4,5,6,8,9,10,11,14,34,14,35,16,18,39,10,29,30,14,26,64,27,48,65]
x = [list(j) for j in mit.consecutive_groups(sorted(list(set(x))))]
# [[1, 2, 3, 4, 5, 6], [8, 9, 10, 11], [14], [16], [18], [26, 27], [29, 30], [34, 35], [39], [48], [64, 65]]
dct_x = {i[0]: i for i in x}
print(dct_x)

Output:

{1: [1, 2, 3, 4, 5, 6], 8: [8, 9, 10, 11], 14: [14], 16: [16], 18: [18], 26: [26, 27], 29: [29, 30], 34: [34, 35], 39: [39], 48: [48], 64: [64, 65]}

One more comment, you want to sort after converting to and from a set, since sets are unordered.

Solution 4:

One can solve this task in O(n) (linear) complexity. Just keep it simple:

integers = [1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 14, 16, 18, 26, 27, 29, 30, 34, 35, 39, 48, 64, 65]

helper = []
counter = 0while counter < len(integers):
  ifnot helper or helper[-1] + 1 != integers[counter]:
    print('gap found', integers[counter])  # do your logic
  helper.append(integers[counter])
  counter += 1

The algorithm above assumes that the input list is already sorted. It gives us a huge advantage. At the same time one can sort the list of integers explicitly before running this algorithm. The total complexity of the solution will be then: O(n * log n) + O(n) which is efficiently O(n * log n). And O(n * log n) is the complexity of the sorting procedure.

I would kindly suggest to remember this extremely useful trick of using sorting before approaching a task for future usages.

Solution 5:

Here's a simple implementation that achieves what you are after, using list slicing:

integers= [1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 14, 16, 18, 26, 27, 29, 30, 34, 35, 39, 48, 64, 65]
fori,integerinenumerate(integers):ifi==0:out_dict= {}
        start=0else:ifinteger!=prev_integer+1:out_dict[integers[start]]=integers[start:i]start=iifi==len(integers)-1:out_dict[integers[start]]=integers[start:]prev_integer=integer>>>out_dict=  {1: [1, 2, 3, 4, 5, 6], 8: [8, 9, 10, 11], 14: [14], 16: [16], 18: [18], 26: [26, 27], 29: [29, 30], 34: [34, 35], 39: [39], 48: [48], 64: [64]}

Note: The dictionary will likely not be sorted by ascending keys, as dict types are not ordered.