Posted on by Kalkicode
Code Backtracking

Print all possible strings of length N in a set

The problem at hand is to generate and print all possible strings of a fixed length N using characters from a given set. In this scenario, we are using the characters 'A' and 'B' as the set. The objective is to generate all combinations of these characters of length N and print them.

Problem Statement and Description

Given a set of characters (in this case, 'A' and 'B'), the goal is to generate all possible strings of length N using these characters and print them. For instance, if N is 4 and the set contains only 'A' and 'B', the program should generate all 16 combinations of 'A' and 'B' of length 4 and print them.

AAAA
AAAB
AABA
AABB
ABAA
ABAB
ABBA
ABBB
BAAA
BAAB
BABA
BABB
BBAA
BBAB
BBBA
BBBB

Example

Let's illustrate this with a smaller example where N = 2 and the set contains only 'A' and 'B'.

  • For N = 2, the possible combinations are: "AA", "AB", "BA", "BB".
  • So, the program should output:
AA
AB
BA
BB

Idea to Solve the Problem

To solve this problem, we can use a recursive approach. We'll iterate through each character in the set and append it to the current output string. Then, we'll recursively call the function with a decremented value of N until N becomes 0. At that point, we'll print the generated string.

Pseudocode

function generateStrings(record, output, n, size):
    if n == 0:
        print(output)
        return
    for i in range(size):
        generateStrings(record, output + record[i], n - 1, size)

record = ['A', 'B']
size = length of record
n = desired string length
generateStrings(record, "", n, size)

Algorithm Explanation

  1. Start by defining a function generateStrings that takes parameters: record (the character set), output (the current generated string), n (remaining length to generate), and size (size of the character set).

  2. In the generateStrings function, check if n is 0. If so, it means we have generated a string of desired length. In this case, print the output string and return.

  3. If n is not 0, iterate through each character in the record set.

  4. For each character, recursively call the generateStrings function with updated parameters:

    • Append the current character to the output string.
    • Decrement n by 1.
    • Keep size unchanged.

  5. When all recursive calls return, the program will have generated and printed all possible strings of length N using characters from the given set.

  6. In the main function, define the character set record and get the size of the set (size). Also, specify the desired length of the generated strings (n).

  7. Call the generateStrings function with initial output as an empty string, the desired n, and the size of the character set.

Code Solution

/*
    Java program
    Print all possible strings of length N in a set 
*/
public class Combinations
{
    public void result(char[] record, String output, int n, int size)
    {
        if (n == 0)
        {
            // Display output
            System.out.println(output);
            return;
        }
        for (int i = 0; i < size; ++i)
        {
            // Find result using recursion
            result(record, output + record[i], n - 1, size);
        }
    }
    public static void main(String[] args)
    {
        Combinations task = new Combinations();
        // record element
        char[] record = {
            'A' , 'B'
        };
        // Get number of element in record set
        int size = record.length;
        // Length of generated string
        int n = 4;
        task.result(record, "", n, size);
    }
}

input

AAAA
AAAB
AABA
AABB
ABAA
ABAB
ABBA
ABBB
BAAA
BAAB
BABA
BABB
BBAA
BBAB
BBBA
BBBB
// Include header file
#include <iostream>

using namespace std;
/*
    C++ program
    Print all possible strings of length N in a set 
*/
class Combinations
{
	public: void result(char record[], string output, int n, int size)
	{
		if (n == 0)
		{
			// Display output
			cout << output << endl;
			return;
		}
		for (int i = 0; i < size; ++i)
		{
			// Find result using recursion
			this->result(record, output  +  record[i], n - 1, size);
		}
	}
};
int main()
{
	Combinations *task = new Combinations();
	// record element
	char record[] = {
		'A' , 'B'
	};
	// Get number of element in record set
	int size = sizeof(record) / sizeof(record[0]);
	// Length of generated string
	int n = 4;
	task->result(record, "", n, size);
	return 0;
}

input

