Golomb sequence using dynamic programming
The Golomb sequence is a non-decreasing sequence of positive integers where each element represents the number of times that a specific integer appears in the sequence. This sequence is named after Solomon W. Golomb, an American mathematician. The sequence starts with the numbers 1, 2, 2, 3, 3, 4, 4, and so on.
Problem Statement
The task is to generate the Golomb sequence up to a given number 'n' using dynamic programming. The input is an integer 'n', and the output is the Golomb sequence up to the 'n'th term.
Pseudocode Algorithm with Explanation
Let's break down the code and understand the steps involved in generating the Golomb sequence using dynamic programming:
1. golombSequence(n):
- Check if 'n' is less than or equal to 0. If true, return.
- Create an array 'dp' of size 'n + 1' to store the Golomb sequence.
- Initialize the first two elements of 'dp' as dp[0] = 0 and dp[1] = 1.
- Print the size of the sequence (value of 'n').
- Print the first element of the sequence (dp[1]).
- Use a loop starting from 2 up to 'n':
- Calculate the Golomb sequence using the formula:
dp[i] = dp[i - dp[dp[i - 1]]] + 1
- Print each element of the sequence (dp[i]).
2. main():
- Call the function golombSequence with different test inputs.
The algorithm utilizes dynamic programming to calculate each element of the Golomb sequence efficiently. It stores the previously calculated elements in the 'dp' array to avoid redundant calculations.
Code Solution
// C Program
// Golomb sequence using dynamic programming
#include <stdio.h>
void golombSequence(int n)
{
if (n <= 0)
{
return;
}
int dp[n + 1];
// Set initial value
dp[0] = 0;
dp[1] = 1;
printf("\n Size : %d", n);
// First sequence
printf("\n %d", dp[1]);
// Display other sequence
for (int i = 2; i <= n; ++i)
{
// Calculate golomb sequence
dp[i] = dp[i - dp[dp[i - 1]]] + 1;
printf(" %d", dp[i]);
}
}
int main()
{
// Test
golombSequence(15);
golombSequence(25);
return 0;
}
Output
Size : 15
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6
Size : 25
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8 9 9
// Java program for
// Golomb sequence using dynamic programming
public class Sequence
{
public void golombSequence(int n)
{
if (n <= 0)
{
return;
}
int[] dp = new int[n + 1];
// Set initial value
dp[0] = 0;
dp[1] = 1;
System.out.print("\n Size : " + n);
// First sequence
System.out.print("\n " + dp[1]);
// Display other sequence
for (int i = 2; i <= n; ++i)
{
// Calculate golomb sequence
dp[i] = dp[i - dp[dp[i - 1]]] + 1;
// Display value
System.out.print(" " + dp[i]);
}
}
public static void main(String[] args)
{
Sequence task = new Sequence();
// Test
task.golombSequence(15);
task.golombSequence(25);
}
}
Output
Size : 15
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6
Size : 25
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8 9 9
// Include header file
#include <iostream>
using namespace std;
// C++ program for
// Golomb sequence using dynamic programming
class Sequence
{
public: void golombSequence(int n)
{
if (n <= 0)
{
return;
}
int dp[n + 1];
// Set initial value
dp[0] = 0;
dp[1] = 1;
cout << "\n Size : " << n;
// First sequence
cout << "\n " << dp[1];
// Display other sequence
for (int i = 2; i <= n; ++i)
{
// Calculate golomb sequence
dp[i] = dp[i - dp[dp[i - 1]]] + 1;
// Display value
cout << " " << dp[i];
}
}
};
int main()
{
Sequence *task = new Sequence();
// Test
task->golombSequence(15);
task->golombSequence(25);
return 0;
}
Output
Size : 15
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6
Size : 25
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8 9 9
// Include namespace system
using System;
// Csharp program for
// Golomb sequence using dynamic programming
public class Sequence
{
public void golombSequence(int n)
{
if (n <= 0)
{
return;
}
int[] dp = new int[n + 1];
// Set initial value
dp[0] = 0;
dp[1] = 1;
Console.Write("\n Size : " + n);
// First sequence
Console.Write("\n " + dp[1]);
// Display other sequence
for (int i = 2; i <= n; ++i)
{
// Calculate golomb sequence
dp[i] = dp[i - dp[dp[i - 1]]] + 1;
// Display value
Console.Write(" " + dp[i]);
}
}
public static void Main(String[] args)
{
Sequence task = new Sequence();
// Test
task.golombSequence(15);
task.golombSequence(25);
}
}
Output
Size : 15
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6
Size : 25
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8 9 9
package main
import "fmt"
// Go program for
// Golomb sequence using dynamic programming
func golombSequence(n int) {
if n <= 0 {
return
}
var dp = make([] int, n + 1)
// Set initial value
dp[0] = 0
dp[1] = 1
fmt.Print("\n Size : ", n)
// First sequence
fmt.Print("\n ", dp[1])
// Display other sequence
for i := 2 ; i <= n ; i++ {
// Calculate golomb sequence
dp[i] = dp[i - dp[dp[i - 1]]] + 1
// Display value
fmt.Print(" ", dp[i])
}
}
func main() {
// Test
golombSequence(15)
golombSequence(25)
}
Output
Size : 15
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6
Size : 25
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8 9 9
<?php
// Php program for
// Golomb sequence using dynamic programming
class Sequence
{
public function golombSequence($n)
{
if ($n <= 0)
{
return;
}
$dp = array_fill(0, $n + 1, 0);
// Set initial value
$dp[0] = 0;
$dp[1] = 1;
echo("\n Size : ".$n);
// First sequence
echo("\n ".$dp[1]);
// Display other sequence
for ($i = 2; $i <= $n; ++$i)
{
// Calculate golomb sequence
$dp[$i] = $dp[$i - $dp[$dp[$i - 1]]] + 1;
// Display value
echo(" ".$dp[$i]);
}
}
}
function main()
{
$task = new Sequence();
// Test
$task->golombSequence(15);
$task->golombSequence(25);
}
main();
Output
Size : 15
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6
Size : 25
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8 9 9
// Node JS program for
// Golomb sequence using dynamic programming
class Sequence
{
golombSequence(n)
{
if (n <= 0)
{
return;
}
var dp = Array(n + 1).fill(0);
// Set initial value
dp[0] = 0;
dp[1] = 1;
process.stdout.write("\n Size : " + n);
// First sequence
process.stdout.write("\n " + dp[1]);
// Display other sequence
for (var i = 2; i <= n; ++i)
{
// Calculate golomb sequence
dp[i] = dp[i - dp[dp[i - 1]]] + 1;
// Display value
process.stdout.write(" " + dp[i]);
}
}
}
function main()
{
var task = new Sequence();
// Test
task.golombSequence(15);
task.golombSequence(25);
}
main();
Output
Size : 15
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6
Size : 25
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8 9 9
# Python 3 program for
# Golomb sequence using dynamic programming
class Sequence :
def golombSequence(self, n) :
if (n <= 0) :
return
dp = [0] * (n + 1)
# Set initial value
dp[0] = 0
dp[1] = 1
print("\n Size : ", n, end = "")
# First sequence
print("\n ", dp[1], end = "")
i = 2
# Display other sequence
while (i <= n) :
# Calculate golomb sequence
dp[i] = dp[i - dp[dp[i - 1]]] + 1
# Display value
print(" ", dp[i], end = "")
i += 1
def main() :
task = Sequence()
# Test
task.golombSequence(15)
task.golombSequence(25)
if __name__ == "__main__": main()
Output
Size : 15
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6
Size : 25
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8 9 9
# Ruby program for
# Golomb sequence using dynamic programming
class Sequence
def golombSequence(n)
if (n <= 0)
return
end
dp = Array.new(n + 1) {0}
# Set initial value
dp[0] = 0
dp[1] = 1
print("\n Size : ", n)
# First sequence
print("\n ", dp[1])
i = 2
# Display other sequence
while (i <= n)
# Calculate golomb sequence
dp[i] = dp[i - dp[dp[i - 1]]] + 1
# Display value
print(" ", dp[i])
i += 1
end
end
end
def main()
task = Sequence.new()
# Test
task.golombSequence(15)
task.golombSequence(25)
end
main()
Output
Size : 15
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6
Size : 25
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8 9 9
// Scala program for
// Golomb sequence using dynamic programming
class Sequence()
{
def golombSequence(n: Int): Unit = {
if (n <= 0)
{
return;
}
var dp: Array[Int] = Array.fill[Int](n + 1)(0);
// Set initial value
dp(0) = 0;
dp(1) = 1;
print("\n Size : " + n);
// First sequence
print("\n " + dp(1));
var i: Int = 2;
// Display other sequence
while (i <= n)
{
// Calculate golomb sequence
dp(i) = dp(i - dp(dp(i - 1))) + 1;
// Display value
print(" " + dp(i));
i += 1;
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Sequence = new Sequence();
// Test
task.golombSequence(15);
task.golombSequence(25);
}
}
Output
Size : 15
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6
Size : 25
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8 9 9
// Swift 4 program for
// Golomb sequence using dynamic programming
class Sequence
{
func golombSequence(_ n: Int)
{
if (n <= 0)
{
return;
}
var dp: [Int] = Array(repeating: 0, count: n + 1);
// Set initial value
dp[0] = 0;
dp[1] = 1;
print("\n Size : ", n, terminator: "");
// First sequence
print("\n ", dp[1], terminator: "");
var i: Int = 2;
// Display other sequence
while (i <= n)
{
// Calculate golomb sequence
dp[i] = dp[i - dp[dp[i - 1]]] + 1;
// Display value
print(" ", dp[i], terminator: "");
i += 1;
}
}
}
func main()
{
let task: Sequence = Sequence();
// Test
task.golombSequence(15);
task.golombSequence(25);
}
main();
Output
Size : 15
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6
Size : 25
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8 9 9
// Kotlin program for
// Golomb sequence using dynamic programming
class Sequence
{
fun golombSequence(n: Int): Unit
{
if (n <= 0)
{
return;
}
val dp: Array < Int > = Array(n + 1)
{
0
};
// Set initial value
dp[0] = 0;
dp[1] = 1;
print("\n Size : " + n);
// First sequence
print("\n " + dp[1]);
var i: Int = 2;
// Display other sequence
while (i <= n)
{
// Calculate golomb sequence
dp[i] = dp[i - dp[dp[i - 1]]] + 1;
// Display value
print(" " + dp[i]);
i += 1;
}
}
}
fun main(args: Array < String > ): Unit
{
val task: Sequence = Sequence();
// Test
task.golombSequence(15);
task.golombSequence(25);
}
Output
Size : 15
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6
Size : 25
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8 9 9
Resultant Output Explanation
Let's analyze the output generated by the provided code for two test inputs, 15 and 25:
For n = 15:
Size: 15
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6
The size of the sequence is 15, and the first element is 1. The following elements represent the Golomb sequence up to the 15th term. Each number indicates the number of times a specific integer appears in the sequence.
For n = 25:
Size: 25
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8 9 9
Similarly, for n = 25, the size of the sequence is 25, and the first element is 1. The subsequent elements represent the Golomb sequence up to the 25th term.
Time Complexity:
The time complexity of the provided code is O(n) since the loop iterates from 2 to n, performing constant-time operations within each iteration.
Finally
We explored the Golomb sequence and implemented it using dynamic programming in C. We discussed the problem statement, provided pseudocode algorithm with explanations, and analyzed the resultant output for two test inputs. The Golomb sequence is an interesting sequence that can be efficiently generated using dynamic programming techniques, enabling us to avoid redundant calculations and improve performance.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment