从嵌套字典（树结构）的值生成列表的列表

Got it, let's tackle how to generate that value-based nested list from your hierarchical clustering dictionary. Here's a practical, step-by-step solution with code and breakdown:

Understand the Clustering Hierarchy #

First, let's map out your cluster tree dic = {6: {2: 2, 5: {3: 3, 4: {0: 0, 1: 1}}}} to clarify the merge order:

• The final merge combines 2 and 5 (where 5 is itself a merge of 3 and 4, and 4 is a merge of 0 and 1)
• Merge sequence: 0+1→4 → 3+4→5 → 2+5→6
• We need to reverse this sequence to get groups from fully merged down to fully split, which is exactly your target "value-based list of lists".

Code Implementation #

Here's a Python script that recursively processes the cluster dict to generate the exact structure you need:

def get_leaves(node):
    """Extract all original data points (leaf nodes) from the cluster tree"""
    if isinstance(node, int):
        return [node]
    leaves = []
    for child in node.values():
        leaves.extend(get_leaves(child))
    return leaves

def generate_value_based_clusters(cluster_dict):
    # Get all leaf nodes (the smallest individual groups)
    all_leaves = get_leaves(cluster_dict)
    result = []
    # Start with the fully merged group
    result.append([all_leaves])
    
    def traverse_cluster(node, current_groups):
        if isinstance(node, int):
            return
        # Split the current groups based on the current cluster's children
        new_groups = []
        for child in node.values():
            child_leaves = get_leaves(child)
            # Replace the parent group with the child's leaf groups
            temp = []
            for group in current_groups:
                if set(child_leaves).issubset(set(group)):
                    if isinstance(child, int):
                        temp.append([child])
                    else:
                        temp.append(child_leaves)
                else:
                    temp.append(group)
            new_groups = temp
        # Add the new split state to our result
        result.append(new_groups)
        # Recurse into each child to keep splitting
        for child in node.values():
            traverse_cluster(child, new_groups)
    
    # Start traversing from the root cluster's child structure
    root_cluster = next(iter(cluster_dict.values()))
    traverse_cluster(root_cluster, [all_leaves])
    
    # Sort the result by number of groups (from merged to split)
    result = sorted(result, key=lambda x: len(x))
    return result

# Test with your cluster dictionary
dic = {6: {2: 2, 5: {3: 3, 4: {0: 0, 1: 1}}}}
output = generate_value_based_clusters(dic)
print(output)
# Output: [[[2, 3, 0, 1]], [[2], [3, 0, 1]], [[2], [3], [0, 1]], [[2], [3], [0], [1]]]

How It Works #

1. get_leaves: Recursively digs through the nested dictionary to pull out all original data points (0, 1, 2, 3) — these are our smallest, individual clusters.
2. Initial State: We start with all leaves merged into a single group, which is the first entry in our result list.
3. Recursive Traversal: We walk through each cluster node, splitting the current groups into the child clusters' leaf sets. Each split state gets added to the result.
4. Sorting: Finally, we sort the result by the number of groups to ensure we go from fully merged (1 group) to fully split (4 individual groups), matching the structure you need.

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