CODEWITHSUNDEEP
pythonpython-3.xalgorithmsequence
Hertzeh
Hertzeh

Reputation: 65

Smallest number of increasing sequences that contain all elements of a list

Suppose you have the following list

a_list = [1, 2, 3, 4, 8, 7, 6]

We want to find the smallest ‘number’ of increasing sequences that contain all elements of the list from either side of the list.

For the example above, we would get

sequence = [[1,2,3,4,8], [6,7]]

Which gives an answer of 2. This is because we can form an increasing sequence from left to right as [1,2,3,4,8]. We can also form an increasing sequence from right to left as [6,7].

I have considered creating two lists which give all the increasing sequences of the list and the reverse of the list, as such

left_to_right = [[1,2,3,4,8],[7], [6]]
right_to_left = [[6,7,8], [4], [3], [2], [1]]

but I am not sure where to go from there. Any thoughts?

Upvotes: 1

Views: 120

Answers (1)

Neil
Neil

Reputation: 3291

EDIT: The original below is unnecessarily complex. Increasing "from the left" just means decreasing. So just iterate over the list once, keeping track of increasing and decreasing sequences with a boolean flag, making them as long as possible, and then count at the end. This should work. Not tested.

increasing = None
current_item = _list[0]
all_sequences = []
current_sequence = [_list[0]]

for item in _list[1:]:
    if increasing is None:
        increasing = item > current_sequence[-1]
        current_sequence.append(item)

    elif (item > current_item and increasing) or (item < current_item and not increasing):
        current_sequence.append(item)

    elif (item > current_item and not increasing) or (item < current_item and increasing):
        all_sequences.append(current_sequence)
        current_sequence = [item]
        increasing = None
    
    current_item = item
all_sequences.append(current_sequence)
result = len(all_sequences)

Original Answer: Here's some thoughts

First, I assume that your function will always make the sequences as long as possible. So you get this:

left_to_right = [[1,2,3,4,8],[7], [6]]

And not, for example, this:

left_to_right = [[1,2],[3],[4,8],[7], [6]]

(which is technically also a list of increasing sequences).

Your next job it to make sure you get all the numbers in the list. So you must pick some increasing sequences. The longer the sequence you pick, the more numbers you get to "use up" while not adding too many more sequences. To take your example:

left_to_right = [[1,2,3,4,8],[7], [6]]
right_to_left = [[6,7,8], [4], [3], [2], [1]]

Join the two lists together:

all = left_to_right + right_to_left

Now find the longest sequence:

longest = max(all, key=lambda x:len(x))

That will give you

[1,2,3,4,8]

Now repeat, grabbing the next longest sequence, keep going until you have captured all the numbers in the list. That would give you:

[[1,2,3,4,8], [6,7,8]]

As a final step, check for duplicates. Then you will get

[[1,2,3,4,8], [6,7]]

as desired

I suspect this should always give you the fewest sequences. But maybe if there are duplicates I might be wrong.

Upvotes: 2

Related Questions