Thue-Morse sequence in Java
The Thue-Morse sequence is an infinite binary sequence that is constructed by starting with 0 and successively appending the bitwise negation (binary complement) of the sequence.
The first few terms of the Thue-Morse sequence are:
0, 1, 10, 1001, 10010110, …
To construct the Thue-Morse sequence:
- Start with 0.
- Append the bitwise negation of the sequence obtained so far.
For example:
Step 1: 0
Step 2: 0 1
Step 3: 0 1 1 0
Step 4: 0 1 1 0 1 0 0 1
And so on...
Example 1
Input: n = 1
Output: 0
Explanation: In the first iteration, the sequence starts with 0.
Example 2
Input: n = 2
Output: 01
Explanation: In the second iteration, the sequence is 0 followed by the negation 1.
Example 3
Input: n = 3
Output: 0110
Explanation: In the third iteration, the sequence 01 is followed by the negation 10.
Example 4
Input: n = 5
Output: 0110100110010110
Explanation: In the fifth iteration, the sequence 01101001 is followed by the negation 10010110.
Approach 1: Using Iterative Approach
The iterative approach to generating the Thue-Morse sequence constructs the sequence step by step. Starting with the initial sequence "0", for each subsequent iteration, the current sequence is extended by appending its bitwise negation.
Algorithm
Step 1: Start with the initial sequence sequence set to "0".
Step 2: Iterate for n-1 Iterations:
Step 2.1: For each iteration i from 1 to n-1:
Step 2.2: Create a temporary copy of the current sequence (temp).
Step 2.3: Append the bitwise negation of each character in the temporary sequence to the original sequence:
Step 2.4: For each character j in temp:
Step 2.4.1: If temp[j] is 0, append 1 to sequence.
Step 2.4.2: If temp[j] is 1, append 0 to sequence.
Step 3: After completing the iterations, return the final sequence.
FileName: ThueMorseSequenceIterative.java
public class ThueMorseSequenceIterative { public static String generateThueMorse(int n) { // Start with the initial sequence "0" StringBuilder sequence = new StringBuilder("0"); // Iteratively build the sequence for (int i = 1; i < n; i++) { // Create a temporary copy of the current sequence StringBuilder temp = new StringBuilder(sequence); // Append the bitwise negation of the current sequence for (int j = 0; j < temp.length(); j++) { sequence.append(temp.charAt(j) == '0' ? '1' : '0'); } } return sequence.toString(); } public static void main (String[] args) { int n = 3; // Number of iterations String thueMorseSequence = generateThueMorse(n); // Print the generated sequence System.out.println(thueMorseSequence); } }
Output
0110
Time Complexity: The time complexity of an algorithm is O(n log n), where n is the number of iterations. This is because the sequence is generated iteratively by appending the bitwise negation of the current sequence.
Space Complexity: The space complexity of an algorithm is O(n). The space is required to store the sequence with the number of iterations.
Approach 2: Using Recursive Approach
The recursive approach to generating the Thue-Morse sequence builds the sequence by recursively appending the bitwise negation of the current sequence. Starting with the initial sequence "0", the function calls itself, reducing the number of iterations by one until the base case of zero iterations is reached.
Algorithm
Step 1: If the number of iterations is zero, return the current sequence.
Step 2: Create a temporary copy of the current sequence.
Step 3: For each character in the temporary sequence:
Step 3.1: Append 1 if the character is 0.
Step 3.2: Append 0 if the character is 1.
Step 4: Call the function recursively with the updated sequence and reduced number of iterations.
Step 5: The final sequence is returned once all recursive calls are complete.
FileName: ThueMorseSequenceRecursive.java
public class ThueMorseSequenceRecursive { public static String generateThueMorseRecursive(String sequence, int iterations) { // Base case: if no iterations are left, return the current sequence if (iterations == 0) { return sequence; } // Create a temporary copy of the current sequence StringBuilder temp = new StringBuilder(sequence); // Append the bitwise negation of the current sequence for (int j = 0; j < temp.length(); j++) { sequence += temp.charAt(j) == '0' ? '1' : '0'; } // Recursive call with the updated sequence and decreased iterations return generateThueMorseRecursive(sequence, iterations - 1); } public static void main(String[] args) { int n = 3; // Number of iterations String thueMorseSequence = generateThueMorseRecursive("0", n - 1); // Print the generated sequence System.out.println(thueMorseSequence); } }
Output
0110
Time Complexity: The time complexity of an algorithm is O(n log n), where n is the number of iterations. This is because the sequence is constructed using a recursive approach that divides the problem into smaller subproblems.
Space Complexity: The space complexity of an algorithm is O(n). The space is required to store the sequence with the number of iterations.