Python中快速查找多维度子列表集合中和大于等于指定值的所有最小子集的最优方法

First, let's clarify the exact requirement: Given a list of sublists (each can have different lengths), we need to find all sublists whose sum is greater than or equal to a target value, and which have the smallest possible length among all qualifying sublists.

Core Approach #

The key steps to solve this efficiently are:

1. Filter out all sublists whose sum meets or exceeds the target value.
2. Determine the smallest length among these qualifying sublists.
3. Extract all sublists that have this minimal length and still meet the sum requirement.

Implementation 1: Straightforward & Reliable #

This is the most direct approach, with optimal theoretical time complexity (O(N*M), where N is the number of sublists and M is the average length of sublists). We only calculate the sum of each sublist once to avoid redundant work.

def find_min_length_sublists(A, target_value):
    # Collect qualifying sublists along with their length and sum
    candidates = []
    for sublist in A:
        sub_sum = sum(sublist)
        if sub_sum >= target_value:
            candidates.append((len(sublist), sub_sum, sublist))
    
    # Handle edge case: no qualifying sublists
    if not candidates:
        return []
    
    # Find the minimal length among all candidates
    min_length = min(item[0] for item in candidates)
    
    # Extract all sublists with this minimal length
    return [item[2] for item in candidates if item[0] == min_length]

Test with your examples

• Example 1:

  A = [[1],[1,2,3,4],[5,6],[10],[1000,12],[11]]
  value = 10
  print(find_min_length_sublists(A, value))  # Output: [[10], [11]]
  

  This matches your expected result perfectly.

• Example 2:

  A = [[1,10],[1,2,3,4],[5,6],[10,10],[1000,12,1],[1,10,11]]
  value = 10
  print(find_min_length_sublists(A, value))  # Output: [[1,10], [5,6], [10,10]]
  

  Note: Your original expected result omitted [5,6], but this sublist has length 2 (the minimal qualifying length) and sum 11 ≥ 10, so it should be included. This suggests a possible typo in your example.

Implementation 2: Optimized for Early Termination #

If your dataset has many long sublists that don't meet the sum requirement, this version can save time by sorting sublists by length first. We stop searching for the minimal length as soon as we find the first qualifying sublist, avoiding unnecessary sum calculations for longer sublists.

def find_min_length_sublists_optimized(A, target_value):
    # Sort sublists by their length (ascending)
    sorted_sublists = sorted(A, key=lambda x: len(x))
    
    # Find the smallest length where at least one sublist meets the sum requirement
    min_length = None
    for sublist in sorted_sublists:
        if sum(sublist) >= target_value:
            min_length = len(sublist)
            break
    
    # Handle edge case: no qualifying sublists
    if min_length is None:
        return []
    
    # Collect all sublists with this minimal length that meet the sum requirement
    return [sublist for sublist in A if len(sublist) == min_length and sum(sublist) >= target_value]

Performance Notes #

• Both implementations have an overall time complexity of O(N*M) in the worst case (when all sublists qualify).
• The optimized version performs better when there are short qualifying sublists, as it avoids calculating sums for longer sublists once the minimal length is found.
• For extremely large datasets, consider using generators instead of lists to reduce memory usage, but this will only help if you don't need to reuse the candidate list multiple times.

内容的提问来源于stack exchange，提问作者jahnLudvik