Decompose a list of integers into lists of increasing sequences

Question

Assume no consecutive integers are in the list.

I've tried using NumPy (np.diff) for the difference between each element, but haven't been able to use that to achieve the answer. Two examples of the input (first line) and expected output (second line) are below.

[6, 0, 4, 8, 7, 6]
[[6], [0, 4, 8], [7], [6]]


[1, 4, 1, 2, 4, 3, 5, 4, 0]
[[1, 4], [1, 2, 4], [3, 5], [4], [0]]

Is this what you want? https://stackoverflow.com/questions/952914/how-to-make-a-flat-list-out-of-list-of-lists — niknoe, Apr 30 '19 at 15:26
@NiklasNoem I think that's the opposite of what OP is looking for — C.Nivs, Apr 30 '19 at 15:28

benvc · Accepted Answer · 2019-05-01T14:14:03.603

5

You could use itertools.zip_longest to enable iteration over sequential element pairs in your list along with enumerate to keep track of index values where the sequences are not increasing in order to append corresponding slices to your output list.

from itertools import zip_longest

nums = [1, 4, 1, 2, 4, 3, 5, 4, 0]

results = []
start = 0
for i, (a, b) in enumerate(zip_longest(nums, nums[1:])):
    if b is None or b <= a:
        results.append(nums[start:i+1])
        start = i + 1

print(results)
# [[1, 4], [1, 2, 4], [3, 5], [4], [0]]

edited May 01 '19 at 14:14

answered Apr 30 '19 at 17:24

benvc

14,448
4
33
54

this is the most pythonic way and better than my approach! – Ji Wei May 01 '19 at 03:54
This doesn't work in the case there's a 0 in the input list. `not b` should be `b is None` – alexbclay May 01 '19 at 13:56
1

@alexbclay - thanks for pointing that out. Answer edited accordingly (now properly handles inclusion of negative numbers if needed). – benvc May 01 '19 at 14:15

score 4 · Answer 2 · edited Nov 21 '19 at 15:17

4

Here's a simple way to do what you're asking without any extra libraries:

result_list = []
sublist = []
previous_number = None

for current_number in inp:
    if previous_number is None or current_number > previous_number:
        # still ascending, add to the current sublist
        sublist.append(current_number)
    else:
        # no longer ascending, add the current sublist 
        result_list.append(sublist)

        # start a new sublist
        sublist = [current_number]
    previous_number = current_number
if sublist:
    # add the last sublist, if there's anything there
    result_list.append(sublist)

edited Nov 21 '19 at 15:17

alexisdevarennes

5,437
4
24
38

answered Apr 30 '19 at 15:40

alexbclay

1,389
14
19

This will throw a `TypeError` immediately because you cannot compare `None` with an `int` – Nordle Apr 30 '19 at 15:42
It doesn't throw a TypeError for me when I run this in either python 2 or 3 – alexbclay Apr 30 '19 at 15:43
My bad, I had a bad test case. This runs in python2. I will update – alexbclay Apr 30 '19 at 15:44
1

If you edit so it works, for sure I'll remove the down :) – Nordle Apr 30 '19 at 15:45
Updated. My answer saves one pass through the array, instead of using `min()` to get the min value. – alexbclay Apr 30 '19 at 15:46
1

from a down to an up! Nice and clean – Nordle Apr 30 '19 at 15:47
Thanks! All these solutions are basically identical. – alexbclay Apr 30 '19 at 15:48
Careful, wont work with negative numbers. inp = [-6, 0, 4, -8, 7, 6] result: [[-6, 0, 4, -8, 7, 6]] – alexisdevarennes Apr 30 '19 at 15:53
How do you figure that? – alexbclay Apr 30 '19 at 15:55
I copied your function and ran it :) – alexisdevarennes Apr 30 '19 at 15:56
Weird. I get `[[-6, 0, 4], [-8, 7], [6]]` when I run it locally. – alexbclay Apr 30 '19 at 15:56

alexisdevarennes · Answer 3 · 2019-04-30T15:48:48.217

Just cause I feel kind, this will also work with negative numbers.

