Posted on by Kalkicode
Code Backtracking

Print all initials sequences of given length

The problem are involves generating all possible sequences of a certain length using the digits from 1 to the given length. These sequences are formed by appending digits one by one, creating a variety of combinations.

Problem Statement

Given a length L, the task is to generate and print all possible sequences of length L using the digits from 1 to L.

Example

For L = 3, the possible sequences are:

  • 111
  • 112
  • 113
  • 121
  • 122
  • 123
  • 131
  • 132
  • 133
  • 211
  • 212
  • 213
  • 221
  • 222
  • 223
  • 231
  • 232
  • 233
  • 311
  • 312
  • 313
  • 321
  • 322
  • 323
  • 331
  • 332
  • 333

Idea to Solve

The problem can be solved using a recursive approach. Starting from an initial number of 0, you can loop through digits from 1 to the given length. At each step, you append the current digit to the number and then recursively call the function to append the next digit.

Pseudocode

function sequence(number, length, n):
    if length == n:
        print number
        return
    for i = 1 to length:
        sequence((number * 10) + i, length, n + 1)

function main():
    length = 3
    sequence(0, length, 0)

main()

Algorithm Explanation

  1. sequence(number, length, n): This function generates and prints all possible sequences of the given length. It takes three parameters:

    • number: The current sequence being formed.
    • length: The desired length of the sequence.
    • n: The current position in the sequence.
  2. If n reaches the desired length, it means a valid sequence has been formed, so the function prints the current sequence.

  3. If n is not yet at the desired length, the function enters a loop from 1 to the given length. It appends the current digit i to the current sequence number and then recursively calls the function with the updated number and n + 1.

Code Solution

// C program
// Print all initials sequences of given length
#include <stdio.h>

// Print the all combinations sequence of given length
void sequence(int number, int length, int n)
{
	if (length == n)
	{
		// Display number
		printf("\n %d", number);
		return;
	}
	// Execute the loop from 1 to length
	for (int i = 1; i <= length; ++i)
	{
		sequence((number *10) + i, length, n + 1);
	}
}
int main()
{
	// Test
	sequence(0, 3, 0);
	return 0;
}

input

 111
 112
 113
 121
 122
 123
 131
 132
 133
 211
 212
 213
 221
 222
 223
 231
 232
 233
 311
 312
 313
 321
 322
 323
 331
 332
 333
/*
  Java Program for
  Print all initials sequences of given length
*/
public class Combination
{
	// Print the all combinations sequence of given length
	public void sequence(int number, int length, int n)
	{
		if (length == n)
		{
			// Display number
			System.out.print("\n " + number);
			return;
		}
		// Execute the loop from 1 to length
		for (int i = 1; i <= length; ++i)
		{
			sequence((number * 10) + i, length, n + 1);
		}
	}
	public static void main(String[] args)
	{
		Combination task = new Combination();
		task.sequence(0, 3,0);
	}
}

input

 111
 112
 113
 121
 122
 123
 131
 132
 133
 211
 212
 213
 221
 222
 223
 231
 232
 233
 311
 312
 313
 321
 322
 323
 331
 332
 333
// Include header file
#include <iostream>

using namespace std;
/*
  C++ Program for
  Print all initials sequences of given length
*/
class Combination
{
	public:
		// Print the all combinations sequence of given length
		void sequence(int number, int length, int n)
		{
			if (length == n)
			{
				// Display number
				cout << "\n " << number;
				return;
			}
			// Execute the loop from 1 to length
			for (int i = 1; i <= length; ++i)
			{
				this->sequence((number *10) + i, length, n + 1);
			}
		}
};
int main()
{
	Combination *task = new Combination();
	task->sequence(0, 3, 0);
	return 0;
}

input

 111
 112
 113
 121
 122
 123
 131
 132
 133
 211
 212
 213
 221
 222
 223
 231
 232
 233
 311
 312
 313
 321
 322
 323
 331
 332
 333
// Include namespace system
using System;
/*
  Csharp Program for
  Print all initials sequences of given length
*/
public class Combination
{
	// Print the all combinations sequence of given length
	public void sequence(int number, int length, int n)
	{
		if (length == n)
		{
			// Display number
			Console.Write("\n " + number);
			return;
		}
		// Execute the loop from 1 to length
		for (int i = 1; i <= length; ++i)
		{
			this.sequence((number * 10) + i, length, n + 1);
		}
	}
	public static void Main(String[] args)
	{
		Combination task = new Combination();
		task.sequence(0, 3, 0);
	}
}

input

 111
 112
 113
 121
 122
 123
 131
 132
 133
 211
 212
 213
 221
 222
 223
 231
 232
 233
 311
 312
 313
 321
 322
 323
 331
 332
 333
<?php
/*
  Php Program for
  Print all initials sequences of given length
*/
class Combination
{
	// Print the all combinations sequence of given length
	public	function sequence($number, $length, $n)
	{
		if ($length == $n)
		{
			// Display number
			echo "\n ".$number;
			return;
		}
		// Execute the loop from 1 to length
		for ($i = 1; $i <= $length; ++$i)
		{
			$this->sequence(($number * 10) + $i, $length, $n + 1);
		}
	}
}

