Ternary representation of Cantor set

0 0 9 minutes read

Given three integers A, B and L, the task is to print the ternary cantor set from range [A, B] upto L levels.
Ternary Cantor Set: A ternary Cantor set is a set built by removing the middle part of a line segment when divided into 3 parts and repeating this process with the remaining shorter segments. Below is an illustration of a cantor set.

An illustration of a Ternary Cantor Set

Examples:

Input: A = 0, B = 1, L = 2
Output:
Level 0: [0.000000] — [1.000000]
Level 1: [0.000000] — [0.333333] [0.666667] — [1.000000]
Level 2: [0.000000] — [0.111111] [0.222222] — [0.333333] [0.666667] — [0.777778] [0.888889] — [1.000000]
Explanation: For the given range [0, 1], in level 1, it is divided into three parts ([0, 0.33], [0.33, 0.67], [0.67, 1]). From the three parts, the middle part is ignored. This process is continued for every part in the subsequent executions.
Input: A = 0, B = 9, L = 3
Output:
Level_0: [0.000000] — [9.000000]
Level_1: [0.000000] — [3.000000] [6.000000] — [9.000000]
Level_2: [0.000000] — [1.000000] [2.000000] — [3.000000] [6.000000] — [7.000000] [8.000000] — [9.000000]
Level_3: [0.000000] — [0.333333] [0.666667] — [1.000000] [2.000000] — [2.333333] [2.666667] — [3.000000] [6.000000] — [6.333333] [6.666667] — [7.000000] [8.000000] — [8.333333] [8.666667] — [9.000000]

Approach:

Create a linked list data structure for each node of the Set, having the start value, end value and a pointer to the next node.
Initialize the list with the start and end value given as the input.
For the next level:
- Create a new node where the difference between the start and end values is $\frac{1}{3} rd$ of the initial, i.e. start value is $\frac{1}{3} rd$ less than the initial end value.
- Further, modify the original node, such that the end value is $\frac{1}{3} rd$ more of the initial start value.
- Place the pointer to the new node after the original one accordingly

Below is the implementation of the above approach:

C++

// C++ implementation to find the cantor set
// for n levels and
// for a given start_num and end_num
#include <bits/stdc++.h>
using namespace std;
 
// The Linked List Structure for the Cantor Set
typedef struct cantor {
    double start, end;
    struct cantor* next;
} Cantor;
 
// Function to initialize the Cantor Set List
Cantor* startList(Cantor* head,
                double start_num,
                double end_num)
{
    if (head == NULL) {
        head = new Cantor;
        head->start = start_num;
        head->end = end_num;
        head->next = NULL;
    }
    return head;
}
 
// Function to propagate the list
// by adding new nodes for the next levels
Cantor* propagate(Cantor* head)
{
    Cantor* temp = head;
 
    if (temp != NULL) {
        Cantor* newNode
            = new Cantor;
        double diff
            = (((temp->end) - (temp->start)) / 3);
 
        // Modifying the start and end values
        // for the next level
        newNode->end = temp->end;
        temp->end = ((temp->start) + diff);
        newNode->start = (newNode->end) - diff;
 
        // Changing the pointers
        // to the next node
        newNode->next = temp->next;
        temp->next = newNode;
 
        // Recursively call the function
        // to generate the Cantor Set
        // for the entire level
        propagate(temp->next->next);
    }
 
    return head;
}
 
// Function to print a level of the Set
void print(Cantor* temp)
{
    while (temp != NULL) {
        printf("[%lf] -- [%lf]\t",
            temp->start, temp->end);
        temp = temp->next;
    }
    cout << endl;
}
 
// Function to build and display
// the Cantor Set for each level
void buildCantorSet(int A, int B, int L)
{
    Cantor* head = NULL;
    head = startList(head, A, B);
    for (int i = 0; i < L; i++) {
        cout <<"Level_"<< i<<" : ";
        print(head);
        propagate(head);
    }
    cout <<"Level_"<< L<<" : ";
    print(head);
}
 
// Driver code
int main()
{
    int A = 0;
    int B = 9;
    int L = 2;
    buildCantorSet(A, B, L);
 
    return 0;
}
 
// This code is contributed by shivanisingh

C

// C implementation to find the cantor set
// for n levels and
// for a given start_num and end_num
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
// The Linked List Structure for the Cantor Set
typedef struct cantor {
    double start, end;
    struct cantor* next;
} Cantor;
 
// Function to initialize the Cantor Set List
Cantor* startList(Cantor* head,
                  double start_num,
                  double end_num)
{
    if (head == NULL) {
        head = (Cantor*)malloc(sizeof(Cantor));
        head->start = start_num;
        head->end = end_num;
        head->next = NULL;
    }
    return head;
}
 
