# The Next Permutation (with proof)

Problem:You have an array of numbers and you want to find the next lexicographic(the next in order) permutation.

Conventions and assumptions:

1. for the array with contents a,b,c,d…. when I say number I mean abcd…(array with contents 2,1,3,4 will be number 2134)
2. for a number left side means higher significant digits (lower array index) and right side means lower significant digits (higher array index)
3. we assume all array elements are distinct for simplicity , however the algorithm will also work for non distinct digits
4. the array indices are a1,a2,a3,….an
5. proofs are kind of informal

Okay, so how do we find the next permutation of a number?

So we have a number now and the next permutation will be a number bigger than the current number.

Step 1. We have to find two numbers ‘small’ and ‘big’ such that the small<big and ‘small’ occurs to the left of ‘big’ and we have to ensure that index of small is as large as possible. Also the number big should be as small as possible while still being greater than the number small (we will see why all this is necessary)
step 2. swap small and big
step 3. sort all the numbers appearing after the index of the big number (after swapping)

Claim 1 : ‘small’ should be to the left of ‘big’ always
Proof 1
This, I believe doesn’t require proof, it is easy to see and is intuitive. How else are you going to form a bigger number using the same digits?

Claim 2: the index of ‘small’ should be as large as possible
Proof 2
Consider number small1 whose index is n1 and the number big1 whose index is n2 (small1<big1 and n1<n2). Assume that index of small1 is not the largest and we are able to find small2 and big2 with index n3 and n4 respectively(small2<big2 and n3<n4) and n3>n1 (this is important).
Now we can form two numbers, one by swapping small1 and big1 call it num1 and the other by swapping small2 and big2 call it num2. num1 has a bigger number at index n1 and num2 has a bigger number at index n3 and since n3>n1 num2 has a change at its lesser significant digit positions.
So clearly num2<num1. (if you are not convinced ,write some numbers and try it out).
This means num1 will not be the next permutation since we were able to find num2 such that num2<num1.
Therefore it is crucial that index of the small number that we find is the largest possible.

Claim 3 : The ‘small’ number is always immediately to the left of a number bigger than it
i.e if we find the largest k such that array[k]<array[k+1] then array[k] will be our ‘small’ number.

Proof 3: (array[k] and small mean the same thing)

Lets assume that index of ‘small’ is k and array[k+1]<small. Lets say there exists array[k+x] (where x>1) such that array[k+x]>small.
So what we are saying above is the next number to ‘small’ ( to the right) is not bigger than ‘small’ and the bigger number is somewhere else ( obviously to the right of index k+1).

But now we see that (arr[k+x] is that bigger number we were talking about, the one that is not next to small)

a. array[k]>array[k+1]
b. array[k+x] > array[k] (where x>0 and x<=n)
from a and b
c. array[k+1]<array[k+x]

This means that the number at index k cannot be the ‘small’ number since we are able to find a number at k+1 , array[k+1] that satisfies all the properties of the ‘small’ number (note that ‘small’ numbers index should be as large as possible).
So if we find the largest k such that array[k]<array[k+1] then array[k] will be our ‘small’ number. This makes finding our small number really easy. ( O(n) )

Claim 4: When the small number is at the index k then the array will be of the form
…a[k+1]>a[k+2]>a[k+3]>……>a[n] (i.e it’ll be in descending order after index k)

Proof 4: (this will be helpful in finding the ‘big’ number also note that we still haven’t done anything to the array no swaps we have only found the ‘small’ number)

Assume this is not the case, say it is like this instead a[k+1]>a[k+2]<a[k+3] (or any other way that contradicts the claim) this contradicts our proof3 that k is the largest index such that a[k]<a[k+1] because we are able to find a[k+2]<a[k+3].
So our assumption is wrong and it is clear that ….
a[k+1]>a[k+2]>a[k+3]>……>a[n] (i.e it’ll be in descending order after index k which is index of small number)

Okay now we have found the ‘small’ number how do we find the ‘big’ number?