seq = [6, 0, 4, 8, 7, 6]
seq_by_incr_groups = []  # Will hold the result
incr_seq = []  # Needed to create groups of increasing values.
previous_value = 0  # Needed to assert whether or not it's an increasing value. 
for curr_value in seq: # Iterate over the list
    if curr_value > previous_value: # It's an increasing value and belongs to the group of increasing values.
        incr_seq.append(curr_value)
    else:  # It was lower, lets append the previous group of increasing values to the result and reset the group so that we can create a new one.
        if incr_seq:  # It could be that it's empty, in the case that the first number in the input list is a negative.
            seq_by_incr_groups.append(incr_seq)
        incr_seq = []
        incr_seq.append(curr_value)
    previous_value = curr_value # Needed so that we in the next iteration can assert that the value is increasing compared to the prior one.

if incr_seq:  # Check if we have to add any more increasing number groups.
    seq_by_incr_groups.append(incr_seq)  # Add them.

print(seq_by_incr_groups)

Sorry, I was wondering myself if I should write any answer as I was sure one would come anytime. — alexisdevarennes, Apr 30 '19 at 15:43

score 1 · Answer 4 · edited Nov 21 '19 at 15:18

Below code should help you. However I would recommend that you use proper nomenclature and consider handling corner cases:

li1 = [6, 0, 4, 8, 7, 6]
li2 = [1, 4, 1, 2, 4, 3, 5, 4, 0]

def inc_seq(li1):
  lix = []
  li_t = [] 
  for i in range(len(li1)):
    #print (i)
    if i < (len(li1) - 1) and li1[i] >= li1[i + 1]:
      li_t.append(li1[i])
      lix.append(li_t)
      li_t = []
    else:
      li_t.append(li1[i])


  print (lix)

inc_seq(li1)
inc_seq(li2)

abhiarora · Answer 5 · 2019-04-30T16:13:46.040

You can write a simple script and you don't need numpy as far as I have understood your problem statement. Try the script below. I have tested it using Python 3.6.7 and Python 2.7.15+ on my Ubuntu machine.

def breakIntoList(inp):
    if not inp:
        return []

    sublist = [inp[0]]
    output = []
    for a in inp[1:]:
        if a > sublist[-1]:
            sublist.append(a)
        else:
            output.append(sublist);
            sublist = [a]


    output.append(sublist)
    return output



list = [1, 4, 1, 2, 4, 3, 5, 4, 0]
print(list)
print(breakIntoList(list))

Explanation:

The script first checks if input List passed to it has one or more elements.
It then initialise a sublist (variable name) to hold elements in increasing order. After that, we append input List's first element into our sublist.
We iterate through the input List beginning from it's second element (Index: 1). We keep on checking if the current element in Input List is greater than last element of sublist (by sublist[-1]). If yes, we append the current element to our sublist (at the end). If not, it means we can't hold that current element in sub-List. We append the sublist to output List and clear the sublist (for holding other increasing order sublists) and add the current element to our sublist.
At the end, we append the remaining sublist to the output List.

Ji Wei · Answer 6 · 2019-04-30T16:56:26.043

Here's an alternative using dict, list comprehensions, and zip:

seq = [1, 4, 1, 2, 4, 3, 5, 4, 0]
dict_seq = {i:j for i,j in enumerate(seq)}

# Get the index where numbers start to decrease
idx = [0] # Adding a zero seems counter-intuitive now; we'll see the benefit later.
for k, v in dict_seq.items():
    if k>0:
        if dict_seq[k]<dict_seq[k-1]:
            idx.append(k)

# Using zip, slice and handling the last entry
inc_seq = [seq[i:j] for i, j in zip(idx, idx[1:])] + [seq[idx[-1:]]]

Output

print(inc_seq)
>>> [[1, 4], [1, 2, 4], [3, 5], [4], [0]]

By initiating idx = [0] and creating 2 sublists idx, idx[1:], we can zip these sublists to form [0:2], [2:5], [5:7] and [7:8] with the list comprehension.

>>> print(idx)
>>> [0, 2, 5, 7, 8]

>>> for i, j in zip(idx, idx[1:]):
       print('[{}:{}]'.format(i,j))

[0:2]
[2:5]
[5:7]
[7:8]   # <-- need to add the last slide [8:]

Decompose a list of integers into lists of increasing sequences

6 Answers6

Linked

Related