CareerCup

Narayana Pandita's algorithm should work...

First sort the string then pass it to the function permutaor and every time u have to just find the next greater string than this u will get the permutations which are in strictly greater order :)
void LexicographicPermutator(char str[])
{
int i,j;
int len;
len=strlen(str);
while(1)
{
for(j=len-2;j>=0;j--)
{
if(str[j]<str[j+1])
break;
}
if(j<0)
return;
InsertionSort(str+j+1);
for(i=j+1;i<=n-1;i++)
{
if(str[i]>str[j])
{
str[i]=str[i]+str[j];
str[j]=str[i]-str[j];
str[i]=str[i]-str[j];
}
break;
}





puts(str);

}


}

1. Sort the string is pretty simple
2. Permutate the string just like this

public static int permutation(int[] a, int start, int end) {
        if (start == end) {
            println(a);
            return 1;
        }
        int p = 0;
        for (int i = start; i <= end; i++) {
            int tmp = a[start];
            a[start] = a[i];
            a[i] = tmp;
            p = p + permutation(a, start + 1, end);
            tmp = a[start];
            a[start] = a[i];
            a[i] = tmp;
        }
        return p;
    }

can you please explain with some input string which is not in lexographic order and the corresponding output string that is in lexographic order....

Sort the string first in increasing order;

void pm(char* s){
     printf("%s\n",s);
     int l = strlen(s);
    
     //find k
     int i;
     int m=-1;
     int k=-1;
     for (i=l-2;i>=0;i--){
         if(s[i]<s[i+1]){
              k=i;           
              break;
         }
     }
     
     //k found? if no, stop
     if(k==-1)
              return;     
     else{

         //find m
         for(i=l-1;i>k;i--){
              if(s[i]>s[k]){
                  m = i;
                  break;
              }     
         }
         //now found m;

         //switch;
         char tmp;
         tmp=s[k];
         s[k]=s[m];
         s[m]=tmp;

         //reverse from k+1 to n   
         res(s,(k+1),(l-1));  

         pm(s);
         
          
     }
}

void res(char* r, int s, int e){
      int a,b;
      for(a=s,b=e; a<b; a++,b--){
          char temp;
          temp=r[a];
          r[a]=r[b];
          r[b]=temp;
      }    
}

{
#include <algorithm>
#include <iostream>
#include <ostream>
#include <string>

int main()
{
std::string s = "cabc";

std::sort(s.begin(), s.end());

for (;;)
{
std::cout << s << std::endl;
if (!std::next_permutation(s.begin(), s.end()))
{
break;
}
}

return 0;
}

}

->Sort the string using any sorting algorithm

-> To generate permutations in lexicographical order, use the code below

char *str;//Sorted String
char *temp;//char array of size 1 greater than that of str

void permutations(int index)
{
if(index == strlen(str)) then print temp array;

int i = 0;
while(i<strlen(str))
{
if(str[i]<0){ i++; continue; }
temp[index] = str[i];
str[i] *= -1;
permutation(index + 1);
str *= -1;
i++;
}
}

void swap(char *a, char *b)
{
char c;
c = *a;
*a = *b;
*b = c;
}

int FindMin(char s[], int arr[], int m, int n)
{
char min = 'z';
int ind = -1;
for(int i = m; i < n; i++)
{
if(arr[s[i] - 'a'] == 1) continue;
if(s[i] < min)
{
min = s[i];
ind = i;
}
}
arr[min - 'a'] = 1;
return ind;
}

void permute(char s[], int m, int n)
{
if(m == n - 1)
{
puts(s);
}

int *arr = (int*) calloc(26, sizeof(int));
int k;
for(int i = m; i < n; i++)
{
k = FindMin(s, arr, m, n);
swap(&s[k], &s[m]);
permute(s, m+1, n);
swap(&s[k], &s[m]);
}
}
int main(void)
{
char s[] = "abcd";
permute(s, 0, strlen(s));
return 0;
}

we can do this easily by using the same general apporach , but one small tweak we need to do is in swap function . while swapping instead a placing the char at some arbitary position we insert it at correct position

Sort the string and use the following code below.

the function is called initially using the parameters

permute(input,b,answer,strlen(input),0)

where b is a boolean array of size strlen(input) all set to 0 and answer is an empty array of size strlen(input).to store intermediate answers.

void permute(char *a,bool b[],char *ans,int size,int pos)
{ 	
	if(size==0)
	{
	  cout<<ans<<endl; 
	  return ;
	}
 	for(int i=0;i<strlen(a);i++)
	{
	   if(b[i]==1 || b[i-1]==0 && a[i-1]==a[i])
	  { 
	    continue;
	  }
	   else
	   {
	    b[i]=1;
	    ans[pos]=a[i];
	    permute(a,b,ans,size-1,pos+1);
	    b[i]=0;
	   }
	}
	return ;
 }

Sort string
apply permutation

Prn()
	for each i from 0 to n-1
		print a[i]
		
P(i)
	if(i == n-1)
		Prn()
	for each j from i+1 to n-1
		P(i+1)
		swap(i, j)

main()
	qSort(a)
	P(0)

Assuming space[] is sorted array of chars

void btrck(char next[],int k,int n)
{
	int i,temp,j;
	if(k>n)
		{
			printf("%s\n",next);
		return ;
		}
	for(j=0;j<3 ;j++)
	{
		if(flag[j]==1) continue;
		flag[j]=1;
		next[k]=space[j];
		btrck(next,k+1,n);
		flag[j]=0;
	}
	
	
}

FINAL ANSWER... RUNNING CODE...

#include<stdio.h>
#include<conio.h>
#include<string.h>
void modify_swap(char ch[], int i, int j)
{

char tmp=ch[j];
while(j>i)
{
ch[j]=ch[j-1];
j--;
}
ch[i]=tmp;
}
void restore(char ch[], int i, int j)
{
char tmp=ch[i];
while(i<j)
{
ch[i]=ch[i+1];
i++;
}
ch[j]=tmp;
}
void lexPerm(char ch[], int l, int i)
{
if(i==l)
{
printf("%s\n",ch);
return;
}
int j=0;
for(j=i;j<l;j++)
{
modify_swap(ch,i,j);
lexPerm(ch,l,i+1);
restore(ch,i,j);
}
}
int main()
{
char ch[5]="1234";
int l=strlen(ch);
lexPerm(ch,l,0);
getch();
return 0;

}