Tech

Analysis of Title Hierarchy Structure

Abstract: This report aims to analyze a specific type of integer sequence and derive all possible hierarchical structures for it. The core of the problem is to reconstruct the implicit, nested tree-like hierarchy from a flat, one-dimensional sequence representing heading numbers. The report specifies the constraints for this problem and provides a complete algorithm capable of finding all possible solutions. The analysis shows that multiple valid solutions may exist, classifying the problem as a Constraint Satisfaction Problem (CSP), which can be systematically solved using a backtracking algorithm.

1. Problem Description

Given an article that uses a consistent numbering format for its sections, how can we reconstruct its implicit tree-like hierarchical structure?

For example, given a sequence like:

1
2
3
4
5
6
7
1 xx
2 xx
1 xx
2 xx
3 xx
1 xx
...

This can be abstracted as follows: given a sequence of positive integers (e.g., [1, 2, 1, 2, 3, 1, 2, 3, 4, 3]), we need to assign a level to each number in the sequence. This level is also represented by a sequence of positive integers, indicating its depth in the document structure (e.g., level-1 heading, level-2 heading, etc.). For instance, [1, 1, 2, 2, 2, 3, 3, 3, 2, 1] and [1, 1, 2, 2, 2, 3, 3, 3, 3, 1] are both valid solutions.

We have determined that a valid hierarchical structure must adhere to the following complete set of constraint rules:

  1. Starting Rule: The first number in the sequence must be 1, and its level is fixed at 1.

  2. Headings Start with 1: If a number in the sequence is 1, its level must be one greater than the level of the preceding number (i.e., level_of_prev + 1).

  3. Level Rule for Non-1s: For any number n > 1 in the sequence, its level L can be any integer such that 1 <= L <= L_prev, where L_prev is the level of the preceding number.

  4. Same-Level Order Rule: At any given level, the heading numbers must appear in a strictly and sequentially increasing order. For example, a sequence of level-2 headings can be 1, 2, 3, but not 1, 3 or 1, 2, 2.

Goal: To find and list all possible level assignment schemes that satisfy all the above rules.

2. Problem Abstraction

This problem can be precisely modeled as a Constraint Satisfaction Problem (CSP).

A CSP consists of three core components:

  • Variables: The unknowns we need to solve for. In this problem, the variables are the levels of each number in the sequence, which can be represented as a set {L_0, L_1, ..., L_{n-1}}, where L_i is the level of the i-th number in the sequence.

  • Domains: The possible values for each variable.

    • For L_0, the domain is {1}.

    • For L_i (where i > 0):

      • If sequence[i] == 1, its domain is {L_{i-1} + 1}.

      • If sequence[i] > 1, its domain is {1, 2, ..., L_{i-1}}.

  • Constraints: The relationships that must hold between the variables. These are the global rules we defined in the problem description, especially the “Same-Level Order Rule.” A formal constraint can be described as: “For any two indices i < j, if their levels are the same (L_i = L_j) and there are no other elements with the same level between them, then it must be that sequence[j] == sequence[i] + 1.”

3. Solution and Algorithm Design

A common and powerful method for solving CSPs is the Backtracking Algorithm. This algorithm systematically explores all possible solutions using a depth-first search (DFS) approach.

The Problem of Multiple Solutions

The sole reason for the existence of multiple solutions is as follows: when the algorithm processes a number that is not ‘1’, there are at least two or more theoretically possible levels it could be assigned to, both of which simultaneously satisfy the global “Same-Level Order Rule.”

This occurs when a number meets the following conditions:

  1. It must be a number other than 1 in the sequence; let’s call it X.

  2. When processing X, the level of the preceding number, L_prev, must be greater than or equal to 2. This provides at least two theoretical level choices for X (e.g., level 1 and level 2). If L_prev were 1, X‘s only possible choice would be level 1, creating no branching.

  3. There are multiple valid “parents.” In the sequence preceding X, there must exist at least two different levels whose last number was X-1.

    • “Parent A”: There exists a level L_A whose last number was X-1.

    • “Parent B”: There also exists a different level L_B (L_B != L_A) whose last number was also X-1.

    • Furthermore, both L_A and L_B must be within X‘s range of possible levels (i.e., both must be less than or equal to L_prev).

Algorithm Implementation (Python)

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
def find_all_structures(sequence):

    if not sequence or sequence[0] != 1:
        return []

    solutions = []

    def backtrack(index, current_levels):
        if index == len(sequence):
            solutions.append(list(current_levels))
            return

        current_num = sequence[index]
        prev_level = current_levels[index - 1]

        if current_num == 1:
            new_level = prev_level + 1
            current_levels.append(new_level)
            backtrack(index + 1, current_levels)
            current_levels.pop()
            return

        for potential_level in range(1, prev_level + 1):
            last_sibling_value = -1
            level_exists = False
            for i in range(index - 1, -1, -1):
                if current_levels[i] == potential_level:
                    last_sibling_value = sequence[i]
                    level_exists = True
                    break
            
            is_valid = False
            if level_exists:
                if current_num == last_sibling_value + 1:
                    is_valid = True
            
            if is_valid:
                current_levels.append(potential_level)
                backtrack(index + 1, current_levels)
                current_levels.pop()
                
    backtrack(1, [1])
    return solutions