Generating all possible subsequences
The problem "Generating all possible subsequences" involves finding and printing all possible subsequences of a given array. A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. The goal is to generate and display all such subsequences of the given array.
Problem Statement
Given an array of integers, we need to generate and print all possible subsequences of the array.
Example
Let's consider the following input array:
[1, 2, 3, 4]
The output will be as follows:
[]
[1]
[2]
[1, 2]
[3]
[1, 3]
[2, 3]
[1, 2, 3]
[4]
[1, 4]
[2, 4]
[1, 2, 4]
[3, 4]
[1, 3, 4]
[2, 3, 4]
[1, 2, 3, 4]
Idea to Solve the Problem
To generate all possible subsequences, we can use a recursive approach along with a stack data structure. The idea is to consider each element in the array and decide whether to include it in the current subsequence or not. For each element, we have two choices: include it in the current subsequence or exclude it.
Algorithm
- Create a stack data structure to hold the elements of the current subsequence.
- Traverse the array from the last element to the first element.
- For each element at index
i
in the array: a. Call the recursive functionall_subsequences
with the array and the indexi-1
. b. Push the element at indexi
into the stack. c. Call the recursive functionall_subsequences
with the array and the indexi-1
. d. Pop the element from the stack. - The base case of the recursion is when the index becomes -1. In this case, print the elements in the stack, which represent one possible subsequence.
- In the main function, call the
all_subsequences
function with the array and its size.
Pseudocode
Function all_subsequences(collection, location):
if location is -1:
Print elements in the stack as a subsequence.
else:
Call all_subsequences(collection, location - 1)
Push collection[location] into the stack
Call all_subsequences(collection, location - 1)
Pop an element from the stack
Code Solution
// C program
// Generating all possible subsequences
#include <stdio.h>
#include <stdlib.h>
struct MyStack
{
int element;
struct MyStack *next;
};
//Add a new element into stack
void push(struct MyStack **top, int data)
{
//Make a new node
struct MyStack *new_node = (struct MyStack *) malloc(sizeof(struct MyStack));
if (new_node != NULL)
{
//Set node values
new_node->element = data;
new_node->next = *top;*top = new_node;
}
else
{
printf("Memory Overflow\n");
}
}
// Remove stack element
void pop(struct MyStack **top)
{
if ( *top != NULL)
{
struct MyStack *temp = *top;*top = temp->next;
free(temp);
temp = NULL;
}
}
// Display given array elements
void display(int collection[], int size)
{
printf("\n Given collection \n ");
for (int i = 0; i < size; ++i)
{
printf(" %d ", collection[i]);
}
}
//Display subsequences
void print_element(struct MyStack *top)
{
struct MyStack *temp = top;
printf(" [");
//Display stack elements
while (temp != NULL)
{
printf(" %d ", temp->element);
//visit to next node
temp = temp->next;
}
printf("]\n");
}
//Recursive finding all elements of subsequences
void all_subsequences(int collection[], struct MyStack **top, int location)
{
if (location == -1)
{
//Print the sub-sequences, with empty sequences
print_element( *top);
}
else
{
all_subsequences(collection, top, location - 1);
// Add a element into stack
push(top, collection[location]);
all_subsequences(collection, top, location - 1);
// Remove a stack element
pop(top);
}
}
// Handles the request to print subsequence element
void subsequences(int collection[], int size)
{
if (size <= 0)
{
return;
}
// Display given collection elements
display(collection, size);
//Create a stack variable
struct MyStack *top = NULL;
printf("\n All subsequences \n");
all_subsequences(collection, &top, size - 1);
}
int main()
{
int arr[] = {
1 , 2 , 3 , 4
};
//Get the size
int size = sizeof(arr) / sizeof(arr[0]);
subsequences(arr, size);
return 0;
}
Output
Given collection
1 2 3 4
All subsequences
[]
[ 1 ]
[ 2 ]
[ 1 2 ]
[ 3 ]
[ 1 3 ]
[ 2 3 ]
[ 1 2 3 ]
[ 4 ]
[ 1 4 ]
[ 2 4 ]
[ 1 2 4 ]
[ 3 4 ]
[ 1 3 4 ]
[ 2 3 4 ]
[ 1 2 3 4 ]
/*
Java program
Print all subsequences of given size
*/
//Stack Node
class Node
{
public int data;
public Node next;
public Node(int data)
{
this.data = data;
this.next = null;
}
}
//Define custom stack and its operation
class MyStack
{
public Node top;
public MyStack()
{
this.top = null;
}
//Add a new element in stack
public void push(int data)
{
//Make a new stack node
Node new_node = new Node(data);
if (new_node != null)
{
new_node.next = this.top;
this.top = new_node;
}
else
{
System.out.print("Memory overflow\n");
}
}
//remove a top element in stack
public void pop()
{
if (this.top != null)
{
this.top = this.top.next;
}
}
//check that whether stack is empty or not
public boolean is_empty()
{
if (this.top != null)
{
return false;
}
else
{
return true;
}
}
//Used to get top element of stack
public int peek()
{
if (this.top != null)
{
return this.top.data;
}
else
{
return 0;
}
}
}
class Subsequence
{
public MyStack stack;
public Subsequence()
{
stack = new MyStack();
}
// Display given array elements
public void display(int[] collection, int size)
{
System.out.print("\n Given collection \n ");
for (int i = 0; i < size; ++i)
{
System.out.print(" " + collection[i] + " ");
}
}
//Display subsequences
public void print_element()
{
Node temp = this.stack.top;
System.out.print(" [");
//Display stack elements
while (temp != null)
{
System.out.print(" " + temp.data + " ");
//visit to next node
temp = temp.next;
}
System.out.print("]\n");
}
//Recursive finding all elements of subsequences
public void all_subsequences(int[] collection, int location)
{
if (location == -1)
{
//Print the sub-sequences, with empty sequences
print_element();
}
else
{
all_subsequences(collection, location - 1);
// Add a element into stack
this.stack.push(collection[location]);
all_subsequences(collection, location - 1);
// Remove a stack element
this.stack.pop();
}
}
// Handles the request to print subsequence element
public void subsequences(int[] collection, int size)
{
if (size <= 0)
{
return;
}
// Display given collection elements
display(collection, size);
System.out.print("\n All subsequences \n");
all_subsequences(collection, size - 1);
}
public static void main(String[] args)
{
Subsequence obj = new Subsequence();
int[] arr = {
1 , 2 , 3 , 4
};
//Get the size
int size = arr.length;
obj.subsequences(arr, size);
}
}
Output
Given collection
1 2 3 4
All subsequences
[]
[ 1 ]
[ 2 ]
[ 1 2 ]
[ 3 ]
[ 1 3 ]
[ 2 3 ]
[ 1 2 3 ]
[ 4 ]
[ 1 4 ]
[ 2 4 ]
[ 1 2 4 ]
[ 3 4 ]
[ 1 3 4 ]
[ 2 3 4 ]
[ 1 2 3 4 ]
//Include header file
#include <iostream>
using namespace std;
/*
C++ program
Print all subsequences of given size
*/
//Stack Node
class Node
{
public:
int data;
Node *next;
Node(int data)
{
this->data = data;
this->next = NULL;
}
};
//Define custom stack and its operation
class MyStack
{
public:
Node *top;
MyStack()
{
this->top = NULL;
}
//Add a new element in stack
void push(int data)
{
//Make a new stack node
Node *new_node = new Node(data);
if (new_node != NULL)
{
new_node->next = this->top;
this->top = new_node;
}
else
{
cout << "Memory overflow\n";
}
}
//remove a top element in stack
void pop()
{
if (this->top != NULL)
{
this->top = this->top->next;
}
}
//check that whether stack is empty or not
bool is_empty()
{
if (this->top != NULL)
{
return false;
}
else
{
return true;
}
}
//Used to get top element of stack
int peek()
{
if (this->top != NULL)
{
return this->top->data;
}
else
{
return 0;
}
}
};
class Subsequence
{
public: MyStack *stack;
Subsequence()
{
this->stack = new MyStack();
}
// Display given array elements
void display(int collection[], int size)
{
cout << "\n Given collection \n ";
for (int i = 0; i < size; ++i)
{
cout << " " << collection[i] << " ";
}
}
//Display subsequences
void print_element()
{
Node *temp = this->stack->top;
cout << " [";
//Display stack elements
while (temp != NULL)
{
cout << " " << temp->data << " ";
//visit to next node
temp = temp->next;
}
cout << "]\n";
}
//Recursive finding all elements of subsequences
void all_subsequences(int collection[], int location)
{
if (location == -1)
{
//Print the sub-sequences, with empty sequences
this->print_element();
}
else
{
this->all_subsequences(collection, location - 1);
// Add a element into stack
this->stack->push(collection[location]);
this->all_subsequences(collection, location - 1);
// Remove a stack element
this->stack->pop();
}
}
// Handles the request to print subsequence element
void subsequences(int collection[], int size)
{
if (size <= 0)
{
return;
}
// Display given collection elements
this->display(collection, size);
cout << "\n All subsequences \n";
this->all_subsequences(collection, size - 1);
}
};
int main()
{
Subsequence obj = Subsequence();
int arr[] = {
1 , 2 , 3 , 4
};
//Get the size
int size = sizeof(arr) / sizeof(arr[0]);
obj.subsequences(arr, size);
return 0;
}
Output
Given collection
1 2 3 4
All subsequences
[]
[ 1 ]
[ 2 ]
[ 1 2 ]
[ 3 ]
[ 1 3 ]
[ 2 3 ]
[ 1 2 3 ]
[ 4 ]
[ 1 4 ]
[ 2 4 ]
[ 1 2 4 ]
[ 3 4 ]
[ 1 3 4 ]
[ 2 3 4 ]
[ 1 2 3 4 ]
//Include namespace system
using System;
/*
C# program
Print all subsequences of given size
*/
//Stack Node
class Node
{
public int data;
public Node next;
public Node(int data)
{
this.data = data;
this.next = null;
}
}
//Define custom stack and its operation
class MyStack
{
public Node top;
public MyStack()
{
this.top = null;
}
//Add a new element in stack
public void push(int data)
{
//Make a new stack node
Node new_node = new Node(data);
if (new_node != null)
{
new_node.next = this.top;
this.top = new_node;
}
else
{
Console.Write("Memory overflow\n");
}
}
//remove a top element in stack
public void pop()
{
if (this.top != null)
{
this.top = this.top.next;
}
}
//check that whether stack is empty or not
public Boolean is_empty()
{
if (this.top != null)
{
return false;
}
else
{
return true;
}
}
//Used to get top element of stack
public int peek()
{
if (this.top != null)
{
return this.top.data;
}
else
{
return 0;
}
}
}
class Subsequence
{
public MyStack stack;
public Subsequence()
{
stack = new MyStack();
}
// Display given array elements
public void display(int[] collection, int size)
{
Console.Write("\n Given collection \n ");
for (int i = 0; i < size; ++i)
{
Console.Write(" " + collection[i] + " ");
}
}
//Display subsequences
public void print_element()
{
Node temp = this.stack.top;
Console.Write(" [");
//Display stack elements
while (temp != null)
{
Console.Write(" " + temp.data + " ");
//visit to next node
temp = temp.next;
}
Console.Write("]\n");
}
//Recursive finding all elements of subsequences
public void all_subsequences(int[] collection, int location)
{
if (location == -1)
{
//Print the sub-sequences, with empty sequences
print_element();
}
else
{
all_subsequences(collection, location - 1);
// Add a element into stack
this.stack.push(collection[location]);
all_subsequences(collection, location - 1);
// Remove a stack element
this.stack.pop();
}
}
// Handles the request to print subsequence element
public void subsequences(int[] collection, int size)
{
if (size <= 0)
{
return;
}
// Display given collection elements
display(collection, size);
Console.Write("\n All subsequences \n");
all_subsequences(collection, size - 1);
}
public static void Main(String[] args)
{
Subsequence obj = new Subsequence();
int[] arr = {
1 , 2 , 3 , 4
};
//Get the size
int size = arr.Length;
obj.subsequences(arr, size);
}
}
Output
Given collection
1 2 3 4
All subsequences
[]
[ 1 ]
[ 2 ]
[ 1 2 ]
[ 3 ]
[ 1 3 ]
[ 2 3 ]
[ 1 2 3 ]
[ 4 ]
[ 1 4 ]
[ 2 4 ]
[ 1 2 4 ]
[ 3 4 ]
[ 1 3 4 ]
[ 2 3 4 ]
[ 1 2 3 4 ]
<?php
/*
Php program
Print all subsequences of given size
*/
//Stack Node
class Node
{
public $data;
public $next;
function __construct($data)
{
$this->data = $data;
$this->next = null;
}
}
//Define custom stack and its operation
class MyStack
{
public $top;
function __construct()
{
$this->top = null;
}
//Add a new element in stack
public function push($data)
{
//Make a new stack node
$new_node = new Node($data);
if ($new_node != null)
{
$new_node->next = $this->top;
$this->top = $new_node;
}
else
{
echo "Memory overflow\n";
}
}
//remove a top element in stack
public function pop()
{
if ($this->top != null)
{
$this->top = $this->top->next;
}
}
//check that whether stack is empty or not
public function is_empty()
{
if ($this->top != null)
{
return false;
}
else
{
return true;
}
}
//Used to get top element of stack
public function peek()
{
if ($this->top != null)
{
return $this->top->data;
}
else
{
return 0;
}
}
}
class Subsequence
{
public $stack;
function __construct()
{
$this->stack = new MyStack();
}
// Display given array elements
public function display( & $collection, $size)
{
echo "\n Given collection \n ";
for ($i = 0; $i < $size; ++$i)
{
echo " ". $collection[$i] ." ";
}
}
//Display subsequences
public function print_element()
{
$temp = $this->stack->top;
echo " [";
//Display stack elements
while ($temp != null)
{
echo " ". $temp->data ." ";
//visit to next node
$temp = $temp->next;
}
echo "]\n";
}
//Recursive finding all elements of subsequences
public function all_subsequences( & $collection, $location)
{
if ($location == -1)
{
//Print the sub-sequences, with empty sequences
$this->print_element();
}
else
{
$this->all_subsequences($collection, $location - 1);
// Add a element into stack
$this->stack->push($collection[$location]);
$this->all_subsequences($collection, $location - 1);
// Remove a stack element
$this->stack->pop();
}
}
// Handles the request to print subsequence element
public function subsequences( & $collection, $size)
{
if ($size <= 0)
{
return;
}
// Display given collection elements
$this->display($collection, $size);
echo "\n All subsequences \n";
$this->all_subsequences($collection, $size - 1);
}
}
function main()
{
$obj = new Subsequence();
$arr = array(1, 2, 3, 4);
//Get the size
$size = count($arr);
$obj->subsequences($arr, $size);
}
main();
Output
Given collection
1 2 3 4
All subsequences
[]
[ 1 ]
[ 2 ]
[ 1 2 ]
[ 3 ]
[ 1 3 ]
[ 2 3 ]
[ 1 2 3 ]
[ 4 ]
[ 1 4 ]
[ 2 4 ]
[ 1 2 4 ]
[ 3 4 ]
[ 1 3 4 ]
[ 2 3 4 ]
[ 1 2 3 4 ]
/*
Node Js program
Print all subsequences of given size
*/
//Stack Node
class Node
{
constructor(data)
{
this.data = data;
this.next = null;
}
}
//Define custom stack and its operation
class MyStack
{
constructor()
{
this.top = null;
}
//Add a new element in stack
push(data)
{
//Make a new stack node
var new_node = new Node(data);
if (new_node != null)
{
new_node.next = this.top;
this.top = new_node;
}
else
{
process.stdout.write("Memory overflow\n");
}
}
//remove a top element in stack
pop()
{
if (this.top != null)
{
this.top = this.top.next;
}
}
//check that whether stack is empty or not
is_empty()
{
if (this.top != null)
{
return false;
}
else
{
return true;
}
}
//Used to get top element of stack
peek()
{
if (this.top != null)
{
return this.top.data;
}
else
{
return 0;
}
}
}
class Subsequence
{
constructor()
{
this.stack = new MyStack();
}
// Display given array elements
display(collection, size)
{
process.stdout.write("\n Given collection \n ");
for (var i = 0; i < size; ++i)
{
process.stdout.write(" " + collection[i] + " ");
}
}
//Display subsequences
print_element()
{
var temp = this.stack.top;
process.stdout.write(" [");
//Display stack elements
while (temp != null)
{
process.stdout.write(" " + temp.data + " ");
//visit to next node
temp = temp.next;
}
process.stdout.write("]\n");
}
//Recursive finding all elements of subsequences
all_subsequences(collection, location)
{
if (location == -1)
{
//Print the sub-sequences, with empty sequences
this.print_element();
}
else
{
this.all_subsequences(collection, location - 1);
// Add a element into stack
this.stack.push(collection[location]);
this.all_subsequences(collection, location - 1);
// Remove a stack element
this.stack.pop();
}
}
// Handles the request to print subsequence element
subsequences(collection, size)
{
if (size <= 0)
{
return;
}
// Display given collection elements
this.display(collection, size);
process.stdout.write("\n All subsequences \n");
this.all_subsequences(collection, size - 1);
}
}
function main()
{
var obj = new Subsequence();
var arr = [1, 2, 3, 4];
//Get the size
var size = arr.length;
obj.subsequences(arr, size);
}
main();
Output
Given collection
1 2 3 4
All subsequences
[]
[ 1 ]
[ 2 ]
[ 1 2 ]
[ 3 ]
[ 1 3 ]
[ 2 3 ]
[ 1 2 3 ]
[ 4 ]
[ 1 4 ]
[ 2 4 ]
[ 1 2 4 ]
[ 3 4 ]
[ 1 3 4 ]
[ 2 3 4 ]
[ 1 2 3 4 ]
# Python 3 program
# Print all subsequences of given size
# Stack Node
class Node :
def __init__(self, data) :
self.data = data
self.next = None
# Define custom stack and its operation
class MyStack :
def __init__(self) :
self.top = None
# Add a new element in stack
def push(self, data) :
# Make a new stack node
new_node = Node(data)
if (new_node != None) :
new_node.next = self.top
self.top = new_node
else :
print("Memory overflow\n", end = "")
# remove a top element in stack
def pop(self) :
if (self.top != None) :
self.top = self.top.next
# check that whether stack is empty or not
def is_empty(self) :
if (self.top != None) :
return False
else :
return True
# Used to get top element of stack
def peek(self) :
if (self.top != None) :
return self.top.data
else :
return 0
class Subsequence :
def __init__(self) :
self.stack = MyStack()
# Display given array elements
def display(self, collection, size) :
print("\n Given collection \n ", end = "")
i = 0
while (i < size) :
print(" ", collection[i] ," ", end = "")
i += 1
# Display subsequences
def print_element(self) :
temp = self.stack.top
print(" [", end = "")
# Display stack elements
while (temp != None) :
print(" ", temp.data ," ", end = "")
# visit to next node
temp = temp.next
print("]\n", end = "")
# Recursive finding all elements of subsequences
def all_subsequences(self, collection, location) :
if (location == -1) :
# Print the sub-sequences, with empty sequences
self.print_element()
else :
self.all_subsequences(collection, location - 1)
# Add a element into stack
self.stack.push(collection[location])
self.all_subsequences(collection, location - 1)
# Remove a stack element
self.stack.pop()
# Handles the request to print subsequence element
def subsequences(self, collection, size) :
if (size <= 0) :
return
# Display given collection elements
self.display(collection, size)
print("\n All subsequences \n", end = "")
self.all_subsequences(collection, size - 1)
def main() :
obj = Subsequence()
arr = [1, 2, 3, 4]
# Get the size
size = len(arr)
obj.subsequences(arr, size)
if __name__ == "__main__": main()
Output
Given collection
1 2 3 4
All subsequences
[]
[ 1 ]
[ 2 ]
[ 1 2 ]
[ 3 ]
[ 1 3 ]
[ 2 3 ]
[ 1 2 3 ]
[ 4 ]
[ 1 4 ]
[ 2 4 ]
[ 1 2 4 ]
[ 3 4 ]
[ 1 3 4 ]
[ 2 3 4 ]
[ 1 2 3 4 ]
# Ruby program
# Print all subsequences of given size
# Stack Node
class Node
# Define the accessor and reader of class Node
attr_reader :data, :next
attr_accessor :data, :next
def initialize(data)
self.data = data
self.next = nil
end
end
# Define custom stack and its operation
class MyStack
# Define the accessor and reader of class MyStack
attr_reader :top
attr_accessor :top
def initialize()
self.top = nil
end
# Add a new element in stack
def push(data)
# Make a new stack node
new_node = Node.new(data)
if (new_node != nil)
new_node.next = self.top
self.top = new_node
else
print("Memory overflow\n")
end
end
# remove a top element in stack
def pop()
if (self.top != nil)
self.top = self.top.next
end
end
# check that whether stack is empty or not
def is_empty()
if (self.top != nil)
return false
else
return true
end
end
# Used to get top element of stack
def peek()
if (self.top != nil)
return self.top.data
else
return 0
end
end
end
class Subsequence
# Define the accessor and reader of class Subsequence
attr_reader :stack
attr_accessor :stack
def initialize()
self.stack = MyStack.new()
end
# Display given array elements
def display(collection, size)
print("\n Given collection \n ")
i = 0
while (i < size)
print(" ", collection[i] ," ")
i += 1
end
end
# Display subsequences
def print_element()
temp = self.stack.top
print(" [")
# Display stack elements
while (temp != nil)
print(" ", temp.data ," ")
# visit to next node
temp = temp.next
end
print("]\n")
end
# Recursive finding all elements of subsequences
def all_subsequences(collection, location)
if (location == -1)
# Print the sub-sequences, with empty sequences
self.print_element()
else
self.all_subsequences(collection, location - 1)
# Add a element into stack
self.stack.push(collection[location])
self.all_subsequences(collection, location - 1)
# Remove a stack element
self.stack.pop()
end
end
# Handles the request to print subsequence element
def subsequences(collection, size)
if (size <= 0)
return
end
# Display given collection elements
self.display(collection, size)
print("\n All subsequences \n")
self.all_subsequences(collection, size - 1)
end
end
def main()
obj = Subsequence.new()
arr = [1, 2, 3, 4]
# Get the size
size = arr.length
obj.subsequences(arr, size)
end
main()
Output
Given collection
1 2 3 4
All subsequences
[]
[ 1 ]
[ 2 ]
[ 1 2 ]
[ 3 ]
[ 1 3 ]
[ 2 3 ]
[ 1 2 3 ]
[ 4 ]
[ 1 4 ]
[ 2 4 ]
[ 1 2 4 ]
[ 3 4 ]
[ 1 3 4 ]
[ 2 3 4 ]
[ 1 2 3 4 ]
/*
Scala program
Print all subsequences of given size
*/
//Stack Node
class Node(var data: Int,
var next: Node)
{
def this(data: Int)
{
this(data, null);
}
}
//Define custom stack and its operation
class MyStack(var top: Node)
{
def this()
{
this(null);
}
//Add a new element in stack
def push(data: Int): Unit = {
//Make a new stack node
var new_node: Node = new Node(data);
if (new_node != null)
{
new_node.next = this.top;
this.top = new_node;
}
else
{
print("Memory overflow\n");
}
}
//remove a top element in stack
def pop(): Unit = {
if (this.top != null)
{
this.top = this.top.next;
}
}
//check that whether stack is empty or not
def is_empty(): Boolean = {
if (this.top != null)
{
return false;
}
else
{
return true;
}
}
//Used to get top element of stack
def peek(): Int = {
if (this.top != null)
{
return this.top.data;
}
else
{
return 0;
}
}
}
class Subsequence(var stack: MyStack)
{
def this()
{
this(new MyStack());
}
// Display given array elements
def display(collection: Array[Int], size: Int): Unit = {
print("\n Given collection \n ");
var i: Int = 0;
while (i < size)
{
print(" " + collection(i) + " ");
i += 1;
}
}
//Display subsequences
def print_element(): Unit = {
var temp: Node = this.stack.top;
print(" [");
//Display stack elements
while (temp != null)
{
print(" " + temp.data + " ");
//visit to next node
temp = temp.next;
}
print("]\n");
}
//Recursive finding all elements of subsequences
def all_subsequences(collection: Array[Int], location: Int): Unit = {
if (location == -1)
{
//Print the sub-sequences, with empty sequences
print_element();
}
else
{
all_subsequences(collection, location - 1);
// Add a element into stack
this.stack.push(collection(location));
all_subsequences(collection, location - 1);
// Remove a stack element
this.stack.pop();
}
}
// Handles the request to print subsequence element
def subsequences(collection: Array[Int], size: Int): Unit = {
if (size <= 0)
{
return;
}
// Display given collection elements
display(collection, size);
print("\n All subsequences \n");
all_subsequences(collection, size - 1);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: Subsequence = new Subsequence();
var arr: Array[Int] = Array(1, 2, 3, 4);
//Get the size
var size: Int = arr.length;
obj.subsequences(arr, size);
}
}
Output
Given collection
1 2 3 4
All subsequences
[]
[ 1 ]
[ 2 ]
[ 1 2 ]
[ 3 ]
[ 1 3 ]
[ 2 3 ]
[ 1 2 3 ]
[ 4 ]
[ 1 4 ]
[ 2 4 ]
[ 1 2 4 ]
[ 3 4 ]
[ 1 3 4 ]
[ 2 3 4 ]
[ 1 2 3 4 ]
/*
Swift 4 program
Print all subsequences of given size
*/
//Stack Node
class Node
{
var data: Int;
var next: Node? ;
init(_ data: Int)
{
self.data = data;
self.next = nil;
}
}
//Define custom stack and its operation
class MyStack
{
var top: Node? ;
init()
{
self.top = nil;
}
//Add a new element in stack
func push(_ data: Int)
{
//Make a new stack node
let new_node: Node? = Node(data);
if (new_node != nil)
{
new_node!.next = self.top;
self.top = new_node;
}
else
{
print("Memory overflow\n", terminator: "");
}
}
//remove a top element in stack
func pop()
{
if (self.top != nil)
{
self.top = self.top!.next;
}
}
//check that whether stack is empty or not
func is_empty() -> Bool
{
if (self.top != nil)
{
return false;
}
else
{
return true;
}
}
//Used to get top element of stack
func peek() -> Int
{
if (self.top != nil)
{
return self.top!.data;
}
else
{
return 0;
}
}
}
class Subsequence
{
var stack: MyStack ;
init()
{
self.stack = MyStack();
}
// Display given array elements
func display(_ collection: [Int], _ size: Int)
{
print("\n Given collection \n ", terminator: "");
var i: Int = 0;
while (i < size)
{
print(" ", collection[i]," ", terminator: "");
i += 1;
}
}
//Display subsequences
func print_element()
{
var temp: Node? = self.stack.top;
print(" [", terminator: "");
//Display stack elements
while (temp != nil)
{
print(" ", temp!.data ," ", terminator: "");
//visit to next node
temp = temp!.next;
}
print("]\n", terminator: "");
}
//Recursive finding all elements of subsequences
func all_subsequences(_ collection: [Int], _ location: Int)
{
if (location == -1)
{
//Print the sub-sequences, with empty sequences
self.print_element();
}
else
{
self.all_subsequences(collection, location - 1);
// Add a element into stack
self.stack.push(collection[location]);
self.all_subsequences(collection, location - 1);
// Remove a stack element
self.stack.pop();
}
}
// Handles the request to print subsequence element
func subsequences(_ collection: [Int], _ size: Int)
{
if (size <= 0)
{
return;
}
// Display given collection elements
self.display(collection, size);
print("\n All subsequences \n", terminator: "");
self.all_subsequences(collection, size - 1);
}
}
func main()
{
let obj: Subsequence = Subsequence();
let arr: [Int] = [1, 2, 3, 4];
//Get the size
let size: Int = arr.count;
obj.subsequences(arr, size);
}
main();
Output
Given collection
1 2 3 4
All subsequences
[]
[ 1 ]
[ 2 ]
[ 1 2 ]
[ 3 ]
[ 1 3 ]
[ 2 3 ]
[ 1 2 3 ]
[ 4 ]
[ 1 4 ]
[ 2 4 ]
[ 1 2 4 ]
[ 3 4 ]
[ 1 3 4 ]
[ 2 3 4 ]
[ 1 2 3 4 ]
Time Complexity
The time complexity of the algorithm is O(2^n), where n is the number of elements in the input array. This is because for each element, we have two choices: include it or exclude it. Hence, there will be a total of 2^n possible subsequences. As we need to print all of them, the time complexity is exponential.
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