Skip to main content

Generating all possible subsequences

Here given code implementation process.

// 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  ]
Last updated on by Kalkicode




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