This is how we heapify the given array of elements.
#define SWAP(x,y) \
x = x ^ y; \
y = x ^ y; \
x = x ^ y; \
void siftDown(vector<int> &v, int start, int end)
{
int root = start;
while (root*2+1 <= end){
int child = root*2+1;
int swap = root;
if (child <= end && v[swap] < v[child]) {
swap = child;
}
if(child+1 <= end && v[swap] < v[child+1]) {
swap = child+1;
}
if (swap != root) {
SWAP(v[root], v[swap]);
root = swap;
} else {
return;
}
}
}
void heapify(vector<int> &v, int count)
{
int start = floor((count-2)/2);
while (start >=0 ) {
siftDown(v, start, count-1);
start = start - 1;
}
}
We modify the stack functionality a little to maintain the element order in the stack with the incoming elements.
void insertToStack(vector<int> &v, stack<int> &s, int val)
{
/* Temporary vector to keep the order from the stack */
vector<int> tmp;
/* Pop the elements till new value finds its place */
while(!s.empty() && v[s.top()] > v[val]){
tmp.insert(tmp.begin(), s.top());
s.pop();
}
/* push the new value into the stack */
s.push(val);
/* Push all the elements in the same order
which are previously popped out */
vector<int>::iterator it;
for (it=tmp.begin(); it<tmp.end(); it++) {
s.push(*it);
}
}
This function traverses the heap to find the Kth element in log time
int find(vector<int> &v, stack<int> &s, int index, int pos, int count)
{
/* If current element is smaller than the element in the stack,
update the current element with the top of the stack and
push the current element into the stack*/
if (!s.empty() && v[s.top()] > v[index]) {
insertToStack(v, s, index);
index = s.top();
}
if (pos == count) {
/* If the count reaches pos, return the current element */
return v[index];
} else {
int lchild = index*2+1;
int rchild = lchild+1;
/* Check if the current element has right child */
if (rchild > v.size()-1) {
/* Check if the current element has left child */
if (lchild > v.size()-1) {
/* The current element is the leaf node. Get the top of
the stack to proceed further */
index = s.top();
s.pop();
} else {
/* The current element has only left child. */
if (s.empty() || v[lchild] > v[s.top()]) {
index = lchild;
} else {
index = s.top();
s.pop();
insertToStack(v, s, lchild);
}
}
} else {
/* Find the max and min from the child nodes */
int max = 0;
int min = 0;
if (v[lchild] > v[rchild]) {
max = lchild;
min = rchild;
} else {
min = lchild;
max = rchild;
}
/* Find the highest element among the child nodes & the top
of the stack, Update the current element with the highest
element and push the other two elements into the stack */
if (s.empty()) {
insertToStack(v, s, min);
index = max;
} else {
int top = s.top();
if (v[max] < v[top]) {
index = top;
s.pop();
insertToStack(v, s, min);
insertToStack(v, s, max);
} else {
index = max;
if (v[min] > v[top]) {
insertToStack(v, s, min);
} else {
s.pop();
insertToStack(v, s, min);
insertToStack(v, s, top);
}
}
}
}
/* Call "find" recursively till "count" reaches "pos" */
return find(v, s, index, pos, count+1);
}
}
int findElement(vector<int> &v, int pos)
{
/* Start with am empty stack */
stack<int> s;
return find(v, s, 0, pos, 1);
}
You are NOT A FAN of recursion? Here you go,
@@ -1,5 +1,6 @@
int find(vector<int> &v, stack<int> &s, int index, int pos, int count)
{
+ while (count <= v.size()) {
/* If current element is smaller than the element in the stack,
update the current element with the top of the stack and
push the current element into the stack*/
@@ -74,8 +75,7 @@
}
}
}
-
- /* Call "find" recursively till "count" reaches "pos" */
- return find(v, s, index, pos, count+1);
+ }
+ count++:
}
}
Here is the main function
int main(int argc, char **argv)
{
/* Store the inputs into a vector */
vector<int> input;
int total= stoi(argv[1]);
for(int c=0; c<total; c++){
input.insert(input.end(), stoi(argv[c+2]));
}
/* Print them */
vector<int>::iterator it;
cout << " my vector contains:";
for (it=input.begin(); it<input.end(); it++)
cout << ' ' << *it;
cout << endl;
/* Heapify the input vector */
heapify(input, total);
cout << "my heap vector contains:";
for (it=input.begin(); it<input.end(); it++)
cout << ' ' << *it;
cout << endl << endl;
for (int count=1; count<=total; count++) {
int ret = findElement(input, count);
cout << "(" << count << "): " << ret << endl;
}
return 0;
}
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define ERRNUM -1
#define SUCCESS 0
#define TRUE 1
#define FALSE 0
#define TOTAL_ALPHA 26
/* Function : permutations
* Args : str [IN]
* index [IN]
* result [IN/OUT]
* Description: Function will print all the permutations and combinations of a given string
* without repeated patterns. PnC(ABC) = { A+PnC(BC), B+PnC(CA), C+PnC(AB) }
* Note : This "without repeated patterns" will not work for non-alpha characters [TBD].
*/
int permutations (char *str, int index, char *result)
{
char *temp = NULL; // To store the given string for processing
int len = strlen (str); // Length of the given string
int count = 0; // Counter variable used in the loop
int j = 0; // Temporary variable
char found[52] = {0}; // To check the variable to check the duplicate characters to avoid duplicate patterns
/* Allocate memory for the temp variable to store the given string for processing.
* So that the given string will not change.
*/
temp = (char *) calloc (len+1, sizeof (char));
if (NULL == temp)
{
fprintf (stderr, "Memory allocation failed.\n");
return ERRNUM;
}
/* Copy the given string into the temporary variable */
strcpy (temp, str);
/* Traverse through the string and find the permutations and combinations of the substring
* PnC(ABC) = { A+PnC(BC), B+PnC(CA), C+PnC(AB) }
*/
for (count=0; count < len; count++)
{
char ch = 0;
*(result + index) = *temp;
if (1 == len)
{
/* We can store in an array of string or a stack */
printf ("%s\n", result);
}
else
{
if (isupper (*temp))
{
if (FALSE == found [TOTAL_ALPHA + (*temp) - 'A'])
{
found [TOTAL_ALPHA + (*temp) - 'A'] = TRUE;
}
else
{
/* Its a duplicate character */
goto NEXT;
}
}
else if (islower (*temp))
{
if (FALSE == found [(*temp) - 'a'])
{
found [(*temp) - 'a'] = TRUE;
}
else
{
/* Its a duplicate character */
goto NEXT;
}
}
/* We can store in an array of string or a stack */
for (j=0; j<=index; j++)
{
printf ("%c", *(result+j));
}
printf ("\n");
/* Find the permutations and combinations for the substring too */
if (ERRNUM == permutations (temp+1, index+1, result))
{
return ERRNUM;
}
NEXT:
ch = *temp;
memcpy (temp, temp+1, len-1);
temp[len-1] = ch;
}
}
/* Free the allocated memory for the temporary variable */
free (temp);
return SUCCESS;
}
int main (int argc, char *argv[])
{
char *result = NULL; // Variable to store the result for printing
int retVal = SUCCESS; // Variable to stroe the return value
// No code to check/validate the input [TBD].
if (NULL == result)
{
result = (char *) calloc (strlen (argv[1])+1, sizeof (char));
if (NULL == result)
{
fprintf (stderr, "Memory allocation failed.\n");
return ERRNUM;
}
}
retVal = permutations (argv[1], 0, result);
free (result);
return retVal;
}
The results:
prompt$ ./permutationsNconbination ABC
A
AB
ABC
AC
ACB
B
BC
BCA
BA
BAC
C
CA
CAB
CB
CBA
prompt$ ./permutationsNconbination AAB
A
AA
AAB
AB
ABA
B
BA
BAA
prompt$ ./permutationsNconbination AAA
A
AA
AAA
prompt$
