5 Best Ways to Find the Length of the Longest Fibonacci Subsequence from a Given List in Python

Rate this post

πŸ’‘ Problem Formulation: We often encounter problems in computer science that require us to extract patterns or sequences from data. In this article, we are looking at the specific problem of determining the length of the longest subsequence within a given list that may form a part of the Fibonacci sequence. Given a list such as [1, 4, 3, 9, 10, 13, 7], the desired output for this challenge would be 3, as the longest Fibonacci-like subsequence is [1, 3, 4] or [1, 3, 13].

Method 1: Using a Set for Verification and Two-Pointer Technique

The first method involves creating a set from the given list for constant-time checks and then using a two-pointer technique to iterate through combinations of the list’s elements while checking if they are consecutive Fibonacci numbers. This method effectively leverages the characteristic that any subsequent Fibonacci number can be found by summing up the two preceding ones, and any number not in the set isn’t part of the Fibonacci subsequence.

Here’s an example:

def find_longest_fib_subseq(arr):
    s = set(arr)
    longest_subseq_len = 0
    for i in range(len(arr)):
        for j in range(i+1, len(arr)):
            x, y = arr[i], arr[j]
            length = 2
            while x + y in s:
                x, y = y, x + y
                length += 1
            longest_subseq_len = max(length, longest_subseq_len)
    return longest_subseq_len if longest_subseq_len >= 3 else 0

# Example Usage:
print(find_longest_fib_subseq([1, 4, 3, 9, 10, 13, 7]))

Output: 3

This code snippet defines a function find_longest_fib_subseq() which takes a list of integers as its argument. It creates a set of the list elements for quick look-up and iterates through pairs of numbers using a nested loop structure. The innermost block uses the Fibonacci property to check and extend potential subsequences until no further continuation is possible, updating the longest sequence length as it goes. It then returns the length of the longest Fibonacci subsequence found or 0 if none is long enough.

Method 2: Dynamic Programming

Dynamic programming can be used to solve this problem by building a solution iteratively using the previously calculated subproblems. Specifically, a two-dimensional table can capture lengths of Fibonacci subsequences with different starting points. This approach reduces redundant calculations you would encounter in a naive recursive solution, improving efficiency.

Here’s an example:

def longest_fib_subseq_DP(arr):
    index_map = {x: i for i, x in enumerate(arr)}
    longest = [[2] * len(arr) for _ in arr]
    max_len = 0

    for k, z in enumerate(arr):
        for j in range(k):
            i = index_map.get(z - arr[j])
            if i is not None and i  2 else 0

# Example Usage:
print(longest_fib_subseq_DP([1, 4, 3, 9, 10, 13, 7]))

Output: 3

In the provided longest_fib_subseq_DP() function, we store indices of the list elements in a map for O(1) access. We then build a 2D array to record lengths of Fibonacci subsequences with different starting elements. We iterate over all possible pairs and update the subsequence length only when a valid prior number exists in the map. The function returns the length of the longest subsequence (greater than 2) or 0 if there isn’t one.

Method 3: Optimized Brute Force with Early Stopping

An optimized brute-force method involves iterating through all possible subsequences while using clever stopping conditions to skip unnecessary calculations. This method attempts to find the Fibonacci subsequences one element at a time and stops early if the sequence cannot be continued, offering improved performance over a strictly naive brute-force approach.

Here’s an example:

def optimized_brute_force(arr):
    s = set(arr)
    longest = 0
    for i in range(len(arr)):
        for j in range(i+1, len(arr)):
            a, b = arr[i], arr[j]
            length = 2
            while a+b in s:
                a, b = b, a+b
                length += 1
                longest = max(longest, length)
            if length + len(arr) - j - 1 <= longest:
                break # Early stopping condition
    return longest

# Example Usage:
print(optimized_brute_force([1, 4, 3, 9, 10, 13, 7]))

Output: 3

This function, optimized_brute_force(), also initializes a set for the input list and iterates through pairs of numbers to find Fibonacci subsequences. Key to its optimization is the early stopping condition, which breaks out of the inner loop when it’s impossible to find a longer subsequence than the longest found so far. This helps avoid redundant computations and significantly speeds up the search, particularly for larger lists.

Method 4: Hash Map and Greedy Approach

Combining a hash map with a greedy approach, this method involves maintaining a map of the last two elements of all found subsequences to their lengths. With each new number visited, we update these values greedilyβ€”only keeping the longest subsequence for each pair of last elementsβ€”resulting in a lesser number of operations compared to the previous methods.

Here’s an example:

def longest_fib_subseq_hash_greedy(arr):
    seq_map = {}
    s = set(arr)
    max_length = 0
    for i in range(len(arr)):
        for j in range(i+1, len(arr)):
            a, b = arr[i], arr[j]
            length = 2
            while a + b in s:
                a, b = b, a + b
                length += 1
                seq_map[(b - a, a)] = length
                max_length = max(max_length, length)
    return max_length if max_length > 2 else 0

# Example Usage:
print(longest_fib_subseq_hash_greedy([1, 4, 3, 9, 10, 13, 7]))

Output: 3

With longest_fib_subseq_hash_greedy(), a hash map (`seq_map`) and a set (`s`) are used to identify and track the longest subsequences. As elements are paired and used to extend subsequences, the map is updated with the length of the subsequence indexed by the last two elements used to produce its next number. The method then returns the maximum length found that is longer than a pair of elements.

Bonus One-Liner Method 5: Using itertools and a Generator Function

This one-liner takes a functional approach, leveraging Python’s itertools library to generate all pairs of numbers, and a generator function to extend them into Fibonacci subsequences. Although compact, this method trades readability for conciseness and may not be as efficient as other methods due to the extensive use of generator expressions.

Here’s an example:

from itertools import combinations

def length_of_longest_fib_subseq(arr):
    s = set(arr)
    gen_fib = lambda x, y: x + y if x + y in s else 0
    return max((len(list(takewhile(lambda x: x, (gen_fib(b, a+b), (a, b := b, a+b))[0] for _ in s))) for a, b in combinations(arr, 2)), default=2)

# Example Usage:
print(length_of_longest_fib_subseq([1, 4, 3, 9, 10, 13, 7]))

Output: 3

In this concise implementation, the length_of_longest_fib_subseq() function creates a set from the input list for look-up. The generator function `gen_fib` calculates the Fibonacci sequence only when possible, and `itertools.combinations` is used to provide pairs of numbers to start the sequences. The takewhile function from the itertools module then extends each sequence until the condition is met, and the length of the longest subsequence is returned.

Summary/Discussion

  • Method 1: Using a Set for Verification and Two-Pointer Technique. Strengths: Relatively straightforward and efficient for small to medium-sized lists. Weaknesses: Time complexity increases significantly with the size of the input list.
  • Method 2: Dynamic Programming. Strengths: More efficient for larger lists due to reduced redundant calculations. Weaknesses: Uses extra space for the 2D table, and the implementation is more complex.
  • Method 3: Optimized Brute Force with Early Stopping. Strengths: Improves on the brute-force method by reducing unnecessary calculations. Weaknesses: Still less efficient than dynamic programming for larger input sizes.
  • Method 4: Hash Map and Greedy Approach. Strengths: Reduces the number of operations with the help of hash maps. Weaknesses: Can still be outperformed by the dynamic programming approach in terms of efficiency.
  • Bonus Method 5: Functional One-Liner with itertools. Strengths: Very concise code. Weaknesses: Not as readable, potentially less efficient due to extensive use of generators, and might not handle large lists as well as other methods.