The thing to be noted is that the ‘big’ number should be as small as possible while still being greater than the ‘small’ number and its index should be greater than k (we are going to swap this number with the ‘small’ number so if we don’t pick the smallest number then it will not result in the very next permutation after we swap them, try out a few examples to convince yourself,proving this is left out as an exercise to the reader , ahahaa I always wanted to say that.)
So we just start scanning from the last index and move towards the lower indices and when we find a[k+x]>a[k] (again x>0) then a[k+x] will be our ‘big’ number. Note that such a number always exists because a[k+1] is also such a number.

Swap the ‘big’ and ‘small’ numbers and we still see that what we showed in proof 4 holds.

why sort after index k+1?
Now that we have swapped them the numbers, the numbers after index k (k+1 to n ) should be sorted in ascending order because only that will give us the very next permutation (not hard to prove try it out yourself)
This sorting will be very easy because since they are already in descending order we just need to reverse the array after index k.

Aaand we are done 🙂

The algorithm:

step1. Find the largest k such that a[k]<a[k+1] (if no such number exists then there is no next permutation)

step 2. find the largest x such that a[k]<a[x] (and x>k)

step 3. swap a[k] and a[x]

step 4. reverse a[k+1] to a[n]

here’s the program:

```#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

#define size 1000
bool Next_Permutation(char *a){
bool possible=false;
int small,big; // we will store index of small and big instead of the values
int l=strlen(a);

//finding small number
for(int k=l-2;k>=0;k--){
if(a[k]<a[k+1]){
small=k;
possible=true;
break;
}
}
if(possible){
//finding big number
for(int x=l-1;x>small;x--){
if(a[x]>a[small]){
big=x;
break;
}
}
//swap small and big
swap(a[small],a[big]);

//now reverse from index k+1(small) to n
for(int st=small+1,en=l-1;st<en;st++,en--){
swap(a[st],a[en]);
}
}
return possible;
}
int main(){
char num[size];
scanf("%s",num);//input number
if(Next_Permutation(num))
printf("%s\n",num);
else
printf("no next permutation\n");
return 0;
}
```

or you could use this
http://www.cplusplus.com/reference/algorithm/next_permutation/

# Know your language – Part 1

1. sizeof operator (c/c++)
We know that the sizeof(variable) returns the size of the variable and sizeof(pointer) returns the amount of memory that can be addressed  in bytes.

```#include
#include
using namespace std;
void sz(int p[]){
cout<<"sz: "<<sizeof(p)<<"\n";
}
int main(){
int p[]={1,2,3,4};
cout<<"main: "<<sizeof(p)<<"\n";
sz(p);
cout<<"main: "<<sizeof(p)<<"\n";
cout<<"sizeof(p):"<<sizeof(p)<<"   sizeof(&p[0]):"<<sizeof(&p[0])<<"\n";
return 0;
}
```

output:

```main: 16
sz: 8
main: 16
sizeof(p):16   sizeof(&p[0]):8
```

int p[4];
we know that p points to the first element in the array so the sizeof(p) should return the size of the memory being addressed, and so p is same as &p[0] and so sizeof(p) and sizeof(&p[0]) should be same.But that is not the case, sizeof(p) gives the sizeof the array in bytes i.e sizeof(int)*4 in this case.

2. Sequence points
A sequence point is a point in the programs execution where all previous side effects shall have taken place and where all subsequent side effects shall not have taken place.
So you should update a variable only once between sequence points.
examples of codes that have undefined behaviour.

```
int x=5,y=0,z;
x=x++; // undefined behavior
z=y++ + ++ y;// undefined behavior
```

3. Changing the value of  a constant variable(only c)

```const int f=2;
f=8; //error: assignment of read-only variable ‘f’
//but u can use pointers to change its value and this only works in c
//gives warnings(warning: assignment discards ‘const’ qualifier from pointer target type) but works
int *p;
p=&f;
*p=8;
printf("%d\n",f); //prints 8
```

```#include<stdio.h>
struct basic{
int a;  char b;
};
struct kaboom{
int a;  char c;  int b;  char d;
};
struct noKaboom{
int a;  char c;  char d;  int b;
};
struct f{
int a; char c[4]; int d;
};
int main(){
printf("%zu\n",sizeof(struct basic));
printf("%zu %zu\n",sizeof(struct kaboom),sizeof(struct noKaboom));
printf("%zu\n",sizeof(struct f));
return 0;
}
```

