Printing powerset for given set of characters.

Printing powerset of characters is somewhat easy. Here the key point is to understand that for a given number of n characters we will have (2^N)-1 combinations. We will then count thru integers starting from 1 to (2^N)-1 and then check the bit set on the integer and accordingly the same element will be printed from the character array. Below is the C implementation of this interesting program :

	/*
	* Combinatorial.cpp
	*
	* Created on: Dec 6, 2014
	* Author: prasadnair
	*/
	#include <stdio.h>
	#include <math.h>
	void printPowerSet(char *, int );
	/*Driver program to test printPowerSet*/
	int main()
	{
	char set[] = {'a','b','c', 'd'};
	printPowerSet(set, 4);
	getchar();
	return 0;
	}
	void printPowerSet(char *set, int set_size)
	{
	/*set_size of power set of a set with set_size
	n is (2**n -1)*/
	unsigned int pow_set_size = pow((float)2, set_size);
	int counter, j;
	/*Run from counter 000..0 to 111..1*/
	for(counter = 0; counter < pow_set_size; counter++)
	{
	for(j = 0; j < set_size; j++)
	{
	/* Check if jth bit in the counter is set
	If set then print jth element from set */
	if(counter & (1<<j))
	printf("%c", set[j]);
	}
	printf("\n");
	}
	}

view raw PowerSet.c hosted with ❤ by GitHub

Stack implementation in C language.

Given below is a simple stack implementation in C language. Three main functions of a stack are implemented here, namely push, pop and top.

	#include <stdio.h>
	#include <stdlib.h>
	int top;
	int push( int temp , int *arr)
	{
	if(top >10 )
	{
	printf("stack is full\n");
	return -1;
	}
	if(arr == NULL)
	{
	printf("stack is empty\n");
	top = 1;
	arr[0] = temp;
	return 1;
	}
	else
	{
	top = top + 1;
	arr[top] = temp;
	return 1;
	}
	}
	int pop(int *arr)
	{
	int temp = 0;
	if(arr == NULL)
	{
	printf("stack doesnt exist\n");
	return -1;
	}
	if(top == 0)
	{
	printf("stack is empty\n");
	return -1;
	}
	else if (top > 0)
	{
	temp = arr[top];
	top = top - 1;
	return temp;
	}
	else
	{
	printf("Invalid top value\n");
	return -1;
	}
	}
	int topstack(int *arr)
	{
	if(arr == NULL)
	{
	printf("stack doesnt exist\n");
	return -1;
	}
	if(top >= 0)
	{
	return arr[top];
	}
	else
	{
	printf("Invalid top value\n");
	return -1;
	}
	}
	int main()
	{
	int *arr;
	int popvalue;
	top = 0;
	arr = (int *) malloc (sizeof(10));
	push(1,arr);
	push(2,arr);
	push(3,arr);
	push(4,arr);
	push(5,arr);
	push(6,arr);
	push(7,arr);
	push(8,arr);
	push(9,arr);
	push(10,arr);
	push(11,arr);
	push(12,arr);
	printf("Popped value %d \n",pop(arr) );
	printf("Popped value %d \n",pop(arr) );
	printf("Popped value %d \n",pop(arr) );
	printf("Top value %d \n",topstack(arr));
	getchar();
	return 0;
	}

view raw stack.c hosted with ❤ by GitHub

String compression

Given a string with repeated characters find out a way to compress the string with a count of number of times the character got appended. For example a string like "aabbbccdeeefff" would become like "a2b3c2de3f3" after compression !

	#! /usr/env/path python
	sampleStr = "aabbbccdeeefff"
	#compress the string a2b3c2de3f3
	def compressString(sampleStr):
	count = 0
	temp = sampleStr[0]
	compressedString = ""
	for i in range(len(sampleStr)):
	if (sampleStr[i] == temp):
	count += 1
	temp = sampleStr[i]
	else:
	if (count > 1):
	compressedString = compressedString + temp + str(count)
	else:
	compressedString = compressedString + temp
	temp = sampleStr[i]
	count = 1
	if (count > 1):
	compressedString = compressedString + temp + str(count)
	else:
	compressedString = compressedString + temp
	return compressedString
	print(compressString(sampleStr))

view raw compress.py hosted with ❤ by GitHub