如何在Python中基于直接前驱列表获取矿块完整前驱列表？

Hey there! Let's figure out how to efficiently compute the full set of predecessors (including all indirect dependencies) for your large-scale mining block problem—whether you're dealing with 1,060 or 100,000 blocks, this approach will work smoothly.

First, let's clarify the problem: you need to expand a list of direct predecessors (immediate blocks that must be mined first) into a list of full predecessors (all blocks that need to be mined before a given block, including the predecessors of predecessors). For example, block 9's direct predecessors are 6,7,8—but its full predecessors include all of 6,7,8's predecessors too (1,2,3,4,5) plus 6,7,8 themselves.

For large datasets (100k blocks), a naive recursive approach will be too slow and risk stack overflow. Instead, we'll use topological sorting on the directed acyclic graph (DAG) of block dependencies—since mining order can't have cycles, this is a perfect fit. Topological sorting lets us process blocks in an order where all predecessors of a block are handled before the block itself, making it easy to accumulate full dependencies efficiently.

Here's a Python solution optimized for scale:

1. Core Function to Compute Full Predecessors #

This function takes the number of blocks N and a dictionary mapping each block number to its direct predecessors, then returns the full predecessor list for each block:

from collections import deque

def compute_full_predecessors(N, direct_predecessors):
    # Initialize full predecessors as sets (for fast union/duplicate removal)
    full_pred = {u: set(direct_predecessors[u]) for u in range(1, N+1)}
    
    # Build a successor adjacency list: track which blocks depend on each block
    successors = {u: [] for u in range(1, N+1)}
    # Track in-degree (number of direct predecessors) for topological sorting
    in_degree = {u: len(direct_predecessors[u]) for u in range(1, N+1)}
    
    # Populate the successor list
    for block in range(1, N+1):
        for pred in direct_predecessors[block]:
            successors[pred].append(block)
    
    # Start topological sort with blocks that have no direct predecessors (in-degree 0)
    queue = deque()
    for block in range(1, N+1):
        if in_degree[block] == 0:
            queue.append(block)
    
    # Process each block in topological order
    while queue:
        current_block = queue.popleft()
        # Update all blocks that depend on current_block
        for dependent_block in successors[current_block]:
            # Merge current_block's full predecessors into the dependent's full predecessors
            full_pred[dependent_block].update(full_pred[current_block])
            # Decrement in-degree: we've resolved one predecessor dependency
            in_degree[dependent_block] -= 1
            # If all dependencies are resolved, add to the queue
            if in_degree[dependent_block] == 0:
                queue.append(dependent_block)
    
    # Convert sets to sorted lists (optional, for consistent ordering)
    full_pred_sorted = {u: sorted(list(full_pred[u])) for u in range(1, N+1)}
    return full_pred_sorted

2. Adapt to Your Existing Code Structure #

If your data uses 0-indexed lists (like your example where p[0] corresponds to block 1), we can map it to the block number-based dictionary the function expects:

# Your original input setup
blocks = [1,2,3,4,5,6,7,8,9]
p = [[] for _ in blocks]
p[0] = []    # Block 1 has no direct predecessors
p[1] = []    # Block 2
p[2] = []    # Block 3
p[3] = []    # Block 4
p[4] = []    # Block 5
p[5] = [1,2,3]  # Block 6's direct predecessors
p[6] = [2,3,4]  # Block 7
p[7] = [3,4,5]  # Block 8
p[8] = [6,7,8]  # Block 9

# Convert to block-number keyed dictionary
direct_predecessors = {}
for idx, block_num in enumerate(blocks):
    direct_predecessors[block_num] = p[idx]

# Compute full predecessors
total_blocks = len(blocks)
full_predecessors = compute_full_predecessors(total_blocks, direct_predecessors)

# Convert back to your original list format (0-indexed)
full_p = []
for block_num in blocks:
    full_p.append(full_predecessors[block_num])

# Check the result for block 9 (index 8 in full_p)
print(full_p[8])  # Output: [1, 2, 3, 4, 5, 6, 7, 8]

• Time Complexity: O(N + E), where N is the number of blocks and E is the total number of direct predecessor relationships. This is linear time, making it feasible even for 100,000 blocks.
• Efficiency: Using sets for predecessor storage ensures fast union operations and automatic duplicate removal. Topological sorting avoids redundant calculations by processing each block exactly once.
• Avoids Stack Overflow: Unlike recursive approaches, the iterative queue-based topological sort handles large datasets without hitting recursion depth limits.

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