// Function to propagate the list
// by adding new nodes for the next levels
Cantor* propagate(Cantor* head)
{
    Cantor* temp = head;
 
    if (temp != NULL) {
        Cantor* newNode
            = (Cantor*)malloc(sizeof(Cantor));
        double diff
            = (((temp->end) - (temp->start)) / 3);
 
        // Modifying the start and end values
        // for the next level
        newNode->end = temp->end;
        temp->end = ((temp->start) + diff);
        newNode->start = (newNode->end) - diff;
 
        // Changing the pointers
        // to the next node
        newNode->next = temp->next;
        temp->next = newNode;
 
        // Recursively call the function
        // to generate the Cantor Set
        // for the entire level
        propagate(temp->next->next);
    }
 
    return head;
}
 
// Function to print a level of the Set
void print(Cantor* temp)
{
    while (temp != NULL) {
        printf("[%lf] -- [%lf]\t",
               temp->start, temp->end);
        temp = temp->next;
    }
    printf("\n");
}
 
// Function to build and display
// the Cantor Set for each level
void buildCantorSet(int A, int B, int L)
{
    Cantor* head = NULL;
    head = startList(head, A, B);
    for (int i = 0; i < L; i++) {
        printf("Level_%d : ", i);
        print(head);
        propagate(head);
    }
    printf("Level_%d : ", L);
    print(head);
}
 
// Driver code
int main()
{
    int A = 0;
    int B = 9;
    int L = 2;
    buildCantorSet(A, B, L);
 
    return 0;
}

Java

// Java implementation to find the cantor set
// for n levels and
// for a given start_num and end_num
 
class GFG
{
 
    // The Linked List Structure for the Cantor Set
    static class Cantor
    {
        double start, end;
        Cantor next;
    };
 
    static Cantor Cantor;
 
    // Function to initialize the Cantor Set List
    static Cantor startList(Cantor head, double start_num, 
                            double end_num)
    {
        if (head == null) 
        {
            head = new Cantor();
            head.start = start_num;
            head.end = end_num;
            head.next = null;
        }
        return head;
    }
 
    // Function to propagate the list
    // by adding new nodes for the next levels
    static Cantor propagate(Cantor head) 
    {
        Cantor temp = head;
 
        if (temp != null)
        {
            Cantor newNode = new Cantor();
            double diff = (((temp.end) - (temp.start)) / 3);
 
            // Modifying the start and end values
            // for the next level
            newNode.end = temp.end;
            temp.end = ((temp.start) + diff);
            newNode.start = (newNode.end) - diff;
 
            // Changing the pointers
            // to the next node
            newNode.next = temp.next;
            temp.next = newNode;
 
            // Recursively call the function
            // to generate the Cantor Set
            // for the entire level
            propagate(temp.next.next);
        }
 
        return head;
    }
 
    // Function to print a level of the Set
    static void print(Cantor temp)
    {
        while (temp != null) 
        {
            System.out.printf("[%f] -- [%f]", temp.start, temp.end);
            temp = temp.next;
        }
        System.out.printf("\n");
    }
 
    // Function to build and display
    // the Cantor Set for each level
    static void buildCantorSet(int A, int B, int L)
    {
        Cantor head = null;
        head = startList(head, A, B);
        for (int i = 0; i < L; i++) 
        {
            System.out.printf("Level_%d : ", i);
            print(head);
            propagate(head);
        }
        System.out.printf("Level_%d : ", L);
        print(head);
    }
 
    // Driver code
    public static void main(String[] args) 
    {
        int A = 0;
        int B = 9;
        int L = 2;
        buildCantorSet(A, B, L);
    }
}
 
// This code is contributed by Rajput-Ji

Python3

# Python3 implementation to find the cantor set
# for n levels and
# for a given start_num and end_num
# The Linked List Structure for the Cantor Set
class Cantor:
 
    def __init__(self):
     
        self.start = 0;
        self.end = 0;
        self.next = None;
     
cantor = None;
 
# Function to initialize the Cantor Set List
def startList(head, start_num, end_num):
 
    if (head == None) :
     
        head = Cantor();
        head.start = start_num;
        head.end = end_num;
        head.next = None;
     
    return head;
 
# Function to propagate the list
# by adding new nodes for the next levels
def propagate(head):
 
    temp = head;
 
    if (temp != None):
     
        newNode = Cantor();
        diff = (((temp.end) - (temp.start)) / 3);
         
        # Modifying the start and end values
        # for the next level
        newNode.end = temp.end;
        temp.end = ((temp.start) + diff);
        newNode.start = (newNode.end) - diff;
         
        # Changing the pointers
        # to the next node
        newNode.next = temp.next;
        temp.next = newNode;
         
        # Recursively call the function
        # to generate the Cantor Set
        # for the entire level
        propagate(temp.next.next);
     
    return head;
 
# Function to Print a level of the Set
def Print(temp):
 
    while (temp != None) :
     
        print("[", temp.start, "] -- [", temp.end, "] ", sep = "", end = "");
        temp = temp.next;
     
    print()
 
