Estimating Tree Size

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95

"""
Calculating node counts for uniform branching trees.
 
A uniform tree has the same branching factor at every internal node.
This makes node counting a straightforward geometric series calculation.
"""
 
def count_nodes_uniform_tree(branching_factor: int, depth: int) -> dict:
    """
    Calculate exact node counts for a uniform tree.
    
    Parameters:
    - branching_factor (b): Number of children per internal node
    - depth (d): Number of levels (root is level 0, leaves at level d)
    
    Returns: Dictionary with detailed node counts
    """
    b, d = branching_factor, depth
    
    # Nodes at each level
    nodes_per_level = [b**level for level in range(d + 1)]
    
    # Leaves are at the deepest level
    leaf_count = b**d
    
    # Internal nodes are at levels 0 through d-1
    internal_count = sum(nodes_per_level[:-1])
    
    # Total nodes using geometric series formula
    if b == 1:
        total = d + 1
    else:
        total = (b**(d + 1) - 1) // (b - 1)
    
    return {
        'branching_factor': b,
        'depth': d,
        'nodes_per_level': nodes_per_level,
        'leaf_count': leaf_count,
        'internal_count': internal_count,
        'total_nodes': total,
        'leaf_to_internal_ratio': leaf_count / max(1, internal_count)
    }
 
 
