get the sum of differences between integers in a list

[marco.nawijn at colosso.nl]

On Wednesday, September 21, 2016 at 4:14:10 PM UTC+2, Daiyue Weng wrote:
> Hi, first of all, let me rephase the problem.
> 
> For an arbitrary list of integers (the integers in the list are not
> necessary to be sequential), e.g. [1,2,3,6,8,9,10,11,13],
> 
> if a set of consecutive integers having a difference of 1 between them, put
> them in a list, i.e. there are two such lists in this example,
> 
> [1,2,3],
> 
> [8,9,10,11],
> 
> and then put such lists in another list (i.e. [[1,2,3], [8,9,10,11]]). Put
> the rest integers (non-sequential) in a separated list, i.e.
> 
> `[6, 13]`.
> 
> Note that, the problem only considers sequential integers with step_size =
> 1.
> 
> I tried to use itertools.groupby and itertools.count,
> 
> from itertools import groupby, count
> lst = [1,2,3,6,8,9,10,11,13]
> c = count()
> result = [list(g) for i, g in groupby(lst, key=lambda x: x-next(c))]
> 
> but the result is close to the requirement shown as a list of lists,
> 
> [[1, 2, 3], [6], [8, 9, 10, 11], [13]]
> 
> but it didn't separate sequential lists from non-sequential ones.
> Also, I couldn't find a way to put [6] and [13] in a single list.
> 
> I have also tried to separate sequential lists from non-sequential ones,
> 
> result = [list(g) for i, g in groupby(lst, key=lambda x: x-next(c) == 1)] #
> tried to extract [1,2,3] and [8,9,10,11] from the list
> 
> or
> 
> result = [list(g) for i, g in groupby(lst, key=lambda x: x-next(c) > 1)] #
> tried to extract [6] and [13] from the list
> 
> but they all ended up with
> 
> [[1, 2, 3], [6, 8, 9, 10, 11, 13]]
> 
> So two questions here,
> 
> 1. How does itertools.groupby key function work in my case?
> 
> 2. How to improve the program to achieve my goals?
> 
> 
> Many thanks
> 
> On 21 September 2016 at 00:19, John Pote <johnpote at jptechnical.co.uk> wrote:
> 
> > On 20/09/2016 12:52, Daiyue Weng wrote:
> >
> > Hi, I have a list numbers say,
> >>
> >> [1,2,3,4,6,8,9,10,11]
> >>
> >> First, I want to calculate the sum of the differences between the numbers
> >> in the list.
> >>
> > At least for this first part a little pencil, paper and algebra yields a
> > simple formula of constant and minimal calculation time. I had an intuitive
> > guess and wrote down the sum of differences for a couple of examples,
> > [1, 2, 5]       => 4
> > [9, 11, 17, 19] => 10
> > It works for negative differences as well,
> > [1, 2, 5, 1]    => 0
> > The trick is to spot the relation between the sum of differences and the
> > numbers in the list. A few lines of algebra then gave a very simple formula.
> >
> > As for the rest it's down to code as others have hinted at.
> >
> > Second, if a sequence of numbers having a difference of 1, put them in a
> >> list, i.e. there are two such lists,
> >>
> >> [1,2,3]
> >>
> >> [8,9,10,11]
> >>
> >> and also put the rest numbers in another list, i.e. there is only one such
> >> list in the example,
> >>
> >> [6].
> >>
> >> Third, get the lists with the max/min sizes from above, i.e. in this
> >> example, the max list is,
> >>
> >> [8,9,10,11]
> >>
> >> min list is
> >>
> >> [1,2,3].
> >>
> >> What's the best way to implement this?
> >>
> >> cheers
> >>
> >
> > --
> > https://mail.python.org/mailman/listinfo/python-list
> >
On Wednesday, September 21, 2016 at 4:14:10 PM UTC+2, Daiyue Weng wrote:
> Hi, first of all, let me rephase the problem.
> 
> For an arbitrary list of integers (the integers in the list are not
> necessary to be sequential), e.g. [1,2,3,6,8,9,10,11,13],
> 
> if a set of consecutive integers having a difference of 1 between them, put
> them in a list, i.e. there are two such lists in this example,
> 
> [1,2,3],
> 
> [8,9,10,11],
> 
> and then put such lists in another list (i.e. [[1,2,3], [8,9,10,11]]). Put
> the rest integers (non-sequential) in a separated list, i.e.
> 
> `[6, 13]`.
> 
> Note that, the problem only considers sequential integers with step_size =
> 1.
> 
> I tried to use itertools.groupby and itertools.count,
> 
> from itertools import groupby, count
> lst = [1,2,3,6,8,9,10,11,13]
> c = count()
> result = [list(g) for i, g in groupby(lst, key=lambda x: x-next(c))]
> 
> but the result is close to the requirement shown as a list of lists,
> 
> [[1, 2, 3], [6], [8, 9, 10, 11], [13]]
> 
> but it didn't separate sequential lists from non-sequential ones.
> Also, I couldn't find a way to put [6] and [13] in a single list.
> 
> I have also tried to separate sequential lists from non-sequential ones,
> 
> result = [list(g) for i, g in groupby(lst, key=lambda x: x-next(c) == 1)] #
> tried to extract [1,2,3] and [8,9,10,11] from the list
> 
> or
> 
> result = [list(g) for i, g in groupby(lst, key=lambda x: x-next(c) > 1)] #
> tried to extract [6] and [13] from the list
> 
> but they all ended up with
> 
> [[1, 2, 3], [6, 8, 9, 10, 11, 13]]
> 
> So two questions here,
> 
> 1. How does itertools.groupby key function work in my case?
> 
> 2. How to improve the program to achieve my goals?
> 
> 
> Many thanks
> 
> On 21 September 2016 at 00:19, John Pote <johnpote at jptechnical.co.uk> wrote:
> 
> > On 20/09/2016 12:52, Daiyue Weng wrote:
> >
> > Hi, I have a list numbers say,
> >>
> >> [1,2,3,4,6,8,9,10,11]
> >>
> >> First, I want to calculate the sum of the differences between the numbers
> >> in the list.
> >>
> > At least for this first part a little pencil, paper and algebra yields a
> > simple formula of constant and minimal calculation time. I had an intuitive
> > guess and wrote down the sum of differences for a couple of examples,
> > [1, 2, 5]       => 4
> > [9, 11, 17, 19] => 10
> > It works for negative differences as well,
> > [1, 2, 5, 1]    => 0
> > The trick is to spot the relation between the sum of differences and the
> > numbers in the list. A few lines of algebra then gave a very simple formula.
> >
> > As for the rest it's down to code as others have hinted at.
> >
> > Second, if a sequence of numbers having a difference of 1, put them in a
> >> list, i.e. there are two such lists,
> >>
> >> [1,2,3]
> >>
> >> [8,9,10,11]
> >>
> >> and also put the rest numbers in another list, i.e. there is only one such
> >> list in the example,
> >>
> >> [6].
> >>
> >> Third, get the lists with the max/min sizes from above, i.e. in this
> >> example, the max list is,
> >>
> >> [8,9,10,11]
> >>
> >> min list is
> >>
> >> [1,2,3].
> >>
> >> What's the best way to implement this?
> >>
> >> cheers
> >>
> >
> > --
> > https://mail.python.org/mailman/listinfo/python-list
> >

