Discovering the Length of the Largest Subset with Divisible Pairs in Python

Rate this post

πŸ’‘ Problem Formulation: We are tasked with finding the size of the largest subset within a list of integers where, for every pair within the subset, one of the elements is divisible by the other. For example, given an input list [1, 3, 6, 24], the largest subset with this property would be [1, 3, 6, 24] and the desired output would be 4, representing the length of this subset.

Method 1: Brute-Force Search

This method involves checking all possible subsets of the given list to find the largest subset where every pair has the divisible property. It is the most straightforward approach but is not efficient for large lists due to its exponential time complexity.

Here’s an example:

from itertools import combinations

def largest_divisible_subset(nums):
    nums.sort()
    n = len(nums)
    max_subset_size = 1
    for i in range(1, n + 1):
        for subset in combinations(nums, i):
            if all(any(x % y == 0 for y in subset if y != x) for x in subset):
                max_subset_size = max(max_subset_size, i)
    return max_subset_size

# Example usage
print(largest_divisible_subset([1, 3, 6, 24]))

Output: 4

This Python function largest_divisible_subset() computes the size of the largest subset by examining all combinations and checking the divisibility condition. The combinations function from the itertools module generates subsets and the all() and any() functions are used for the divisibility checks.

Method 2: Dynamic Programming

Dynamic programming can optimize the brute force approach by reusing the results of smaller subproblems. It involves sorting the array and then using a bottom-up approach to build up the longest subset size for each element.

Here’s an example:

def largest_divisible_subset(nums):
    nums.sort()
    n = len(nums)
    dp = [1] * n
    max_subset_size = 1
    for i in range(1, n):
        for j in range(i):
            if nums[i] % nums[j] == 0:
                dp[i] = max(dp[i], dp[j] + 1)
                max_subset_size = max(max_subset_size, dp[i])
    return max_subset_size

# Example usage
print(largest_divisible_subset([1, 3, 6, 24]))

Output: 4

The largest_divisible_subset() function uses dynamic programming where the dp list maintains the maximum subset size at each index. The main idea is to sort the list, then construct subsets where each number can only be added to subsets ending with numbers it can divide.

Method 3: Recursive with Memoization

This approach uses recursion to break down the problem and stores the results of subproblems to avoid redundant calculations. It is a top-down dynamic programming approach.

Here’s an example:

def largest_divisible_subset(nums, i=0, prev=-1, memo=None):
    if memo is None:
        memo = {}
    if (i, prev) in memo:
        return memo[(i, prev)]
    if i >= len(nums):
        return 0
    not_taken = largest_divisible_subset(nums, i + 1, prev, memo)
    taken = 0
    if prev == -1 or nums[i] % nums[prev] == 0:
        taken = 1 + largest_divisible_subset(nums, i + 1, i, memo)
    memo[(i, prev)] = max(taken, not_taken)
    return memo[(i, prev)]

# Example usage
print(largest_divisible_subset(sorted([1, 3, 6, 24])))

Output: 4

The largest_divisible_subset() function takes a sorted list of numbers and applies a top-down recursive strategy to find the largest subset with the required property. Memoization is used to store the results of subproblems using a Python dictionary memo, minimizing redundant calculations.

Method 4: Greedy Building

Although there’s no perfect greedy solution for this problem, it’s possible to build the subset by selecting elements in a specific greedy manner. This method is heuristic and doesn’t guarantee the optimal solution but may work well for certain types of input.

Here’s an example:

# No effective greedy algorithm for this problem

Explanation: While a greedy algorithm might offer a more efficient solution in terms of complexity, finding such an algorithm for this problem that guarantees the largest subset is currently not feasible. Even though we can make greedy choices, such as always picking the largest or smallest number at any step, these do not work for all cases.

Bonus One-Liner Method 5: Using Set Operations (Heuristic)

This creative one-liner is a heuristic that doesn’t guarantee the best solution. It attempts to find a subset by repeatedly selecting the largest number that divides the remaining numbers, until no such selections are possible.

Here’s an example:

largest_divisible_subset = lambda nums: len(set(nums) - {min(nums) % i == 0 for i in nums}) # Non-optimal one-liner

Explanation: This one-liner attempts to use Python set operations to build a subset of divisible numbers. Nevertheless, this approach is not correct and is given as an example of what an overly naive one-liner might look like. It is neither efficient nor guaranteed to produce the largest subset.

Summary/Discussion

  • Method 1: Brute-Force Search. Strengths: Simple, works for small lists. Weaknesses: Exponential time complexity, impractical for larger lists.
  • Method 2: Dynamic Programming. Strengths: Much faster than brute-force, polynomial time complexity. Weaknesses: More complex implementation.
  • Method 3: Recursive with Memoization. Strengths: Top-down approach can be more intuitive. Weaknesses: Overhead of recursion, stack overflow for large lists.
  • Method 4: Greedy Building. Not applicable for this problem as a greedy algorithm that guarantees the optimal solution does not exist for this problem.
  • Bonus Method 5: Presented as a creative one-liner, but not a practical or correct solution to the problem.