def print_uniform_tree_analysis():
    """
    Display analysis for common uniform tree configurations.
    """
    print("=" * 70)
    print("UNIFORM TREE NODE COUNTS")
    print("=" * 70)
    
    # Binary tree (subset generation)
    print("
BINARY TREE (b=2) - Subset Generation Pattern")
    print("-" * 50)
    for depth in [5, 10, 15, 20]:
        result = count_nodes_uniform_tree(2, depth)
        print(f"  Depth {depth:2d}: {result['leaf_count']:,} leaves, "
              f"{result['total_nodes']:,} total")
    
    # Ternary tree
    print("
TERNARY TREE (b=3)")
    print("-" * 50)
    for depth in [5, 10, 15]:
        result = count_nodes_uniform_tree(3, depth)
        print(f"  Depth {depth:2d}: {result['leaf_count']:,} leaves, "
              f"{result['total_nodes']:,} total")
    
    # Decisions with 4 choices (e.g., grid movement: up/down/left/right)
    print("
QUATERNARY TREE (b=4) - Grid Navigation Pattern")
    print("-" * 50)
    for depth in [5, 10, 12]:
        result = count_nodes_uniform_tree(4, depth)
        print(f"  Depth {depth:2d}: {result['leaf_count']:,} leaves, "
              f"{result['total_nodes']:,} total")
    
    # Key insight: leaf dominance
    print("
LEAF DOMINANCE DEMONSTRATION (b=2, d=10)")
    print("-" * 50)
    result = count_nodes_uniform_tree(2, 10)
    for level, count in enumerate(result['nodes_per_level']):
        percentage = 100 * count / result['total_nodes']
        bar = '#' * int(percentage / 2)
        print(f"  Level {level:2d}: {count:>6,} nodes ({percentage:5.2f}%) {bar}")
    print(f"
  Leaves represent {result['leaf_count']/result['total_nodes']*100:.2f}% of total nodes")
 
 
# Run the analysis
print_uniform_tree_analysis()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153

"""
Calculating node counts for non-uniform branching trees.
 
The classic case is permutation generation, where branching factor
decreases at each level: n, n-1, n-2, ..., 1.
"""
 
import math
 
def count_nodes_permutation_tree(n: int) -> dict:
    """
    Calculate exact node counts for a permutation tree of n elements.
    
    The tree has:
    - Root with n children
    - Level 1 nodes each have n-1 children
    - Level k nodes each have n-k children
    - Level n-1 nodes each have 1 child (leaves at level n)
    
    Parameters:
    - n: Number of elements to permute
    
    Returns: Dictionary with detailed node counts
    """
    # Nodes at each level
    nodes_per_level = []
    cumulative = 1  # Start with root
    
    for level in range(n + 1):
        if level == 0:
            nodes_per_level.append(1)
        else:
            cumulative *= (n - level + 1)
            nodes_per_level.append(cumulative)
    
    # Leaves are n!
    leaf_count = math.factorial(n)
    
    # Internal nodes are sum of levels 0 through n-1
    internal_count = sum(nodes_per_level[:-1])
    
    # Total nodes
    total = internal_count + leaf_count
    
    # Theoretical ratio: total/leaf_count should approach e
    ratio = total / leaf_count if leaf_count > 0 else 0
    
    return {
        'n': n,
        'nodes_per_level': nodes_per_level,
        'leaf_count': leaf_count,
        'internal_count': internal_count,
        'total_nodes': total,
        'total_to_factorial_ratio': ratio,
        'e_approximation': math.e
    }
 
 
def count_nodes_k_permutation_tree(n: int, k: int) -> dict:
    """
    Count nodes for k-permutation tree (arrangements of k items from n).
    
    Tree depth is k (not n), with branching factors: n, n-1, ..., n-k+1
    
    Parameters:
    - n: Total elements available
    - k: Number of positions to fill
    
    Returns: Dictionary with node counts
    """
    nodes_per_level = [1]  # Root
    cumulative = 1
    
    for level in range(1, k + 1):
        cumulative *= (n - level + 1)
        nodes_per_level.append(cumulative)
    
    leaf_count = nodes_per_level[-1]  # P(n,k) = n!/(n-k)!
    internal_count = sum(nodes_per_level[:-1])
    total = internal_count + leaf_count
    
    return {
        'n': n,
        'k': k,
        'nodes_per_level': nodes_per_level,
        'leaf_count': leaf_count,  # P(n,k)
        'internal_count': internal_count,
        'total_nodes': total
    }
 
 
def print_permutation_tree_analysis():
    """
    Display analysis of permutation tree structures.
    """
    print("=" * 70)
    print("PERMUTATION TREE NODE COUNTS")
    print("=" * 70)
    
    print("
FULL PERMUTATION TREES")
    print("-" * 50)
    print(f"{'n':>3} | {'Leaves (n!)':>15} | {'Total Nodes':>15} | {'Ratio to n!':>10}")
    print("-" * 50)
    
    for n in range(1, 13):
        result = count_nodes_permutation_tree(n)
        print(f"{n:3d} | {result['leaf_count']:>15,} | "
              f"{result['total_nodes']:>15,} | {result['total_to_factorial_ratio']:>10.4f}")
    
    print(f"
Note: Ratio converges to e ≈ {math.e:.4f}")
    
    # K-permutation example
    print("
 
K-PERMUTATION TREES (selecting k from n)")
    print("-" * 50)
    n = 10
    print(f"From n={n} elements:
")
    
    for k in range(1, n + 1):
        result = count_nodes_k_permutation_tree(n, k)
        print(f"  k={k:2d}: {result['leaf_count']:>10,} leaves (P({n},{k})), "
              f"{result['total_nodes']:>12,} total nodes")
 
 
def visualize_permutation_tree_shape(n: int):
    """
    Show the 'triangular' shape of a permutation tree.
    """
    print(f"
 
PERMUTATION TREE SHAPE (n={n})")
    print("=" * 70)
    
    result = count_nodes_permutation_tree(n)
    max_width = 50
    max_nodes = max(result['nodes_per_level'])
    
    for level, count in enumerate(result['nodes_per_level']):
        bar_width = int((count / max_nodes) * max_width)
        bar = '█' * bar_width
        print(f"Level {level:2d} | {bar} {count:,}")
    
    print(f"
Observe: Node count INCREASES then hits the leaf explosion at n!")
 
 
# Run all analyses
print_permutation_tree_analysis()
visualize_permutation_tree_shape(6)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126

"""
Demonstrating how constraints affect tree size estimates.
 
We compare theoretical bounds with actual exploration counts
for the N-Queens problem to illustrate constraint power.
"""
 
def n_queens_estimates(n: int) -> dict:
    """
    Calculate various tree size estimates for N-Queens.
    
    Provides:
    1. Naive bound (n^n): assuming any cell is valid
    2. Permutation bound (n!): one queen per column
    3. Actual exploration: with all constraint checking
    4. Valid solutions: queens that satisfy all constraints
    """
    import math
    
    # Count actual tree nodes explored with full constraints
    nodes_explored = 0
    solutions_found = 0
    
    def is_safe(board: list, row: int, col: int) -> bool:
        """Check if placing queen at (row, col) is safe."""
        for prev_row in range(row):
            prev_col = board[prev_row]
            # Same column or diagonal
            if prev_col == col or abs(prev_col - col) == abs(prev_row - row):
                return False
        return True
    
    def solve(board: list, row: int):
        nonlocal nodes_explored, solutions_found
        nodes_explored += 1
        
        if row == n:
            solutions_found += 1
            return
        
        for col in range(n):
            if is_safe(board, row, col):
                board.append(col)
                solve(board, row + 1)
                board.pop()
    
    solve([], 0)
    
    naive_bound = n ** n
    perm_bound = math.factorial(n)
    
    return {
        'n': n,
        'naive_bound_n^n': naive_bound,
        'permutation_bound_n!': perm_bound,
        'actual_nodes_explored': nodes_explored,
        'valid_solutions': solutions_found,
        'pruning_ratio_from_naive': naive_bound / nodes_explored if nodes_explored else float('inf'),
        'pruning_ratio_from_perm': perm_bound / nodes_explored if nodes_explored else float('inf')
    }
 
 
def print_constraint_analysis():
    """
    Show how constraints reduce tree exploration across N-Queens variants.
    """
    print("=" * 80)
    print("N-QUEENS: CONSTRAINT IMPACT ON TREE SIZE")
    print("=" * 80)
    print()
    print(f"{'n':>3} | {'n^n':>12} | {'n!':>10} | {'Explored':>10} | "
          f"{'Solutions':>9} | {'Pruning Factor':>14}")
    print("-" * 80)
    
    for n in range(4, 13):
        result = n_queens_estimates(n)
        print(f"{n:3d} | {result['naive_bound_n^n']:>12,} | "
              f"{result['permutation_bound_n!']:>10,} | "
              f"{result['actual_nodes_explored']:>10,} | "
              f"{result['valid_solutions']:>9} | "
              f"{result['pruning_ratio_from_naive']:>14.1f}x")
    
    print()
    print("Key insight: Actual exploration is ORDERS OF MAGNITUDE smaller than")
    print("theoretical bounds, demonstrating the power of constraint propagation.")
 
 
def visualize_constraint_layers():
    """
    Illustrate how each constraint layer reduces the search space.
    """
    print("
 
" + "=" * 70)
    print("CONSTRAINT LAYER VISUALIZATION (8-Queens)")
    print("=" * 70)
    
    import math
    n = 8
    
    layers = [
        ("No constraints (n^n)", n**n),
        ("One queen per row (n^n)", n**n),  # Same as above with row iteration
        ("+ One per column (n!)", math.factorial(n)),
        ("+ No diagonal attacks", 2057),  # Actual 8-queens exploration
        ("Valid solutions only", 92)
    ]
    
    print()
    max_width = 50
    base = layers[0][1]
    
    for name, count in layers:
        if count > 0:
            log_ratio = math.log10(count) / math.log10(base) if count > 1 else 0
            bar_width = int(log_ratio * max_width)
            bar = '█' * bar_width
            print(f"{name:35s}: {count:>12,}  {bar}")
    
    print()
    print("Each constraint layer EXPONENTIALLY reduces the search space.")
 
 
# Run the analysis
print_constraint_analysis()
visualize_constraint_layers()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152

"""
Practical techniques for estimating search tree size
when analytical formulas are unavailable or complex.
"""
 
import math
from typing import Callable, List, Tuple
 
def estimate_complexity_from_samples(
    algorithm: Callable[[int], int],
    sample_sizes: List[int]
) -> dict:
    """
    Estimate complexity class by sampling algorithm behavior.
    
    Parameters:
    - algorithm: Function that takes input size n and returns node count
    - sample_sizes: List of n values to test
    
    Returns: Complexity analysis with predictions
    """
    # Collect samples
    samples = []
    for n in sample_sizes:
        node_count = algorithm(n)
        samples.append((n, node_count))
    
    # Analyze growth pattern
    growth_rates = []
    for i in range(1, len(samples)):
        n1, c1 = samples[i-1]
        n2, c2 = samples[i]
        
        # Ratio analysis
        ratio = c2 / c1 if c1 > 0 else 0
        
        # Check if exponential: ratio ≈ constant
        # Check if factorial: ratio ≈ n2
        growth_rates.append({
            'from_n': n1,
            'to_n': n2,
            'ratio': ratio,
            'expected_exp_ratio': 2 ** (n2 - n1),  # For O(2^n)
            'expected_fact_ratio': math.prod(range(n1 + 1, n2 + 1))  # For O(n!)
        })
    
    # Determine best-fit complexity class
    avg_ratio = sum(g['ratio'] for g in growth_rates) / len(growth_rates)
    
    # Estimate base of exponential
    log_ratio = math.log(avg_ratio) if avg_ratio > 1 else 0
    estimated_base = math.exp(log_ratio)  # Approx base if O(b^n)
    
    return {
        'samples': samples,
        'growth_rates': growth_rates,
        'average_ratio': avg_ratio,
        'estimated_exponential_base': estimated_base,
        'complexity_guess': 'O(2^n)' if 1.8 < estimated_base < 2.2 else 
                           'O(n!)' if estimated_base > 3 else
                           f'O({estimated_base:.2f}^n)'
    }
 
 
def predict_tree_size(samples: List[Tuple[int, int]], target_n: int) -> int:
    """
    Predict tree size for target_n based on observed samples.
    Uses log-linear regression for exponential extrapolation.
    """
    import statistics
    
    # Convert to log scale for linear regression
    log_counts = [(n, math.log(c)) for n, c in samples if c > 0]
    
    # Simple linear regression on log values
    n_vals = [x[0] for x in log_counts]
    log_vals = [x[1] for x in log_counts]
    
    n_mean = statistics.mean(n_vals)
    log_mean = statistics.mean(log_vals)
    
    # Calculate slope
    numerator = sum((n - n_mean) * (lv - log_mean) 
                    for n, lv in zip(n_vals, log_vals))
    denominator = sum((n - n_mean) ** 2 for n in n_vals)
    
    slope = numerator / denominator if denominator else 0
    intercept = log_mean - slope * n_mean
    
    # Predict
    predicted_log = slope * target_n + intercept
    return int(math.exp(predicted_log))
 
 
def demonstrate_estimation():
    """
    Demonstrate estimation techniques on known problems.
    """
    print("=" * 70)
    print("TREE SIZE ESTIMATION DEMONSTRATION")
    print("=" * 70)
    
    # Example: N-Queens node counting
    def n_queens_nodes(n: int) -> int:
        count = 0
        def solve(row, cols, diags, anti_diags):
            nonlocal count
            count += 1
            if row == n:
                return
            for col in range(n):
                if col in cols or (row - col) in diags or (row + col) in anti_diags:
                    continue
                cols.add(col)
                diags.add(row - col)
                anti_diags.add(row + col)
                solve(row + 1, cols, diags, anti_diags)
                cols.remove(col)
                diags.remove(row - col)
                anti_diags.remove(row + col)
        solve(0, set(), set(), set())
        return count
    
    sample_sizes = [4, 5, 6, 7, 8, 9, 10]
    samples = [(n, n_queens_nodes(n)) for n in sample_sizes]
    
    print("
N-Queens Node Counts (actual measurements):")
    print("-" * 40)
    for n, count in samples:
        print(f"  n={n:2d}: {count:>10,} nodes")
    
    # Predict for larger n
    print("
Predictions based on extrapolation:")
    print("-" * 40)
    for target in [11, 12, 13, 14]:
        predicted = predict_tree_size(samples, target)
        print(f"  n={target:2d}: ~{predicted:>12,} nodes (predicted)")
    
    # Verify one prediction
    print("
Verification (computing actual):")
    actual_11 = n_queens_nodes(11)
    predicted_11 = predict_tree_size(samples, 11)
    print(f"  n=11 actual:    {actual_11:>12,}")
    print(f"  n=11 predicted: {predicted_11:>12,}")
    print(f"  Error: {abs(actual_11 - predicted_11) / actual_11 * 100:.1f}%")
 
 
# Run demonstration
demonstrate_estimation()