# Function to build and display
# the Cantor Set for each level
def buildCantorSet(A, B, L):
 
    head = None;
    head = startList(head, A, B);
    for i in range(L):
     
        print("Level_", i, " : ", sep = "", end = "");
        Print(head);
        propagate(head);
     
    print("Level_", L, " : ", end = "", sep = "");
    Print(head);
 
# Driver code
A = 0;
B = 9;
L = 2;
buildCantorSet(A, B, L);
 
# This code is contributed by phasing17

C#

// C# implementation to find the cantor set
// for n levels and
// for a given start_num and end_num
using System;
 
class GFG
{
 
    // The Linked List Structure for the Cantor Set
    class Cantor
    {
        public double start, end;
        public Cantor next;
    };
 
    static Cantor cantor;
 
    // Function to initialize the Cantor Set List
    static Cantor startList(Cantor head, double start_num, 
                            double end_num)
    {
        if (head == null) 
        {
            head = new Cantor();
            head.start = start_num;
            head.end = end_num;
            head.next = null;
        }
        return head;
    }
 
    // Function to propagate the list
    // by adding new nodes for the next levels
    static Cantor propagate(Cantor head) 
    {
        Cantor temp = head;
 
        if (temp != null)
        {
            Cantor newNode = new Cantor();
            double diff = (((temp.end) - (temp.start)) / 3);
 
            // Modifying the start and end values
            // for the next level
            newNode.end = temp.end;
            temp.end = ((temp.start) + diff);
            newNode.start = (newNode.end) - diff;
 
            // Changing the pointers
            // to the next node
            newNode.next = temp.next;
            temp.next = newNode;
 
            // Recursively call the function
            // to generate the Cantor Set
            // for the entire level
            propagate(temp.next.next);
        }
 
        return head;
    }
 
    // Function to print a level of the Set
    static void print(Cantor temp)
    {
        while (temp != null) 
        {
            Console.Write("[{0:F6}] -- [{1:F6}]", 
                            temp.start, temp.end);
            temp = temp.next;
        }
        Console.Write("\n");
    }
 
    // Function to build and display
    // the Cantor Set for each level
    static void buildCantorSet(int A, int B, int L)
    {
        Cantor head = null;
        head = startList(head, A, B);
        for (int i = 0; i < L; i++) 
        {
            Console.Write("Level_{0} : ", i);
            print(head);
            propagate(head);
        }
        Console.Write("Level_{0} : ", L);
        print(head);
    }
 
    // Driver code
    public static void Main(String[] args) 
    {
        int A = 0;
        int B = 9;
        int L = 2;
        buildCantorSet(A, B, L);
    }
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
 
// Javascript implementation to find the cantor set
// for n levels and
// for a given start_num and end_num
// The Linked List Structure for the Cantor Set
class Cantor
{
    constructor()
    {
        this.start = 0;
        this.end = 0;
        this.next = null;
    }
};
 
var cantor = null;
 
// Function to initialize the Cantor Set List
function startList(head, start_num, end_num)
{
    if (head == null) 
    {
        head = new Cantor();
        head.start = start_num;
        head.end = end_num;
        head.next = null;
    }
    return head;
}
// Function to propagate the list
// by adding new nodes for the next levels
function propagate(head) 
{
    var temp = head;
 
    if (temp != null)
    {
        var newNode = new Cantor();
        var diff = (((temp.end) - (temp.start)) / 3);
        // Modifying the start and end values
        // for the next level
        newNode.end = temp.end;
        temp.end = ((temp.start) + diff);
        newNode.start = (newNode.end) - diff;
        // Changing the pointers
        // to the next node
        newNode.next = temp.next;
        temp.next = newNode;
        // Recursively call the function
        // to generate the Cantor Set
        // for the entire level
        propagate(temp.next.next);
    }
    return head;
}
// Function to print a level of the Set
function print(temp)
{
    while (temp != null) 
    {
        document.write("["+temp.start.toFixed(6)+"] -- ["+
        temp.end.toFixed(6)+"] ");
        temp = temp.next;
    }
    document.write("<br>");
}
// Function to build and display
// the Cantor Set for each level
function buildCantorSet(A, B, L)
{
    var head = null;
    head = startList(head, A, B);
    for (var i = 0; i < L; i++) 
    {
        document.write("Level_"+ i +" : ");
        print(head);
        propagate(head);
    }
    document.write("Level_"+ L +" : ");
    print(head);
}
// Driver code
var A = 0;
var B = 9;
var L = 2;
buildCantorSet(A, B, L);
 
 
</script>

Output:
Level_0 : [0.000000] — [9.000000]
Level_1 : [0.000000] — [3.000000] [6.000000] — [9.000000]
Level_2 : [0.000000] — [1.000000] [2.000000] — [3.000000] [6.000000] — [7.000000] [8.000000] — [9.000000]

References: Cantor Set Wikipedia
Related Article: N-th term of George Cantor set of rational numbers

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!