AAAA
AAAB
AABA
AABB
ABAA
ABAB
ABBA
ABBB
BAAA
BAAB
BABA
BABB
BBAA
BBAB
BBBA
BBBB
// Include namespace system
using System;
/*
    Csharp program
    Print all possible strings of length N in a set 
*/
public class Combinations
{
	public void result(char[] record, String output, int n, int size)
	{
		if (n == 0)
		{
			// Display output
			Console.WriteLine(output);
			return;
		}
		for (int i = 0; i < size; ++i)
		{
			// Find result using recursion
			this.result(record, output + record[i], n - 1, size);
		}
	}
	public static void Main(String[] args)
	{
		Combinations task = new Combinations();
		// record element
		char[] record = {
			'A' , 'B'
		};
		// Get number of element in record set
		int size = record.Length;
		// Length of generated string
		int n = 4;
		task.result(record, "", n, size);
	}
}

input

AAAA
AAAB
AABA
AABB
ABAA
ABAB
ABBA
ABBB
BAAA
BAAB
BABA
BABB
BBAA
BBAB
BBBA
BBBB
package main
import "fmt"
/*
    Go program
    Print all possible strings of length N in a set 
*/

func result(record[] byte, output string, n int, size int) {
	if n == 0 {
		// Display output
		fmt.Println(output)
		return
	}
	for i := 0 ; i < size ; i++ {
		// Find result using recursion
		result(record, output + string(record[i]), n - 1, size)
	}
}
func main() {
	
	// record element
	var record = [] byte {
		'A',
		'B',
	}
	// Get number of element in record set
	var size int = len(record)
	// Length of generated string
	var n int = 4
	result(record, "", n, size)
}

input

AAAA
AAAB
AABA
AABB
ABAA
ABAB
ABBA
ABBB
BAAA
BAAB
BABA
BABB
BBAA
BBAB
BBBA
BBBB
<?php
/*
    Php program
    Print all possible strings of length N in a set 
*/
class Combinations
{
	public	function result($record, $output, $n, $size)
	{
		if ($n == 0)
		{
			// Display output
			echo($output.
				"\n");
			return;
		}
		for ($i = 0; $i < $size; ++$i)
		{
			// Find result using recursion
			$this->result($record, $output.strval($record[$i]), $n - 1, $size);
		}
	}
}

function main()
{
	$task = new Combinations();
	// record element
	$record = array('A', 'B');
	// Get number of element in record set
	$size = count($record);
	// Length of generated string
	$n = 4;
	$task->result($record, "", $n, $size);
}
main();

input

AAAA
AAAB
AABA
AABB
ABAA
ABAB
ABBA
ABBB
BAAA
BAAB
BABA
BABB
BBAA
BBAB
BBBA
BBBB
/*
    Node JS program
    Print all possible strings of length N in a set 
*/
class Combinations
{
	result(record, output, n, size)
	{
		if (n == 0)
		{
			// Display output
			console.log(output);
			return;
		}
		for (var i = 0; i < size; ++i)
		{
			// Find result using recursion
			this.result(record, output + record[i], n - 1, size);
		}
	}
}

function main()
{
	var task = new Combinations();
	// record element
	var record = ['A', 'B'];
	// Get number of element in record set
	var size = record.length;
	// Length of generated string
	var n = 4;
	task.result(record, "", n, size);
}
main();

input

AAAA
AAAB
AABA
AABB
ABAA
ABAB
ABBA
ABBB
BAAA
BAAB
BABA
BABB
BBAA
BBAB
BBBA
BBBB
#    Python 3 program
#    Print all possible strings of length N in a set 
class Combinations :
	def result(self, record, output, n, size) :
		if (n == 0) :
			#  Display output
			print(output)
			return
		
		i = 0
		while (i < size) :
			#  Find result using recursion
			self.result(record, output + str(record[i]), n - 1, size)
			i += 1

def main() :
	task = Combinations()
	#  record element
	record = ['A', 'B']
	#  Get number of element in record set
	size = len(record)
	#  Length of generated string
	n = 4
	task.result(record, "", n, size)

if __name__ == "__main__": main()

input

