Generating all sub-sequence of an array of limited size
In this article, we will discuss how to generate all sub-sequences of an array with a limited size. A sub-sequence of an array is a sequence of elements taken from the original array, preserving their relative order.
Problem Statement
Given an array of integers and a limit on the size of sub-sequences, we want to generate all possible sub-sequences that satisfy the given limit.
Example
Let's consider the following examples to understand the problem better:
Example 1:
Input: [1, 2, 3, 6] Limit: 3 Output: 1 2 1 2 3 1 3 2 3 1 2 3 6 1 6 2 6 1 2 6 3 6 1 3 6 2 3 6 1 2 3 6
Example 2:
Input: [7, 8, 1, 6, 4] Limit: 4 Output: 7 8 7 8 1 7 1 8 1 7 8 1 6 7 6 8 6 7 8 6 1 6 7 1 6 8 1 6 7 8 1 6 4 7 4 8 4 7 8 4 1 4 7 1 4 8 1 4 7 8 1 4 6 4 7 6 4 8 6 4 7 8 6 4 1 6 4 7 1 6 4 8 1 6 4 7 8 1 6 4
Algorithm
To generate all sub-sequences of an array, we can use a binary counting technique. The idea is to use a binary representation of numbers from 1 to 2^n - 1, where n is the size of the array.
The steps of the algorithm are as follows:
- Create an empty list to store each sub-sequence.
- Iterate from 1 to 2^n - 1.
- For each number, iterate over the array elements.
- If the bit at the corresponding index is set, add the element to the sub-sequence list.
- Print the sub-sequence list.
- Clear the sub-sequence list for the next iteration.
Pseudocode
function printSubArray(record):
for i = 0 to record.length - 1:
print record[i]
end for
end function
function findSubArray(arr, n):
record = empty list
for i = 1 to (1 << n) - 1:
for j = 0 to n - 1:
if (i & (1 << j)) > 0:
record.add(arr[j])
end if
end for
printSubArray(record)
clear record
end for
end function
function main():
arr1 = [1, 2, 3, 6]
arr2 = [7, 8, 1, 6, 4]
n = length of arr1
findSubArray(arr1, n)
n = length of arr2
findSubArray(arr2, n)
end function
main()
Explanation
The algorithm uses nested loops to generate all possible sub-sequences. The outer loop iterates from 1 to 2^n - 1, where n is the size of the array. This loop generates all possible binary representations from 1 to 2^n - 1.
The inner loop iterates over the array elements. It checks if the corresponding bit is set in the binary representation of the outer loop's counter. If the bit is set, the element at that index is added to the sub-sequence list.
After adding the elements to the sub-sequence list, it is printed, and then the list is cleared for the next iteration.
Code Solution
// Java program for
// Generating all sub-sequence of an array of limited size
import java.util.ArrayList;
public class SubSequence
{
public void printSubArray(ArrayList < Integer > record)
{
// Print record elements
for (int i = 0; i < record.size(); i++)
{
System.out.print(" " + record.get(i));
}
}
public void findSubArray(int []arr, int n)
{
// Use to collect information of sub-sequence
ArrayList < Integer > record = new ArrayList < Integer > ();
for (int i = 1; i < (1 << n); i++)
{
// This loop are generating all sub-sequence
for (int j = 0; j < n; j++)
{
if ((i & (1 << j)) > 0)
{
// Add sub-sequence element
record.add(arr[j]);
}
}
// Display sub array element
printSubArray(record);
// Add new line
System.out.print("\n");
// Remove all record element
record.clear();
}
System.out.print("\n");
}
public static void main(String[] args)
{
SubSequence task = new SubSequence();
int []arr1 =
{
1 , 2 , 3 , 6
};
int []arr2 =
{
7 , 8 , 1 , 6, 4
};
// Test Case A
int n = arr1.length;
task.findSubArray(arr1, n);
// Test Case B
n = arr2.length;
task.findSubArray(arr2, n);
}
}
input
1
2
1 2
3
1 3
2 3
1 2 3
6
1 6
2 6
1 2 6
3 6
1 3 6
2 3 6
1 2 3 6
7
8
7 8
1
7 1
8 1
7 8 1
6
7 6
8 6
7 8 6
1 6
7 1 6
8 1 6
7 8 1 6
4
7 4
8 4
7 8 4
1 4
7 1 4
8 1 4
7 8 1 4
6 4
7 6 4
8 6 4
7 8 6 4
1 6 4
7 1 6 4
8 1 6 4
7 8 1 6 4
// Include header file
#include <iostream>
#include <vector>
using namespace std;
// C++ program for
// Generating all sub-sequence of an array of limited size
class SubSequence
{
public: void printSubArray(vector < int > record)
{
// Print record elements
for (int i = 0; i < record.size(); i++)
{
cout << " " << record.at(i);
}
}
void findSubArray(int arr[], int n)
{
// Use to collect information of sub-sequence
vector < int > record ;
for (int i = 1; i < (1 << n); i++)
{
// This loop are generating all sub-sequence
for (int j = 0; j < n; j++)
{
if ((i &(1 << j)) > 0)
{
// Add sub-sequence element
record.push_back(arr[j]);
}
}
// Display sub array element
this->printSubArray(record);
// Add new line
cout << "\n";
// Remove all record element
record.clear();
}
cout << "\n";
}
};
int main()
{
SubSequence *task = new SubSequence();
int arr1[] = {
1 , 2 , 3 , 6
};
int arr2[] = {
7 , 8 , 1 , 6 , 4
};
// Test Case A
int n = sizeof(arr1) / sizeof(arr1[0]);
task->findSubArray(arr1, n);
// Test Case B
n = sizeof(arr2) / sizeof(arr2[0]);
task->findSubArray(arr2, n);
return 0;
}
input
1
2
1 2
3
1 3
2 3
1 2 3
6
1 6
2 6
1 2 6
3 6
1 3 6
2 3 6
1 2 3 6
7
8
7 8
1
7 1
8 1
7 8 1
6
7 6
8 6
7 8 6
1 6
7 1 6
8 1 6
7 8 1 6
4
7 4
8 4
7 8 4
1 4
7 1 4
8 1 4
7 8 1 4
6 4
7 6 4
8 6 4
7 8 6 4
1 6 4
7 1 6 4
8 1 6 4
7 8 1 6 4
// Include namespace system
using System;
using System.Collections.Generic;
// Csharp program for
// Generating all sub-sequence of an array of limited size
public class SubSequence
{
public void printSubArray(List < int > record)
{
// Print record elements
for (int i = 0; i < record.Count; i++)
{
Console.Write(" " + record[i]);
}
}
public void findSubArray(int[] arr, int n)
{
// Use to collect information of sub-sequence
List < int > record = new List < int > ();
for (int i = 1; i < (1 << n); i++)
{
// This loop are generating all sub-sequence
for (int j = 0; j < n; j++)
{
if ((i & (1 << j)) > 0)
{
// Add sub-sequence element
record.Add(arr[j]);
}
}
// Display sub array element
this.printSubArray(record);
// Add new line
Console.Write("\n");
// Remove all record element
record.Clear();
}
Console.Write("\n");
}
public static void Main(String[] args)
{
SubSequence task = new SubSequence();
int[] arr1 = {
1 , 2 , 3 , 6
};
int[] arr2 = {
7 , 8 , 1 , 6 , 4
};
// Test Case A
int n = arr1.Length;
task.findSubArray(arr1, n);
// Test Case B
n = arr2.Length;
task.findSubArray(arr2, n);
}
}
input
1
2
1 2
3
1 3
2 3
1 2 3
6
1 6
2 6
1 2 6
3 6
1 3 6
2 3 6
1 2 3 6
7
8
7 8
1
7 1
8 1
7 8 1
6
7 6
8 6
7 8 6
1 6
7 1 6
8 1 6
7 8 1 6
4
7 4
8 4
7 8 4
1 4
7 1 4
8 1 4
7 8 1 4
6 4
7 6 4
8 6 4
7 8 6 4
1 6 4
7 1 6 4
8 1 6 4
7 8 1 6 4
<?php
// Php program for
// Generating all sub-sequence of an array of limited size
class SubSequence
{
public function printSubArray($record)
{
// Print record elements
for ($i = 0; $i < count($record); $i++)
{
echo(" ".$record[$i]);
}
}
public function findSubArray($arr, $n)
{
// Use to collect information of sub-sequence
$record = array();
for ($i = 1; $i < (1 << $n); $i++)
{
// This loop are generating all sub-sequence
for ($j = 0; $j < $n; $j++)
{
if (($i & (1 << $j)) > 0)
{
// Add sub-sequence element
$record[] = $arr[$j];
}
}
// Display sub array element
$this->printSubArray($record);
// Add new line
echo("\n");
// Remove all record element
$record = array();
}
echo("\n");
}
}
function main()
{
$task = new SubSequence();
$arr1 = array(1, 2, 3, 6);
$arr2 = array(7, 8, 1, 6, 4);
// Test Case A
$n = count($arr1);
$task->findSubArray($arr1, $n);
// Test Case B
$n = count($arr2);
$task->findSubArray($arr2, $n);
}
main();
input
1
2
1 2
3
1 3
2 3
1 2 3
6
1 6
2 6
1 2 6
3 6
1 3 6
2 3 6
1 2 3 6
7
8
7 8
1
7 1
8 1
7 8 1
6
7 6
8 6
7 8 6
1 6
7 1 6
8 1 6
7 8 1 6
4
7 4
8 4
7 8 4
1 4
7 1 4
8 1 4
7 8 1 4
6 4
7 6 4
8 6 4
7 8 6 4
1 6 4
7 1 6 4
8 1 6 4
7 8 1 6 4
// Node JS program for
// Generating all sub-sequence of an array of limited size
class SubSequence
{
printSubArray(record)
{
// Print record elements
for (var i = 0; i < record.length; i++)
{
process.stdout.write(" " + record[i]);
}
}
findSubArray(arr, n)
{
// Use to collect information of sub-sequence
var record = [];
for (var i = 1; i < (1 << n); i++)
{
// This loop are generating all sub-sequence
for (var j = 0; j < n; j++)
{
if ((i & (1 << j)) > 0)
{
// Add sub-sequence element
record.push(arr[j]);
}
}
// Display sub array element
this.printSubArray(record);
// Add new line
process.stdout.write("\n");
// Remove all record element
record = [];
}
process.stdout.write("\n");
}
}
function main()
{
var task = new SubSequence();
var arr1 = [1, 2, 3, 6];
var arr2 = [7, 8, 1, 6, 4];
// Test Case A
var n = arr1.length;
task.findSubArray(arr1, n);
// Test Case B
n = arr2.length;
task.findSubArray(arr2, n);
}
main();
input
1
2
1 2
3
1 3
2 3
1 2 3
6
1 6
2 6
1 2 6
3 6
1 3 6
2 3 6
1 2 3 6
7
8
7 8
1
7 1
8 1
7 8 1
6
7 6
8 6
7 8 6
1 6
7 1 6
8 1 6
7 8 1 6
4
7 4
8 4
7 8 4
1 4
7 1 4
8 1 4
7 8 1 4
6 4
7 6 4
8 6 4
7 8 6 4
1 6 4
7 1 6 4
8 1 6 4
7 8 1 6 4
# Python 3 program for
# Generating all sub-sequence of an array of limited size
class SubSequence :
def printSubArray(self, record) :
# Print record elements
i = 0
while (i < len(record)) :
print(" ", record[i], end = "")
i += 1
def findSubArray(self, arr, n) :
# Use to collect information of sublist
record = []
i = 1
while (i < (1 << n)) :
j = 0
# This loop are generating all sublists
while (j < n) :
if ((i & (1 << j)) > 0) :
# Add sublist element
record.append(arr[j])
j += 1
# Display sub list element
self.printSubArray(record)
# Add new line
print(end = "\n")
# Remove all record element
record.clear()
i += 1
print(end = "\n")
def main() :
task = SubSequence()
arr1 = [1, 2, 3, 6]
arr2 = [7, 8, 1, 6, 4]
# Test Case A
n = len(arr1)
task.findSubArray(arr1, n)
# Test Case B
n = len(arr2)
task.findSubArray(arr2, n)
if __name__ == "__main__": main()
input
1
2
1 2
3
1 3
2 3
1 2 3
6
1 6
2 6
1 2 6
3 6
1 3 6
2 3 6
1 2 3 6
7
8
7 8
1
7 1
8 1
7 8 1
6
7 6
8 6
7 8 6
1 6
7 1 6
8 1 6
7 8 1 6
4
7 4
8 4
7 8 4
1 4
7 1 4
8 1 4
7 8 1 4
6 4
7 6 4
8 6 4
7 8 6 4
1 6 4
7 1 6 4
8 1 6 4
7 8 1 6 4
# Ruby program for
# Generating all sub-sequence of an array of limited size
class SubSequence
def printSubArray(record)
i = 0
# Print record elements
while (i < record.length)
print(" ", record[i])
i += 1
end
end
def findSubArray(arr, n)
# Use to collect information of sub-sequence
record = []
i = 1
while (i < (1 << n))
# This loop are generating all sub-sequence
j = 0
while (j < n)
if ((i & (1 << j)) > 0)
# Add sub-sequence element
record.push(arr[j])
end
j += 1
end
# Display sub array element
self.printSubArray(record)
# Add new line
print("\n")
# Remove all record element
record.clear()
i += 1
end
print("\n")
end
end
def main()
task = SubSequence.new()
arr1 = [1, 2, 3, 6]
arr2 = [7, 8, 1, 6, 4]
# Test Case A
n = arr1.length
task.findSubArray(arr1, n)
# Test Case B
n = arr2.length
task.findSubArray(arr2, n)
end
main()
input
1
2
1 2
3
1 3
2 3
1 2 3
6
1 6
2 6
1 2 6
3 6
1 3 6
2 3 6
1 2 3 6
7
8
7 8
1
7 1
8 1
7 8 1
6
7 6
8 6
7 8 6
1 6
7 1 6
8 1 6
7 8 1 6
4
7 4
8 4
7 8 4
1 4
7 1 4
8 1 4
7 8 1 4
6 4
7 6 4
8 6 4
7 8 6 4
1 6 4
7 1 6 4
8 1 6 4
7 8 1 6 4
import scala.collection.mutable._;
// Scala program for
// Generating all sub-sequence of an array of limited size
class SubSequence()
{
def printSubArray(record: ArrayBuffer[Int]): Unit = {
var i: Int = 0;
// Print record elements
while (i < record.size)
{
print(" " + record(i));
i += 1;
}
}
def findSubArray(arr: Array[Int], n: Int): Unit = {
// Use to collect information of sub-sequence
var record: ArrayBuffer[Int] = new ArrayBuffer[Int]();
var i: Int = 1;
while (i < (1 << n))
{
var j: Int = 0;
// This loop are generating all sub-sequence
while (j < n)
{
if ((i & (1 << j)) > 0)
{
// Add sub-sequence element
record += arr(j);
}
j += 1;
}
// Display sub array element
printSubArray(record);
// Add new line
print("\n");
// Remove all record element
record.clear();
i += 1;
}
print("\n");
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: SubSequence = new SubSequence();
var arr1: Array[Int] = Array(1, 2, 3, 6);
var arr2: Array[Int] = Array(7, 8, 1, 6, 4);
// Test Case A
var n: Int = arr1.length;
task.findSubArray(arr1, n);
// Test Case B
n = arr2.length;
task.findSubArray(arr2, n);
}
}
input
1
2
1 2
3
1 3
2 3
1 2 3
6
1 6
2 6
1 2 6
3 6
1 3 6
2 3 6
1 2 3 6
7
8
7 8
1
7 1
8 1
7 8 1
6
7 6
8 6
7 8 6
1 6
7 1 6
8 1 6
7 8 1 6
4
7 4
8 4
7 8 4
1 4
7 1 4
8 1 4
7 8 1 4
6 4
7 6 4
8 6 4
7 8 6 4
1 6 4
7 1 6 4
8 1 6 4
7 8 1 6 4
import Foundation;
// Swift 4 program for
// Generating all sub-sequence of an array of limited size
class SubSequence
{
func printSubArray(_ record: [Int])
{
// Print record elements
var i = 0;
while (i < record.count)
{
print(" ", record[i], terminator: "");
i += 1;
}
}
func findSubArray(_ arr: [Int], _ n: Int)
{
// Use to collect information of sub-sequence
var record = [Int]();
var i = 1;
while (i < (1 << n))
{
var j = 0;
// This loop are generating all sub-sequence
while (j < n)
{
if ((i & (1 << j)) > 0)
{
// Add sub-sequence element
record.append(arr[j]);
}
j += 1;
}
// Display sub array element
self.printSubArray(record);
// Add new line
print(terminator: "\n");
// Remove all record element
record.removeAll();
i += 1;
}
print(terminator: "\n");
}
}
func main()
{
let task = SubSequence();
let arr1 = [1, 2, 3, 6];
let arr2 = [7, 8, 1, 6, 4];
// Test Case A
var n = arr1.count;
task.findSubArray(arr1, n);
// Test Case B
n = arr2.count;
task.findSubArray(arr2, n);
}
main();
input
1
2
1 2
3
1 3
2 3
1 2 3
6
1 6
2 6
1 2 6
3 6
1 3 6
2 3 6
1 2 3 6
7
8
7 8
1
7 1
8 1
7 8 1
6
7 6
8 6
7 8 6
1 6
7 1 6
8 1 6
7 8 1 6
4
7 4
8 4
7 8 4
1 4
7 1 4
8 1 4
7 8 1 4
6 4
7 6 4
8 6 4
7 8 6 4
1 6 4
7 1 6 4
8 1 6 4
7 8 1 6 4
// Kotlin program for
// Generating all sub-sequence of an array of limited size
class SubSequence
{
fun printSubArray(record: MutableList < Int > ): Unit
{
// Print record elements
var i: Int = 0;
while (i < record.size)
{
print(" " + record[i]);
i += 1;
}
}
fun findSubArray(arr: Array < Int > , n: Int): Unit
{
// Use to collect information of sub-sequence
val record: MutableList < Int > = mutableListOf < Int > ();
var i: Int = 1;
while (i < (1 shl n))
{
// This loop are generating all sub-sequence
var j: Int = 0;
while (j < n)
{
if ((i and (1 shl j)) > 0)
{
// Add sub-sequence element
record.add(arr[j]);
}
j += 1;
}
// Display sub array element
this.printSubArray(record);
// Add new line
print("\n");
// Remove all record element
record.clear();
i += 1;
}
print("\n");
}
}
fun main(args: Array < String > ): Unit
{
val task: SubSequence = SubSequence();
val arr1: Array < Int > = arrayOf(1, 2, 3, 6);
val arr2: Array < Int > = arrayOf(7, 8, 1, 6, 4);
// Test Case A
var n: Int = arr1.count();
task.findSubArray(arr1, n);
// Test Case B
n = arr2.count();
task.findSubArray(arr2, n);
}
input
1
2
1 2
3
1 3
2 3
1 2 3
6
1 6
2 6
1 2 6
3 6
1 3 6
2 3 6
1 2 3 6
7
8
7 8
1
7 1
8 1
7 8 1
6
7 6
8 6
7 8 6
1 6
7 1 6
8 1 6
7 8 1 6
4
7 4
8 4
7 8 4
1 4
7 1 4
8 1 4
7 8 1 4
6 4
7 6 4
8 6 4
7 8 6 4
1 6 4
7 1 6 4
8 1 6 4
7 8 1 6 4
Output Explanation
For example 1, the input array is [1, 2, 3, 6] with a limit of 3. The algorithm generates all sub-sequences of length 1, 2, and 3. The output shows all the generated sub-sequences.
Similarly, for example 2, the input array is [7, 8, 1, 6, 4] with a limit of 4. The algorithm generates all sub-sequences of length 1, 2, 3, and 4. The output displays all the generated sub-sequences.
Time Complexity
The time complexity of this algorithm is O(2^n * n), where n is the size of the input array. The outer loop runs 2^n - 1 times, and the inner loop iterates over n elements. Hence, the overall time complexity is exponential but bounded by the size of the input array.
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