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
-
Start by defining a function
generateStrings
that takes parameters:record
(the character set),output
(the current generated string),n
(remaining length to generate), andsize
(size of the character set). -
In the
generateStrings
function, check ifn
is 0. If so, it means we have generated a string of desired length. In this case, print theoutput
string and return. -
If
n
is not 0, iterate through each character in therecord
set. -
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.
- Append the current character to the
-
When all recursive calls return, the program will have generated and printed all possible strings of length
N
using characters from the given set. -
In the
main
function, define the character setrecord
and get the size of the set (size
). Also, specify the desired length of the generated strings (n
). -
Call the
generateStrings
function with initialoutput
as an empty string, the desiredn
, 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.
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