AAAA
AAAB
AABA
AABB
ABAA
ABAB
ABBA
ABBB
BAAA
BAAB
BABA
BABB
BBAA
BBAB
BBBA
BBBB
#    Ruby program
#    Print all possible strings of length N in a set 
class Combinations 
	def result(record, output, n, size) 
		if (n == 0) 
			#  Display output
			print(output, "\n")
			return
		end

		i = 0
		while (i < size) 
			#  Find result using recursion
			self.result(record, output + record[i].to_s, n - 1, size)
			i += 1
		end

	end

end

def main() 
	task = Combinations.new()
	#  record element
	record = ['A', 'B']
	#  Get number of element in record set
	size = record.length
	#  Length of generated string
	n = 4
	task.result(record, "", n, size)
end

main()

input

AAAA
AAAB
AABA
AABB
ABAA
ABAB
ABBA
ABBB
BAAA
BAAB
BABA
BABB
BBAA
BBAB
BBBA
BBBB

/*
    Scala program
    Print all possible strings of length N in a set 
*/
class Combinations()
{
	def result(record: Array[Char], output: String, n: Int, size: Int): Unit = {
		if (n == 0)
		{
			// Display output
			println(output);
			return;
		}
		var i: Int = 0;
		while (i < size)
		{
			// Find result using recursion
			result(record, output + record(i).toString(), n - 1, size);
			i += 1;
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Combinations = new Combinations();
		// record element
		var record: Array[Char] = Array('A', 'B');
		// Get number of element in record set
		var size: Int = record.length;
		// Length of generated string
		var n: Int = 4;
		task.result(record, "", n, size);
	}
}

input

AAAA
AAAB
AABA
AABB
ABAA
ABAB
ABBA
ABBB
BAAA
BAAB
BABA
BABB
BBAA
BBAB
BBBA
BBBB
import Foundation;
/*
    Swift 4 program
    Print all possible strings of length N in a set 
*/
class Combinations
{
	func result(_ record: [Character], 
  				_ output: String, _ n: Int, _ size: Int)
	{
		if (n == 0)
		{
			// Display output
			print(output);
			return;
		}
		var i: Int = 0;
		while (i < size)
		{
			// Find result using recursion
			self.result(record, output + String(record[i]), n - 1, size);
			i += 1;
		}
	}
}
func main()
{
	let task: Combinations = Combinations();
	// record element
	let record: [Character] = ["A", "B"];
	// Get number of element in record set
	let size: Int = record.count;
	// Length of generated string
	let n: Int = 4;
	task.result(record, "", n, size);
}
main();

input

AAAA
AAAB
AABA
AABB
ABAA
ABAB
ABBA
ABBB
BAAA
BAAB
BABA
BABB
BBAA
BBAB
BBBA
BBBB
/*
    Kotlin program
    Print all possible strings of length N in a set 
*/
class Combinations
{
	fun result(record: Array < Char > , 
                output: String, n: Int, size: Int): Unit
	{
		if (n == 0)
		{
			// Display output
			println(output);
			return;
		}
		var i: Int = 0;
		while (i < size)
		{
			// Find result using recursion
			this.result(record, output + record[i].toString(), n - 1, size);
			i += 1;
		}
	}
}
fun main(args: Array < String > ): Unit
{
	val task: Combinations = Combinations();
	// record element
	val record: Array < Char > = arrayOf('A', 'B');
	// Get number of element in record set
	val size: Int = record.count();
	// Length of generated string
	val n: Int = 4;
	task.result(record, "", n, size);
}

input

AAAA
AAAB
AABA
AABB
ABAA
ABAB
ABBA
ABBB
BAAA
BAAB
BABA
BABB
BBAA
BBAB
BBBA
BBBB

Time Complexity

The time complexity of this algorithm is exponential since each character in the character set is being recursively appended to the output string for each level of recursion. If the character set size is M and the desired string length is N, the time complexity can be approximated as O(M^N), where each character has M possibilities and the recursion goes to a depth of N. Keep in mind that this complexity can grow rapidly as M and N increase.

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





Categories
Relative Post