Identify groups of varying continuous numbers in a list
<p>In this <a href="https://stackoverflow.com/questions/2154249/identify-groups-of-continuous-numbers-in-a-list">other SO post</a>, a Python user asked how to group continuous numbers such that any sequences could just be represented by its start/end and any stragglers would be displayed as single items. The accepted answer works brilliantly for continuous sequences.</p>

<p>I need to be able to adapt a similar solution but for a sequence of numbers that have potentially (not always) varying increments. Ideally, how I represent that will also include the increment (so they'll know if it was every 3, 4, 5, nth)</p>

<p>Referencing the original question, the user asked for the following input/output</p>

<pre><code>[2, 3, 4, 5, 12, 13, 14, 15, 16, 17, 20]  # input
[(2,5), (12,17), 20]
</code></pre>

<p>What I would like is the following (Note: I wrote a tuple as the output for clarity but xrange would be preferred using its step variable):</p>

<pre><code>[2, 3, 4, 5, 12, 13, 14, 15, 16, 17, 20]  # input
[(2,5,1), (12,17,1), 20]  # note, the last element in the tuple would be the step value
</code></pre>

<p>And it could also handle the following input</p>

<pre><code>[2, 4, 6, 8, 12, 13, 14, 15, 16, 17, 20]  # input
[(2,8,2), (12,17,1), 20]  # note, the last element in the tuple would be the increment
</code></pre>

<p>I know that <code>xrange()</code> supports a step so it may be possible to even use a variant of the other user's answer. I tried making some edits based on what they wrote in the explanation but I wasn't able to get the result I was looking for.</p>

<p>For anyone that doesn't want to click the original link, the code that was originally posted by <a href="https://stackoverflow.com/users/97828/nadia-alramli">Nadia Alramli</a> is:</p>

<pre><code>ranges = []
for key, group in groupby(enumerate(data), lambda (index, item): index - item):
    group = map(itemgetter(1), group)
    if len(group) &gt; 1:
        ranges.append(xrange(group[0], group[-1]))
    else:
        ranges.append(group[0])
</code></pre>

<p>Here is a quickly written (and extremely ugly) answer:</p>

<pre><code>def test(inArr):
    arr=inArr[:] #copy, unnecessary if we use index in a smart way
    result = []
    while len(arr)&gt;1: #as long as there can be an arithmetic progression
        x=[arr[0],arr[1]] #take first two
        arr=arr[2:] #remove from array
        step=x[1]-x[0]
        while len(arr)&gt;0 and x[1]+step==arr[0]: #check if the next value in array is part of progression too
            x[1]+=step #add it
            arr=arr[1:]
        result.append((x[0],x[1],step)) #append progression to result
    if len(arr)==1:
        result.append(arr[0])
    return result

print test([2, 4, 6, 8, 12, 13, 14, 15, 16, 17, 20])
</code></pre>

<p>This returns <code>[(2, 8, 2), (12, 17, 1), 20]</code></p>

<p>Slow, as it copies a list and removes elements from it</p>

<p>It only finds complete progressions, and only in sorted arrays.</p>

<p>In short, it is shitty, but should work ;)</p>

<p>There are other (cooler, more pythonic) ways to do this, for example you could convert your list to a set, keep removing two elements, calculate their arithmetic progression and intersect with the set.</p>

<p>You could also reuse the answer you provided to check for <strong>certain</strong> step sizes. e.g.:</p>

<pre><code>ranges = []
step_size=2
for key, group in groupby(enumerate(data), lambda (index, item): step_size*index - item):
    group = map(itemgetter(1), group)
    if len(group) &gt; 1:
        ranges.append(xrange(group[0], group[-1]))
    else:
        ranges.append(group[0])
</code></pre>

<p>Which finds every group with <strong>step size</strong> of <em>2</em>, but only those.</p>

python