集合列表的交集拓展与缩减问题及代码优化诉求

Alright, let's fix this problem properly. Here's a step-by-step solution to generate all valid intersection combinations as required, addressing both your existing issues:

First, let's restate the problem clearly to make sure we're aligned:

Given my_list_of_sets, each set at index x can only intersect with other sets whose indexes are elements of my_list_of_sets[x]. We need to recursively generate all valid intersection results, while fixing two key issues:

1. Inconsistent results due to traversal order (violating the unordered property of sets)
2. Missing valid combinations like {1,2,4} or {3,4} from rolling window logic

Core Approach: Filter Valid Index Subsets First #

Instead of relying on rolling windows (which easily miss valid combinations), we'll generate all possible non-empty index subsets, filter out the ones that meet the rules, then compute their intersections and deduplicate results. This ensures we don't miss any valid combination, and results are consistent regardless of traversal order.

Step-by-Step Implementation #

1. Define the Original List #

First, let's write down the input list clearly for reference:

my_list_of_sets = [
    {0,1,2,3,4,5,7,9},
    {0,1,2,4,5,6,7},
    {0,1,2,3,4,8,9},
    {1,3,4,5,6,7,8,9},
    {1,2,3,4,5,6},
    {3,4,5,6,7,8,9},
    {1,2,3,5,6,8,9},
    {2,3,4,5,6,7,8},
    {2,5,6,7,8,9},
    {3,4,6,7,8,9}
]

2. Generate & Filter Valid Index Subsets #

We'll use itertools.combinations to create all possible non-empty index groups, then keep only those groups where every index in the group is present in every set corresponding to the group's indexes. This ensures the "only intersect with sets whose indexes are in your own set" rule is fully satisfied.

from itertools import combinations

# Generate all non-empty index subsets (from size 1 to 10)
all_index_subsets = []
for subset_size in range(1, len(my_list_of_sets) + 1):
    all_index_subsets.extend(combinations(range(len(my_list_of_sets)), subset_size))

# Filter valid subsets: For every index i in the subset, all other indexes j in the subset are in my_list_of_sets[i]
valid_subsets = []
for subset in all_index_subsets:
    is_valid = True
    for idx in subset:
        # Check all other indexes in the subset are present in the current set
        for other_idx in subset:
            if idx == other_idx:
                continue
            if other_idx not in my_list_of_sets[idx]:
                is_valid = False
                break
        if not is_valid:
            break
    if is_valid:
        valid_subsets.append(subset)

3. Compute Intersections & Deduplicate #

Now calculate the intersection for each valid subset, then deduplicate results (since different subsets can produce the same intersection). We use frozenset because regular sets can't be stored in another set for deduplication.

# Calculate intersections and deduplicate
unique_intersections = set()
for subset in valid_subsets:
    # Start with the first set in the subset, then iteratively intersect with others
    current_intersection = my_list_of_sets[subset[0]].copy()
    for idx in subset[1:]:
        current_intersection.intersection_update(my_list_of_sets[idx])
    # Add as frozenset to allow storing in a set for deduplication
    unique_intersections.add(frozenset(current_intersection))

# Convert back to regular sets for readability
final_results = [set(s) for s in unique_intersections]

# Optional: Sort results by size for easier inspection
final_results.sort(key=lambda x: len(x))

# Print the results
for res in final_results:
    print(res)

Why This Fixes Your Issues #

1. Consistent Results: By generating all valid subsets and deduplicating intersections, the order of traversal doesn't affect the final output. Results are pure sets, adhering to their unordered nature.
2. No Missing Combinations: Unlike rolling window logic, this approach covers every possible valid index combination (size 1 to 10), including small groups like (1,2,4) or (3,4) that were previously missed.

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