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).
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.
- The outer loop counts down from the length of the sequence to zero.
- The inner loop generates combinations of the current length in the outer loop
- If the
sub_sequenceis 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.
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
- From Python Algorithms