the sizeof struct basic is not sizeof(int)+ sizeof(char)
when the size goes over a word length (specific to each computer) the rest is padded to make it a multiple of 1 word length
in this case the word length is 4 (on a 32 bit machine) so size of int+char is 5 so it makes it 8 by padding it.

why is this done?
It is expensive to work on subword size data types so compiler will pad them so that they are on the word boundary.
Why is it expensive?
It is because the instruction set of most processors is optimized to move 1 word data between the processor and the memory.

the output of the above program is:

```8
16 12
12
```

5. Wtf is happening here!?

😛

# Competitive Programming

What is competitive programming?

http://en.wikipedia.org/wiki/Competitive_programming

now to the more important/fun part

Why do it?
1.It is super fun
(most of the top programmers who compete in such competitions work for big companies like google,facebook etc)
How do i get started?

register here
http://www.codechef.com/
http://www.spoj.pl/

Ok now how do i solve the problems there?
We’ll take this simple problem
http://www.spoj.pl/problems/TEST/

Before you start solving it is important to know how the online judge system judges your solution

it redirects your output to a file and compares it with the correct output file (that they already have on their server)  so your program should not output any extra characters, if it does it will result in a wrong answer. (you should not print things like “input number”, “the answer is:”, output ONLY what is asked)

And also since only the output files are compared it does not matter at which point in your program you print the output as long as it is correct.

also i highly recommend you read everything here, http://www.codechef.com/wiki/faq
it also applies to other online judges.

here is a solution to the problem

```#include<iostream>
using namespace std;
int main()
{
int input;
while(1)
{
cin>>input;
if(input==42)
break;
else
cout<<input<<"\n";
}

return 0;
}
```

ok, I’ve been solving problems what now?
By now you would have already noticed that you are forced to learn stuff if you want to solve a particular problem. If you have solved around 50 problems you can start participating in timed programming competitions.
http://codeforces.com/
http://www.topcoder.com/
they are more fun and you learn a lot of stuff in the 1-2 hours you participate in each contest.

and also try this, http://train.usaco.org/usacogate

You have listed so many sites, how are they different?
1.http://www.spoj.pl/
they dont have any timed contests, the solutions are not public.Wrong answers dont cost you penalties so you can use this site for practicing and experimenting.

2.http://www.codechef.com/
they have 2 contests every month- challenge and cook off
challenge- it lasts for 10days  and there are no penalties for wrong answers
cook off-  it lasts for 2 hours and there are penalties for wrong answers
also they have a practice section where the solutions are public and also all the contest solutions are made public once the contest is over
3. http://www.topcoder.com/http://codeforces.com/

They host a lot of competitions every month ( 3 or more). And all the solutions are made public after the contests.All the top programmers participate here so you get to see how they have solved after the contest is over.

Well now you are on your own 😛

# N Queens – Backtracking

The N queens puzzle is the problem of placing N chess queens on an N×N chessboard so that no two queens attack each other.

Here we are going to look at a small variation of the problem, some of the queens have already been placed on the board we have to find the solution without disturbing the queens that have already been placed.

Basic idea:
1
.Has a queen already been placed on the current row?

1a.yes- Move to next row (step1 again with next row)

1b.no- find the column on the current row that isn’t attacked and that hasn’t already been tried before for that particular row. Is it possible?

2a. yes (it is possible to find such a square in current row)
place the queen and goto step1 with next row
2b. no (not possible to find any column on current row that isn’t attacked)
go to step1 with previous row ( backtrack)

Here is the solution , it will make things easier to understand

The program takes as input N ( the dimension of the chessboard NxN)
then it takes N inputs -c1,c2,….cn
the column number of the queen in each row (0 means no queen in that row)

