Topics

Saturday, May 16, 2020

Array, Pointer Programs .

↓↑ Program 1

#include<stdlib.h> struct node { int x; struct node *next; }; int main() { /* This will be the unchanging first node */ struct node *root; /* Now root points to a node struct */ root = (struct node *) malloc( sizeof(struct node) ); /* The node root points to has its next pointer equal to a null pointer set */ root->next = 0; /* By using the -> operator, you can modify what the node, a pointer, (root in this case) points to. */ root->x = 5; }

BT problem 1 - Generate all permutations of a string.

Permutations of string ABC are ABC, ACB, BAC, BCA, CBA, CAB

Recurcive program to genrate permutation of String [ ABC ]

*******************  Program ***************************

/*
Time Complexity: O(n*n!)
This program prints unique permutation,
if there are no repeating character in string.
in case of duplicate chars it will print duplicate permutations.
 */

#include <iostream>
using namespace std;

void string_permutation(string str, int left, int right){
// terminating condition
if(left == right){
cout << str << endl;
return;
}
for(int itr = left ; itr <= right ; itr++){
swap(str[left],str[itr]);
string_permutation(str, left + 1, right );
swap(str[left], str[itr]); // BT
}
}

int main(){
string str = "ABC";
string_permutation(str, 0, str.size()-1);
return 0;
}


Call flow of string_permutation function:
>>[Entry Permute] ABC with 0:2
itr=0 ***
[1.Before Permute] swap A with A
left= 0 right=2
[2.Permute] ABC with 1:2
>>[Entry Permute] ABC with 1:2
itr=1 ***
[1.Before Permute] swap B with B
left= 1 right=2
[2.Permute] ABC with 2:2
>>[Entry Permute] ABC with 2:2
ABC

[3.After Permute] swap B with B
itr=2 ***
[1.Before Permute] swap B with C
left= 1 right=2
[2.Permute] ACB with 2:2
>>[Entry Permute] ACB with 2:2
ACB

[3.After Permute] swap C with B

[3.After Permute] swap A with A
--------------------------------
itr=1 ***
[1.Before Permute] swap A with B
left= 0 right=2
[2.Permute] BAC with 1:2
>>[Entry Permute] BAC with 1:2
itr=1 ***
[1.Before Permute] swap A with A
left= 1 right=2
[2.Permute] BAC with 2:2
>>[Entry Permute] BAC with 2:2
BAC

[3.After Permute] swap A with A
itr=2 ***
[1.Before Permute] swap A with C
left= 1 right=2
[2.Permute] BCA with 2:2
>>[Entry Permute] BCA with 2:2
BCA

[3.After Permute] swap C with A

[3.After Permute] swap B with A
--------------------------------
itr=2 ***
[1.Before Permute] swap A with C
left= 0 right=2
[2.Permute] CBA with 1:2
>>[Entry Permute] CBA with 1:2
itr=1 ***
[1.Before Permute] swap B with B
left= 1 right=2
[2.Permute] CBA with 2:2
>>[Entry Permute] CBA with 2:2
CBA

[3.After Permute] swap B with B
itr=2 ***
[1.Before Permute] swap B with A
left= 1 right=2
[2.Permute] CAB with 2:2
>>[Entry Permute] CAB with 2:2
CAB

[3.After Permute] swap A with B

[3.After Permute] swap C with A
----------------------------------------

Similar Problems : 
1. Palindrome string permutations e.g. -> str = "aacdd" then adcda, dacad, dacad ... 
2. String permutation using STL.next_permutation() function on sorted string.
3. With Given constraint Genrate string permutation. like permutations do not contain "AB" substring.

Array, Pointer Programs .

↓↑ Program 1 #include<stdlib.h> struct node { int x; struct node *next; }; int main() { /* This will be the unchanging f...