Posted on by Kalkicode
Code Mathematics

# 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:

1. Create an empty list to store each sub-sequence.
2. Iterate from 1 to 2^n - 1.
3. For each number, iterate over the array elements.
4. If the bit at the corresponding index is set, add the element to the sub-sequence list.
5. Print the sub-sequence list.
6. 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:
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)
{
}
}
// Display sub array element
printSubArray(record);

System.out.print("\n");

// Remove all record element
record.clear();
}
System.out.print("\n");
}
public static void main(String[] args)
{

int []arr1 =
{
1 , 2 , 3 , 6
};
int []arr2 =
{
7 , 8 , 1 , 6, 4
};

// Test Case A
int n = arr1.length;

// Test Case B
n = arr2.length;
}
}``````

#### 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)
{
record.push_back(arr[j]);
}
}
// Display sub array element
this->printSubArray(record);
cout << "\n";
// Remove all record element
record.clear();
}
cout << "\n";
}
};
int main()
{
int arr1[] = {
1 , 2 , 3 , 6
};
int arr2[] = {
7 , 8 , 1 , 6 , 4
};
// Test Case A
int n = sizeof(arr1) / sizeof(arr1[0]);
// Test Case B
n = sizeof(arr2) / sizeof(arr2[0]);
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)
{
}
}
// Display sub array element
this.printSubArray(record);
Console.Write("\n");
// Remove all record element
record.Clear();
}
Console.Write("\n");
}
public static void Main(String[] args)
{
int[] arr1 = {
1 , 2 , 3 , 6
};
int[] arr2 = {
7 , 8 , 1 , 6 , 4
};
// Test Case A
int n = arr1.Length;
// Test Case B
n = arr2.Length;
}
}``````

#### 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)
{
\$record[] = \$arr[\$j];
}
}
// Display sub array element
\$this->printSubArray(\$record);
echo("\n");
// Remove all record element
\$record = array();
}
echo("\n");
}
}

function main()
{
\$arr1 = array(1, 2, 3, 6);
\$arr2 = array(7, 8, 1, 6, 4);
// Test Case A
\$n = count(\$arr1);
// Test Case B
\$n = count(\$arr2);
}
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)
{
record.push(arr[j]);
}
}
// Display sub array element
this.printSubArray(record);
process.stdout.write("\n");
// Remove all record element
record = [];
}
process.stdout.write("\n");
}
}

function main()
{
var arr1 = [1, 2, 3, 6];
var arr2 = [7, 8, 1, 6, 4];
// Test Case A
var n = arr1.length;
// Test Case B
n = arr2.length;
}
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) :
record.append(arr[j])

j += 1

#  Display sub list element
self.printSubArray(record)
print(end = "\n")
#  Remove all record element
record.clear()
i += 1

print(end = "\n")

def main() :
arr1 = [1, 2, 3, 6]
arr2 = [7, 8, 1, 6, 4]
#  Test Case A
n = len(arr1)
#  Test Case B
n = len(arr2)

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)
record.push(arr[j])
end

j += 1
end

#  Display sub array element
self.printSubArray(record)
print("\n")
#  Remove all record element
record.clear()
i += 1
end

print("\n")
end

end

def main()
arr1 = [1, 2, 3, 6]
arr2 = [7, 8, 1, 6, 4]
#  Test Case A
n = arr1.length
#  Test Case B
n = arr2.length
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)
{
record += arr(j);
}
j += 1;
}
// Display sub array element
printSubArray(record);
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;
// Test Case B
n = arr2.length;
}
}``````

#### 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)
{
record.append(arr[j]);
}
j += 1;
}
// Display sub array element
self.printSubArray(record);
print(terminator: "\n");
// Remove all record element
record.removeAll();
i += 1;
}
print(terminator: "\n");
}
}
func main()
{
let arr1 = [1, 2, 3, 6];
let arr2 = [7, 8, 1, 6, 4];
// Test Case A
var n = arr1.count;
// Test Case B
n = arr2.count;
}
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)
{
}
j += 1;
}
// Display sub array element
this.printSubArray(record);
print("\n");
// Remove all record element
record.clear();
i += 1;
}
print("\n");
}
}
fun main(args: Array < String > ): Unit
{
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();
// Test Case B
n = arr2.count();
}``````

#### 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.

## 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.

Categories
Relative Post