Print A Cantor Set Pattern In C++

In this article, we will discuss the Print a Cantor Set Pattern in C++ with its approach, an example, time complexity, and space complexity.

Cantor Set Pattern:

The middle third of a line segment is repeatedly removed to produce the Ternary Cantor Set, a fractal structure. The procedure starts with a single segment, which is subsequently divided into three equal parts, with the middle section being removed. The remaining two segments are then subjected to this process iteratively, resulting in a structure that is self-similar but increasingly fragmented. The set transforms into an endlessly large collection of disconnected intervals as the number of iterations increases, illustrating the mathematical analysis concepts of self-similarity and nowhere density.

Approach:

Method for Building a Ternary Cantor Set Making Use of 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:

Start with a single node that has start and end values specified and represents the complete first segment [0,1].

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

The new reduced length for each existing segment [start, end] is calculated 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

In order to create the subsequent level of the Cantor set, keep iterating through the linked list and perform the same modification to every segment.

Example:

Let us take an example to illustrate the Duck Number in C++ .

Example


#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:

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 uses a linked list method to generate and display the Cantor Set. A dynamically allocated linked list is used to iteratively remove the middle third from each segment at each level after initializing the list with a single segment. Whereas displayCantorSet prints the segments at each level, generateNextLevel updates the segment endpoints and adds new segments appropriately. In order to ensure flexibility in the creation of Cantor sets, user input is obtained for the start value, end value, and number of levels.