Chunking sequential values in a list

[David Hirschfield]

I have this function:

def sequentialChunk s(l, stride=1):
chunks = []
chunk = []
for i,v in enumerate(l[:-1]):
v2 = l[i+1]
if v2-v == stride:
if not chunk:
chunk.append(v)
chunk.append(v2 )
else:
if not chunk:
chunk.append(v)
chunks.append(c hunk)
chunk = []
if chunk:
chunks.append(c hunk)
return chunks

Which takes a list of numerical values "l" and splits it into chunks
where each chunk is sequential, where sequential means each value in a
chunk is
separated from the next by "stride".

So sequentialChunk s([1,2,3,5,6,8,12]) returns:

[[1,2,3],[5,6],[8],[12]]

I don't think the code above is the most efficient way to do this, but
it is relatively clear. I tried fiddling with list-comprehension ways of
accomplishing it, but kept losing track of things...so if anyone has a
suggestion, I'd appreciate it.

Thanks,
-Dave


--
Presenting:
mediocre nebula.

[bearophileHUGS@lycos.com]

Re: Chunking sequential values in a list

It looks like homework. Sometimes the simpler code is better:

def splitter(seq):
if not seq:
return []
result = []
current = [seq[0]]
for pos, el in enumerate(seq[1:]):
if el - current[-1] 1:
result.append(c urrent[:])
current = []
current.append( el)
result.append(c urrent)
return result

print splitter([1, 2, 3, 5, 6, 8, 12])
print splitter([1, 1, 1, 2, 2, 5, 6])
print splitter([1, 1, 1, 1, 1, 1, 1])
print splitter([1, 2, 3])
print splitter([1])
print splitter([])
print splitter([1.0, 1.1, 1.99, 4.01])
print splitter([1.0, 2.0, 3.0, 4.01])

To reduce memory used you can use islice instead of the slice seq[1:]
If you want something less easy to understand, you can try fixing the
following code that doesn't work:

from itertools import groupby
l = [1,2,3,5,6,8,12]
keyf = lambda (pos,x): x-l[pos]>1
[[el[1] for el in gr] for he,gr in groupby(enumera te(l[:-1]), keyf)]

Bye,
bearophile

[Gerard Flanagan]

Re: Chunking sequential values in a list


David Hirschfield wrote:

I have this function:
>
def sequentialChunk s(l, stride=1):
chunks = []
chunk = []
for i,v in enumerate(l[:-1]):
v2 = l[i+1]
if v2-v == stride:
if not chunk:
chunk.append(v)
chunk.append(v2 )
else:
if not chunk:
chunk.append(v)
chunks.append(c hunk)
chunk = []
if chunk:
chunks.append(c hunk)
return chunks
>
Which takes a list of numerical values "l" and splits it into chunks
where each chunk is sequential, where sequential means each value in a
chunk is
separated from the next by "stride".
>
So sequentialChunk s([1,2,3,5,6,8,12]) returns:
>
[[1,2,3],[5,6],[8],[12]]
>
I don't think the code above is the most efficient way to do this, but
it is relatively clear. I tried fiddling with list-comprehension ways of
accomplishing it, but kept losing track of things...so if anyone has a
suggestion, I'd appreciate it.
>

see the groupby example here:

http://docs.python.org/lib/itertools-example.html

Gerard

[skip@pobox.com]

Re: Chunking sequential values in a list


GerardDavid Hirschfield wrote:

>I have this function:
>>
>def sequentialChunk s(l, stride=1):

...

>>
>Which takes a list of numerical values "l" and splits it into chunks
>where each chunk is sequential...

Gerardsee the groupby example here:

Gerardhttp://docs.python.org/lib/itertools-example.html

I've never been a fan of the operator module, so I find the example in the
docs ugly even though it's succinct. I'd also never used groupby but
thought it was the solution to the problem. As I was walking home from the
train I realized how it would work. You beat me to the punch with your
reply, but I'll post my solution anyway:

from itertools import groupby

class Counter:
def __init__(self):
self.last = None
self.value = True

def __call__(self, val):
if self.last is not None and self.last+1 != val:
self.value = not self.value
self.last = val
return self.value

for key, group in groupby([1,2,3, 5,6, 8, 12,13,14], Counter()):
print list(group)

Skip

[Paul Rubin]

Re: Chunking sequential values in a list

David Hirschfield <davidh@ilm.com writes:

So sequentialChunk s([1,2,3,5,6,8,12]) returns:
[[1,2,3],[5,6],[8],[12]]

Ugly and not too efficient: find the break points and use them to make
sub-lists.

