Posted on by Kalkicode
Code Stack

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

  1. Create a stack data structure to hold the elements of the current subsequence.
  2. Traverse the array from the last element to the first element.
  3. For each element at index i in the array: a. Call the recursive function all_subsequences with the array and the index i-1. b. Push the element at index i into the stack. c. Call the recursive function all_subsequences with the array and the index i-1. d. Pop the element from the stack.
  4. 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.
  5. 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.

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