And here is a straightforward one without any helpers:


l = [1, 2, 3, 6, 8, 9, 10, 11, 13, 17, 19, 20]
n = len(l)

seq_list = None

non_seq_list = []
all_seq_list = []
diff = []
for i, li in enumerate(l):
    # Handle edge case
    if i == n - 1:
        if l[-1] - l[-2] == 1:
            seq_list.append(l[-1])
            all_seq_list.append(seq_list)
        else:
            non_seq_list.append(l[-1])
        break

    d = l[i+1] - li
    diff.append(d)
    if d == 1:
        if seq_list is None:
            seq_list = []
        seq_list.append(li)
    else:
        if seq_list is not None:
            seq_list.append(li)
            all_seq_list.append(seq_list)
            seq_list = None
        else:
            non_seq_list.append(li)

print('input', l)
print('sum of differences', sum(diff))
print('sequential lists', all_seq_list)
print('non-sequential entries', non_seq_list)

length_seq_list = sorted([(len(s), s) for s in all_seq_list])
print('shortest', length_seq_list[0])
print('longest', length_seq_list[-1])

This gives:

input [1, 2, 3, 6, 8, 9, 10, 11, 13, 17, 19, 20]
sum of differences 19
sequential lists [[1, 2, 3], [8, 9, 10, 11], [19, 20]]
non-sequential entries [6, 13, 17]
shortest (2, [19, 20])
longest (4, [8, 9, 10, 11])