```#include<iostream>
#include<cstdio>
#include<cstring>
int queens[60],n;
bool fixed[60],solved;
bool isAttacked(int row,int col){
//function checks if current row and column is attacked
// checks rows,columns and diagonals
if(queens[row]!=0)
return true;
else{
for(int i=1;i<=n;i++)
if(queens[i]==col) return true;
for(int r=row,c=col;r>=1&&c>=1;r--,c--)
if(queens[r]==c) return true;
for(int r=row,c=col;r<=n&&c<=n;r++,c++)
if(queens[r]==c) return true;
for(int r=row,c=col;r<=n&&c>=1;r++,c--)
if(queens[r]==c) return true;
for(int r=row,c=col;r>=1&&c<=n;r--,c++)
if(queens[r]==c) return true;
}
return false;
}
void solve(int row){
if(row==n+1){
// row==n had a solution which is why we are at n+1 so
// the problem is solved, print answer
for(int k=1;k<=n;k++)
printf("%d ",queens[k]);
putchar('\n');
solved=true;
}
if(solved) return;// problem already solved so return

if(fixed[row]) solve(row+1);// current row already has a queen
//fixed (given as input) so move on to next row
else{
for(int i=1;i<=n;i++){
if(isAttacked(row,i)==false){
queens[row]=i; // not attacked so place queen
solve(row+1); //move on to next row
queens[row]=0; // backtrack
}
}
}
}
int main(){
while(scanf("%d",&n)&&n!=0){
memset(queens,0,sizeof(queens));
memset(fixed,false,sizeof(fixed));
solved=false;
for(int i=1;i<=n;i++){
scanf("%d",&queens[i]);
}
solve(1);
if(!solved)printf("No solution exists for the given input\n");
}
return 0;
}
```

Backtracking is slow and has its limitations (sloooow), if you want it to work for large values of N take a look at these links
http://en.wikipedia.org/wiki/Knuth’s_Algorithm_X

# Memoization

What is memoization?
No,it is not memorization wrongly spelled :P. Memoization is an algorithm optimization technique.

How does it work?
It avoids unnecessary recursive calls by storing the processed values for the particular input and by reusing the values when the same input is encountered again(like caching).

Examples
1 .Factorial
consider the following program  that calculates the factorial using recursion

(the programs are only for demonstrating the concept of memoization, standard data types (in c,c++ etc)  are not sufficient to hold the value
of factorial for larger values of  n)

```//not the best method
using namespace std;
#include<cstdio>
long factorial(long n){
if(n==0)
return 1L;
else
return n*factorial(n-1);
}
int main()
{
long n;
while(scanf("%ld",&n) && n>0){ //take input till negative number encountered
printf("%ld\n",factorial(n));
}
return 0;
}
```

Let us provide the first input as 4 and trace the calls ( factorial(n) is called f(n) to make it look cleaner)
f(4)
4*f(3)
4*3*f(2)
4*3*2*f(1)
4*3*2*1*f(0)
4*3*2*1*1
here we see that in the process of calculating f(4) we also calculate f(3),f(2),f(1)
But, if we provide the second input as 3 it is obvious that the program will again calculate f(3) from scratch.
If we store the value for each value of n as we calculate we can just return that value if the same value of n is given as input again.

here is the same program modified to avoid unnecessary calls
(if you are using c++ it is a better idea to use the standard hash map instead of the array
to store the preprocessed values,here i’m just using the array to keep it simpler :))

```//optimized program
using namespace std;
#include<cstdio>
#include<cstring>
long factMemo[50];// assume n takes values such that 0<=n<=100
//factMemo will hold the already processed values
//factMemo[x] will hold the value of f(x)
long factorial(long n){
long temp;
if(n==0)
return 1L;
if(factMemo[n]!=0)//if f(n) has already been computed just return it
return factMemo[n];
else{
temp=n*factorial(n-1);
factMemo[n]=temp;//store the value for future use
return temp;
}
}
int main(){
memset(factMemo,0,sizeof(factMemo));//initially all values are set to zero
long n;
while(scanf("%ld",&n) && n>0){ //take input till negative number encountered
printf("%ld\n",factorial(n));
}
return 0;
}
```

