Brute Force Longest Non-Decreasing Sub-Sequence

Source

The Problem

The problem at hand is that we're given a sequence and we want to find the longest combination we can find in it that is non-decreasing (each element after the first is greater than or equal to the previous element).

Brute Force

This will be a brute-force solution using nested for-loops. This will use the itertools.combinations function to generate the candidate solutions.

from itertools import combinations

def brute_force(sequence: iter) -> tuple:
    """Finds the longest non-decreasing sub-sequence

    Args:
     sequence: the source collection of items

    Returns:
      the longest non-decreasing sub-sequence in the sequence, number of for-loops
    """
    count = 0
    for length in range(len(sequence), 0, -1):
        count += 1
        for sub_sequence in combinations(sequence, length):
            count += 1
            if list(sub_sequence) == sorted(sub_sequence):
                return sub_sequence, count
    return

Here's what it's doing.

  1. The outer loop counts down from the length of the sequence to zero.
  2. The inner loop generates combinations of the current length in the outer loop
  3. If the sub_sequence is in sorted (non-decreasing) order then it is as long or longer than any other non-decreasing sub-sequence so choose it as the longest sub-sequence.

Example One

source = (3, 1, 0, 2, 4)
expected = (1, 2, 4)

actual, count = brute_force(source)
print(actual)
print(count)
assert actual == expected

(1, 2, 4)
18