Application of Prufer Code: Random Tree Generation, Cayley’s Formula and Building Tree from Degree Count

On the last post (Prufer Code: Linear Representation of a Labeled Tree), we discussed how to convert a labeled tree into Prufer Code and vice versa. On this post, we will look into some of its applications in problem-solving.

Generating Random Tree

This one is the simplest. Though problem-solving may not require generating random trees, problem setting might. In order to generate a random tree with $N$ nodes, all we need to do is generate a Prufer Code of length $N-2$ with each element being in the range of $1$ to $N$. Next, we just convert the Prufer Code into a tree.

The randomness of the tree depends on the randomness of the sequence generated. Using rand() function is not good since it’s not truly random. How we can generate a random sequence requires a blog post of its own. Maybe I will write a post on it in near future.

Read More

Prufer Code: Linear Representation of a Labeled Tree

I guess this is going to be my first post (apart from the contest analysis’) which is not about Number Theory! It’s not about graph either, even though the title has “Tree” in it. This post is actually about Combinatorics.

Prufer code, in my opinion, is one of the most underrated algorithms I have learned. It has a wide range of applications, yet, very few people seem to know about it. It’s not even a hard algorithm! It’s very easy and you should understand it intuitively.

In this post, we will be discussing what is Prufer Code and its conversion to and from a tree. On next post, we will look into some of its application.

Prufer Code: What is it?

Every labeled tree of $N$ nodes can be uniquely represented as an array of $N-2$ integers and vice versa

The linear array representation of a labeled tree is called Prufer Code. In case you are wondering what’s a labeled tree, it’s just a tree with distinguishable nodes, i.e, each node is marked such that they can be distinguished from one another.

Okay, before we move on to how to covert a labeled tree into Prufer Code and vice versa, let me tell you how I came to know about Prufer Code. If you are a problem setter, the story will be helpful to you.

Read More

Chinese Remainder Theorem Part 2 – Non Coprime Moduli

As promised on the last post, today we are going to discuss the “Strong Form” of Chinese Remainder Theorem, i.e, what do we do when the moduli in the congruence equations are not pairwise coprime. The solution is quite similar to the one we have already discussed in the previous post, so hopefully, it will be a lot easier to understand.

Prerequisite

If you haven’t read my previous post, you can find it here: Chinese Remainder Theorem Part 1. I strongly suggest you read that one before proceeding onwards.

Problem

Given two sequences of numbers $A = [a_1, a_2, \dots, a_n]$ and $M = [m_1, m_2, \dots, m_n]$, find the smallest solution to the following linear congruence equations if it exists:

$$x \equiv a_1 \text{(mod } m_1) \\ x \equiv a_2 \text{(mod } m_2) \\ \dots \\ x \equiv a_n \text{(mod } m_n)$$

Note: The elements of $M$ are not pairwise coprime

Read More


Fatal error: Uncaught Error: Call to undefined function is_user_logged_in() in /home/forthrig/public_html/wp-content/plugins/auto-terms-of-service-and-privacy-policy/includes/frontend.php:126 Stack trace: #0 [internal function]: wpautoterms\Frontend::_out_head('<!DOCTYPE html>...', 9) #1 /home/forthrig/public_html/wp-includes/functions.php(4556): ob_end_flush() #2 /home/forthrig/public_html/wp-includes/class-wp-hook.php(288): wp_ob_end_flush_all('') #3 /home/forthrig/public_html/wp-includes/class-wp-hook.php(312): WP_Hook->apply_filters('', Array) #4 /home/forthrig/public_html/wp-includes/plugin.php(478): WP_Hook->do_action(Array) #5 /home/forthrig/public_html/wp-includes/load.php(947): do_action('shutdown') #6 [internal function]: shutdown_action_hook() #7 {main} thrown in /home/forthrig/public_html/wp-content/plugins/auto-terms-of-service-and-privacy-policy/includes/frontend.php on line 126