Print A Cantor Set Pattern In C++

In this guide, we will explore how to generate a Cantor Set Pattern in C++ including its methodology, a demonstration, time analysis, and memory usage.

Cantor Set Pattern:

The central one-third portion of a line segment is iteratively eliminated to generate the Ternary Cantor Set, an intricate fractal pattern. Initially, a single segment is divided into three equal parts, and the middle part is excised. This process is then applied to the remaining two segments repeatedly, leading to a pattern that is self-replicating yet progressively more fragmented. With each iteration, the set evolves into a vast array of disjointed intervals, demonstrating the mathematical principles of self-similarity and nowhere density.

Approach:

Creating a Ternary Cantor Set Using Linked Lists.

We use a linked list data structure, in which each node represents a segment of the Ternary Cantor Set, to efficiently represent and produce the set. Three key elements are included in every node:

• ✅ Start value: The beginning of the segment.
• ✅ End value: The end of the segment.
• ✅ Pointer to the next node: A link to the next list segment is called a pointer to the next node.

Steps:

1. Initialize the Linked List:

Begin with a solitary node that includes defined start and end values, representing the entirety of the initial segment [0,1].

2. Iterative Refinement (For Each Level of the Cantor Set):

The updated reduced size for each current segment [beginning, conclusion] is computed as:

(end - start) / 3.

To indicate the right segment, create a new node:

• ✅ This new node has an end - new_length as its start value.
• ✅ The original end value remains.
• ✅ Modify the current node to represent the left segment:
• ✅ The adjusted end value is start + new_length.
• ✅ In order to place the new node in the correct position within the list, modify the pointers.

3. Repeat the Process

To generate the next stage of the Cantor set, continue iterating over the linked list and apply the identical alteration to each segment.

Example:

Let's consider an example to demonstrate the concept of Duck Number in C++.

#include <iostream>
#include <iomanip>
using namespace std;
// Structure representing a segment in the Cantor set
struct CantorSegment 
{
    double start, end;
    CantorSegment* next;
};
// Function to initialize the linked list with the first segment
CantorSegment* initializeList(double start, double end) 
{
    CantorSegment* head = new CantorSegment;
    head->start = start;
    head->end = end;
    head->next = nullptr;
    return head;
}
// Function to generate the next level of the Cantor set
void generateNextLevel(CantorSegment* head)
{
    CantorSegment* current = head;
    while (current != nullptr)
    {
        double segmentLength = (current->end - current->start) / 3.0;
        CantorSegment* newSegment = new CantorSegment;
        // Setting up new segment values
        newSegment->start = current->end - segmentLength;
        newSegment->end = current->end;
        newSegment->next = current->next;
        // Updating the current segment
        current->end = current->start + segmentLength;
        current->next = newSegment;
        // Move two steps ahead to process the next segment
        current = newSegment->next;
    }
}
// Function to display the Cantor set at each level
void displayCantorSet(CantorSegment* head, int level)
{
    cout << "Level " << level << ": ";
    CantorSegment* current = head;
    while (current != nullptr)
    {
        cout << "[" << fixed << setprecision(3) << current->start << ", " << current->end << "]  ";
        current = current->next;
    }
    cout << endl;
}
// Function to build and display the Cantor set up to a given level
void buildCantorSet(double start, double end, int levels) 
{
    CantorSegment* head = initializeList(start, end);
    for (int i = 0; i < levels; i++) 
    {
        displayCantorSet(head, i);
        generateNextLevel(head);
    }
    displayCantorSet(head, levels);
}
// Main function to take user input and generate the Cantor set
int main()
{
    double start, end;
    int levels;
    cout << "Enter the start value: ";
    cin >> start;
    cout << "Enter the end value: ";
    cin >> end;
    cout << "Enter the number of levels: ";
    cin >> levels;
    cout << "\nGenerating Cantor Set:\n";
    buildCantorSet(start, end, levels);
    return 0;
}

Output:

Enter the start value: 0
Enter the end value: 9
Enter the number of levels: 3
Generating Cantor Set:
Level 0: [0.000, 9.000]  
Level 1: [0.000, 3.000]  [6.000, 9.000]  
Level 2: [0.000, 1.000]  [2.000, 3.000]  [6.000, 7.000]  [8.000, 9.000]  
Level 3: [0.000, 0.333]  [0.667, 1.000]  [2.000, 2.333]  [2.667, 3.000]  [6.000, 6.333]  [6.667, 7.000]  [8.000, 8.333]  [8.667, 9.000]

Complexity Analysis:

• ✅ Time Complexity: O(2^L)
• ✅ Space Complexity: O(2^L)

Explanation:

This C++ program implements the Cantor Set generation using a linked list approach. The program utilizes a dynamically allocated linked list to systematically eliminate the middle third from each segment at every level. Initially, the list is set up with a single segment. The function displayCantorSet is responsible for showcasing the segments at each level, while generateNextLevel manages the adjustment of segment boundaries and the addition of new segments as needed. To enhance the program's versatility in creating Cantor sets, user interaction prompts for the initiation value, conclusion value, and level count.