def sequentialChunk s(l, stride=1):
p = [0] + [i for i in xrange(1,len(l) ) if l[i]-l[i-1] != stride] + [len(l)]
return [l[p[i]:p[i+1]] for i in xrange(len(p)-1)]

print sequentialChunk s([1,2,3,5,6,8,12])

[Gerard Flanagan]

Re: Chunking sequential values in a list


skip@pobox.com wrote:

GerardDavid Hirschfield wrote:

>I have this function:
>>
>def sequentialChunk s(l, stride=1):

...

>>
>Which takes a list of numerical values "l" and splits it into chunks
>where each chunk is sequential...

>
Gerardsee the groupby example here:
>
Gerardhttp://docs.python.org/lib/itertools-example.html
>
I've never been a fan of the operator module, so I find the example in the
docs ugly even though it's succinct. I'd also never used groupby but
thought it was the solution to the problem. As I was walking home from the
train I realized how it would work. You beat me to the punch with your
reply, but I'll post my solution anyway:
>
from itertools import groupby
>
class Counter:
def __init__(self):
self.last = None
self.value = True
>
def __call__(self, val):
if self.last is not None and self.last+1 != val:
self.value = not self.value
self.last = val
return self.value
>
for key, group in groupby([1,2,3, 5,6, 8, 12,13,14], Counter()):
print list(group)
>

I've no strong feelings about the operator module myself, or the
groupby example, but I do prefer your code in this case. I tweaked it
a little to take into account the stride, though I'm not sure it gives
what the OP wants.

all the best

Gerard

-----------------------------

class Counter:
def __init__(self, stride=1):
self.last = None
self.value = True
self.stride = stride

def __call__(self, val):
if self.last is not None:
d = val - self.last
if d self.stride:
self.value = not self.value
self.last = val
return self.value

def group(data,stri de=1):
for key, group in groupby(data, Counter(stride) ):
yield list(group)

-----------------------------------

[Gerard Flanagan]

Re: Chunking sequential values in a list


David Hirschfield wrote:

I have this function:
>
def sequentialChunk s(l, stride=1):
chunks = []
chunk = []
for i,v in enumerate(l[:-1]):
v2 = l[i+1]
if v2-v == stride:
if not chunk:
chunk.append(v)
chunk.append(v2 )
else:
if not chunk:
chunk.append(v)
chunks.append(c hunk)
chunk = []
if chunk:
chunks.append(c hunk)
return chunks
>
Which takes a list of numerical values "l" and splits it into chunks
where each chunk is sequential, where sequential means each value in a
chunk is
separated from the next by "stride".
>
So sequentialChunk s([1,2,3,5,6,8,12]) returns:
>
[[1,2,3],[5,6],[8],[12]]
>
I don't think the code above is the most efficient way to do this, but
it is relatively clear. I tried fiddling with list-comprehension ways of
accomplishing it, but kept losing track of things...so if anyone has a
suggestion, I'd appreciate it.
>

Gerard wrote:

>see the groupby example here:
>
http://docs.python.org/lib/itertools-example.html

tweaking the example from the docs to take the stride into account:

def stride(length):
i = 0
while True:
yield i
i += length

def group(data,d=1) :
for k, g in groupby(zip(str ide(d),data), lambda (i,x):i-x):
yield map(operator.it emgetter(1), g)

data = [1,2,3, 5, 6, 8, 12,13,14]

print list( group( data,2 ) )

hth

Gerard

[Peter Otten]

Re: Chunking sequential values in a list

bearophileHUGS@ lycos.com wrote:

If you want something less easy to understand, you can try fixing the
following code that doesn't work:
>
from itertools import groupby
l = [1,2,3,5,6,8,12]
keyf = lambda (pos,x): x-l[pos]>1
[[el[1] for el in gr] for he,gr in groupby(enumera te(l[:-1]), keyf)]

>>from itertools import groupby
>>items = [1, 2, 3, 5, 6, 8, 12]
>>[[v for i, v in group] for key, group in groupby(enumera te(items),

lambda (i, v): i-v)]
[[1, 2, 3], [5, 6], [8], [12]]

which is almost identical to the last example in

http://docs.python.org/lib/itertools-example.html

Peter

[bearophileHUGS@lycos.com]

Re: Chunking sequential values in a list

Peter Otten:

which is almost identical to the last example in
http://docs.python.org/lib/itertools-example.html

I see, thank you. I haven't had enoug time and brain to fix it (and the
OP question seemed like homework, so leaving some other things to do is
positive).

I think still that too much clever code can be bad, it isn't easy to
understand, fix and modify if you need something a little different.
To solve such problem in 'production code' I probably prefer a longer
function like the one I have shown.

Bye,
bearophile