function main()
{
	$task = new Combination();
	$task->sequence(0, 3, 0);
}
main();

input

 111
 112
 113
 121
 122
 123
 131
 132
 133
 211
 212
 213
 221
 222
 223
 231
 232
 233
 311
 312
 313
 321
 322
 323
 331
 332
 333
/*
  Node JS Program for
  Print all initials sequences of given length
*/
class Combination
{
	// Print the all combinations sequence of given length
	sequence(number, length, n)
	{
		if (length == n)
		{
			// Display number
			process.stdout.write("\n " + number);
			return;
		}
		// Execute the loop from 1 to length
		for (var i = 1; i <= length; ++i)
		{
			this.sequence((number * 10) + i, length, n + 1);
		}
	}
}

function main()
{
	var task = new Combination();
	task.sequence(0, 3, 0);
}
main();

input

 111
 112
 113
 121
 122
 123
 131
 132
 133
 211
 212
 213
 221
 222
 223
 231
 232
 233
 311
 312
 313
 321
 322
 323
 331
 332
 333
#  Python 3 Program for
#  Print all initials sequences of given length
class Combination :
	#  Print the all combinations sequence of given length
	def sequence(self, number, length, n) :
		if (length == n) :
			#  Display number
			print("\n ", number, end = "")
			return
		
		i = 1
		#  Execute the loop from 1 to length
		while (i <= length) :
			self.sequence((number * 10) + i, length, n + 1)
			i += 1
		
	

def main() :
	task = Combination()
	task.sequence(0, 3, 0)

if __name__ == "__main__": main()

input

  111
  112
  113
  121
  122
  123
  131
  132
  133
  211
  212
  213
  221
  222
  223
  231
  232
  233
  311
  312
  313
  321
  322
  323
  331
  332
  333
#  Ruby Program for
#  Print all initials sequences of given length
class Combination 
	#  Print the all combinations sequence of given length
	def sequence(number, length, n) 
		if (length == n) 
			#  Display number
			print("\n ", number)
			return
		end

		i = 1
		#  Execute the loop from 1 to length
		while (i <= length) 
			self.sequence((number * 10) + i, length, n + 1)
			i += 1
		end

	end

end

def main() 
	task = Combination.new()
	task.sequence(0, 3, 0)
end

main()

input

 111
 112
 113
 121
 122
 123
 131
 132
 133
 211
 212
 213
 221
 222
 223
 231
 232
 233
 311
 312
 313
 321
 322
 323
 331
 332
 333
/*
  Scala Program for
  Print all initials sequences of given length
*/
class Combination()
{
	// Print the all combinations sequence of given length
	def sequence(number: Int, length: Int, n: Int): Unit = {
		if (length == n)
		{
			// Display number
			print("\n " + number);
			return;
		}
		var i: Int = 1;
		// Execute the loop from 1 to length
		while (i <= length)
		{
			sequence((number * 10) + i, length, n + 1);
			i += 1;
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Combination = new Combination();
		task.sequence(0, 3, 0);
	}
}

input

 111
 112
 113
 121
 122
 123
 131
 132
 133
 211
 212
 213
 221
 222
 223
 231
 232
 233
 311
 312
 313
 321
 322
 323
 331
 332
 333
/*
  Swift 4 Program for
  Print all initials sequences of given length
*/
class Combination
{
	// Print the all combinations sequence of given length
	func sequence(_ number: Int, _ length: Int, _ n: Int)
	{
		if (length == n)
		{
			// Display number
			print("\n ", number, terminator: "");
			return;
		}
		var i: Int = 1;
		// Execute the loop from 1 to length
		while (i <= length)
		{
			self.sequence((number * 10) + i, length, n + 1);
			i += 1;
		}
	}
}
func main()
{
	let task: Combination = Combination();
	task.sequence(0, 3, 0);
}
main();

input

  111
  112
  113
  121
  122
  123
  131
  132
  133
  211
  212
  213
  221
  222
  223
  231
  232
  233
  311
  312
  313
  321
  322
  323
  331
  332
  333
/*
  Kotlin Program for
  Print all initials sequences of given length
*/
class Combination
{
	// Print the all combinations sequence of given length
	fun sequence(number: Int, length: Int, n: Int): Unit
	{
		if (length == n)
		{
			// Display number
			print("\n " + number);
			return;
		}
		var i: Int = 1;
		while (i <= length)
		{
			this.sequence((number * 10) + i, length, n + 1);
			i += 1;
		}
	}
}
fun main(args: Array < String > ): Unit
{
	val task: Combination = Combination();
	task.sequence(0, 3, 0);
}

input

 111
 112
 113
 121
 122
 123
 131
 132
 133
 211
 212
 213
 221
 222
 223
 231
 232
 233
 311
 312
 313
 321
 322
 323
 331
 332
 333

Time Complexity

The time complexity of the algorithm depends on the number of sequences to be generated. In this case, there are L^L possible sequences of length L, where L is the given length.

Comment

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