Another example
Starting in the top left corner of an nn grid, how many routes are there to the bottom right corner of the grid. (at each location you are allowed to move to the right of the current or to the one below it)
(which same is this problem at projecteuler http://projecteuler.net/problem=15)
There is a mathematical solutions to this problem, however we will look at the DP solution.

this is the code without optimization

```using namespace std;
#include<iostream>
int size;
unsigned long long grid(int i,int j){
if(j>size-1||i>size-1)
return 0;
if(i==j&&i==size-1){
return 1L;
}
else{
return grid(i+1,j)+grid(i,j+1);
}
}
int main(){
cin>>size;
size+=1;
cout<<grid(0,0)<<endl;
return 0;
}
```

Now when we solve for a particular input x,y we get the number of ways from x,y to the bottom right corner (n,n). And since the program checks all the possible paths, the same x,y coordinates will be encountered a lot of times so if we store it we know that everytime we visit an x,y for which the number of paths to n,n has already been found we dont need to branch further we can use the preprocessed value,since it doesnt depend on the path we followed. for example from n-1,n-1 there will always be 2 ways to reach n,n.

this is the optimized solution

```using namespace std;
#include<iostream>
#include<cstdio>
int size;
unsigned long long memo[30][30];
unsigned long long grid(int i,int j){
unsigned long long temp=0;
if(j>size-1||i>size-1)
return 0;
if(memo[i][j]!=0){
return memo[i][j];
}
if(i==j&&i==size-1){
return 1L;
}
else{
temp+=grid(i+1,j)+grid(i,j+1);
memo[i][j]=temp;
return temp;
}
}
int main(){
memset(memo,0,sizeof(memo));
cin>>size;
size+=1;
cout<<grid(0,0)<<endl;
return 0;
}

```

some data to show the difference between the two programs
(the times  vary according to machine, here however the difference will be obvious no matter which machine you run it on)
time for different values of n(grid size)
n=15
normal solution     : 0m   4.164s
optimized solution: 0m0.000s

n=16
normal solution     : 0m   16.105s
optimized solution: 0m   0.000s

n=17
normal solution     : 1m   2.624s
optimized solution: 0m   0.002s

# Quicksort

`Quick Sort is a divide and conquer sorting algorithm.`

time complexity
worst case : O(n^2)
average case : O(nlogn)

Steps:
1.Divide
2.Merge

1.Divide:
Basic idea:
Divide the main list into two sublists arund a pivot element and sort the two sblists recursively.

• start,end are the starting and ending index of the array to be sorted
• pick a pivot element (it can be any element in the array, in this implementation the middle element is chosen as pivot)
• partition the array into two sub list such that elements in the left sublist are less than the pivot element and the elements in the right sub list are greater than the pivot.
(after this step the pivot is in its correct position in the array.)
•  call quicksort on the two sublists ((start,pivotIndex-1) and (pivotIndx+1,end))
```void quickSort(int *arr,int start,int end)
{
int pivot,pivotIndex,store; //store is used while partitoning the array around the pivot
pivotIndex=(start+end)/2;    //store holds the index to be swapped with if we encounter smaller element
pivot=arr[pivotIndex];
if(start<end){//number of elements is more than one
store=start;
swap(arr[pivotIndex],arr[end]); // the pivot is swapped to the end so that it doesnt get in the way while partitioning
for(int i=start;i<end;i++){     //partition the array around the pivot
if(arr[i]<pivot){
swap(arr[i],arr[store]);
store++;
}
}
swap(arr[end],arr[store]); //swap the pivot(which is at the end) back to the correct position
/*at this point the array is partitioned around the pivot the left list with
values lesser than pivot and the right list with values greater than the pivot
*/
quickSort(arr,start,store-1); //recursively sort left
quickSort(arr,store+1,end);  //recursively sort right
}

}

```

the partioning method used above:

• swap the pivot and the last element
• initialize ‘store’ to ‘start’ of array
• for i in range start to end-1
if arr[i]<pivot then swap arr[i] and arr[store] and increment ‘store’
• swap arr[store] and arr[end] so that pivot element is in its correct position

there are other methods to partiton the array in place(even without swapping), however I find this easier to understand.

2.Merge
There is no need for a merge step because we are doing the partition step in place 🙂

Here’s the complete program:

```using namespace std;
#include<iostream>
#include<cstdio>
#include<cstdlib>
void swap(int *a,int *b)
{
int temp;
temp=*a;
*a=*b;
*b=temp;
}
void quickSort(int *arr,int start,int end)
{
int pivot,pivotIndex,store;
pivotIndex=(start+end)/2;
pivot=arr[pivotIndex];
if(start<end){
store=start;
swap(arr[pivotIndex],arr[end]);
for(int i=start;i<end;i++){
if(arr[i]<pivot){
swap(arr[i],arr[store]);
store++;
}
}
swap(arr[end],arr[store]);
quickSort(arr,start,store-1);
quickSort(arr,store+1,end);
}

}
int main()
{
int n;
scanf("%d",&n);
int arr[n];
for(int i=0;i<n;i++)
scanf("%d",&arr[i]);
quickSort(arr,0,n-1);
//prints sorted array
for(int i=0;i<n;i++)
printf("%d\n",arr[i]);
return 0;
}
```

Note:
Although the pivot can be element between start and end the algorithm will have a worst case of nlogn if we manage to pick the median of the array as the pivot everytime.
I will try to do one on the optimizations of quicksort soon 🙂

# Merge Sort

It is a sorting algorithm based on the divide and conquer paradigm.

It has two steps:
1.Divide
2.Merge

1.Divide
Basic idea: recursively divide the list with n elements into n sublists (each with one element) and call merge

The function takes as input an array ,starting and ending index of the array ,
we divide the array two sublists like this:
(start,middle),(middle+1,end)
and we recursively call the merge function for the sublists till start<end for each sublist
why till start<end ?
if start==end it means we have one element(no need to split),start>end is not valid
so start<end ensures the list has atleast two elements before splitting it

```void split(int *arr,int start,int end){
if(start<end){
int middle=(start+end)/2;
split(arr,start,middle);
split(arr,middle+1,end);
merge(arr,start,middle,end);
}
}
```

2.Merge
Basic idea: take two lists as input and merge them into a new list in sorted order.

The function takes as input an array and the start,middle,end of the array.
The array is treated as two sublists (start,middle) and (middle+1,end) which are to be merged

• temp array will hold the contents of the merged lists
• ‘p1’ points to starting index of left sublist and ‘p2’ of the right sublists
• ‘index’ points to the top of the temp array

Now  begin by comparing the starting index of left sublist with that of the right sublist and put whichever is smaller into the temp array first and increment the respective lists starting index,we do this till all the elements  in the two sublists are in the temp array.

```void merge(int *arr,int start,int middle,int end)
{
int p1,p2,index,temp[size];
index=p1=start;
p2=middle+1;
while(p1<=middle&&p2<=end){//till there are elements to compare
if(arr[p1]>arr[p2]){
temp[index]=arr[p2];
index++;p2++;
}
else{
temp[index]=arr[p1];
index++;p1++;
}
}
/*at this point all the contents of one of the lists is in temp
find out which list has elements yet to be added to temp
and append them to the temp list (we dont need to check anything
since the sublists are already sorted, so just append to temp)*/

if(p1<=middle){// left sublist has elements left out, so append them to temp list
for(;p1<=middle;p1++,index++)
temp[index]=arr[p1];
}
else{ // right sublists has elements left out, so add its elements to temp list
for(;p2<=end;p2++,index++)
temp[index]=arr[p2];
}

/*since arrays are passed by reference automatically in c++
put the contents of the temp into the main list.
*/
for(int i=start;i<=end;i++)
arr[i]=temp[i];
//at this point main list's elements from index 'start'to 'end ' are sorted
}
```

Putting it all together

```using namespace std;
#include<iostream>
#include<cstdio>
#include<cstdlib>
#define size 100
void merge(int *arr,int start,int middle,int end)
{
int p1,p2,index,temp[size];
index=p1=start;
p2=middle+1;
while(p1<=middle&&p2<=end){
if(arr[p1]>arr[p2]){
temp[index]=arr[p2];
index++;p2++;
}
else{
temp[index]=arr[p1];
index++;p1++;
}
}
if(p1<=middle){
for(;p1<=middle;p1++,index++)
temp[index]=arr[p1];
}
else{
for(;p2<=end;p2++,index++)
temp[index]=arr[p2];
}
for(int i=start;i<=end;i++)
arr[i]=temp[i];
}
void split(int *arr,int start,int end){
if(start<end){
int middle=(start+end)/2;
split(arr,start,middle);
split(arr,middle+1,end);
merge(arr,start,middle,end);
}
}
void mergeSort(int *arr,int end){
split(arr,0,end-1);
}
int main()
{
int arr[size],n;
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d",&arr[i]);
mergeSort(arr,n);
//prints sorted array
for(int i=0;i<n;i++)
printf("%d ",arr[i]);
return 0;
}
```