Hello here i am posting the non recursive or no recursion implementation of outputting Permutations of a string as compared to the recursive implementations previously posted.
Any feedback, constructive criticism or comments are most welcome.
Hello here i am posting the non recursive or no recursion implementation of outputting Permutations of a string as compared to the recursive implementations previously posted.
Any feedback, constructive criticism or comments are most welcome.
// permutations of any string inputted by user //
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define display(X) printf( "\n%s", X );
static int counter = 1 ;
/**
* This function is used to remove the trailing new line which is normally present at the end of the string accepted from the user
* using fgets( ). This function is very important since without this the newline character at the end of the input will be considered
* while drawing out permutations of the string which we dont want.
*
* @author ~s.o.s~
* @param input C style string from which the trailing newline has to be removed.
*/
void remove_newline( char* input )
{
char* p = 0 ;
if( p = strrchr( input, '\n' ) )
*p = '\0' ;
}
/**
* This function is used to swap the two characters in the string array under consideration.
*
* @author ~s.o.s~
* @param a - character pointer pointing at the character to be swapped.
* @param b - character pointer pointing at the character to be swapped with.
*/
void swapPlaces (char* a, char* b)
{
char temp = *a;
*a = *b;
*b = temp;
}
/**
* The algorithm used for permutations of the string is an adaptation of the "Countdown Quickperm algorithm"
* by Mr. Phillip Paul Fuchs. The credit for this algo goes to him.
*
* @author ~s.o.s~
* @param input which is the old C style string holding the string which has to be permuted
*/
void wordPermutation (const char* input)
{
int string_length = strlen( input ) ;
if ( string_length == 0) // guard against no input
return ;
int* p = (int*) malloc( string_length + 1 ) ;
// start of naked block meant for initializing array P
{
int j ;
for( j = 0; j <= string_length; ++j )
p[j] = j ;
}
// end of naked block
char* tempBuffer = (char*) malloc( string_length + 1 ); // dont affect the original string, create temporary string.
strcpy (tempBuffer, input);
printf( "\n%s", tempBuffer ) ;
/// core algorithm begins
int i = 1, j = 0;
while(i < string_length)
{
p[i]--;
j = i % 2 * p[i];
swapPlaces( &tempBuffer[i], &tempBuffer[j] ) ;
counter++ ;
display(tempBuffer);
i = 1;
while (!p[i])
{
p[i] = i;
i++;
}
}
/// core algorithm ends
free( tempBuffer ) ;
free( p ) ;
printf( "\n\nThe number of permutations is %d\n\n", counter ) ;
}
int main ( )
{
char buffer[BUFSIZ] = {'\0'} ;
printf ("\nEnter the string whose permutation u want: ");
fgets (buffer, BUFSIZ, stdin);
remove_newline (buffer);
wordPermutation (buffer);
return 0;
}
It doesn't work for any string that has more than 3 characters :S
Changes made and now working for any kind and length of input -- thanks for letting me know it didn't work previously.
#include <conio.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
void main()
{
char a[20],st_char;
static int i,j,k,n,st,ctr,main_ctr;
printf("Enter the string : ");
gets(a);
n=strlen(a);
if(n<=1)
{
printf("please enter a valid string :) ");
exit(0);
}
label :
for(i=0;i<=n-2;++i)
{
ctr=0;
printf("\n");
printf("%c",a[0]);
for(j=i+1;j<=n-1;j++)
{
printf("%c",a[j]);
ctr++;
}
if(ctr!=n-1)
//while(ctr!=n-1)
{
st=i+1;
for(k=1;k<=st-1;k++)
{
printf("%c",a[k]);
ctr++;
}
}
}
st_char=a[0];
for(i=0;i<=n-2;i++)
a=a[i+1];
a[n-1]=st_char;
main_ctr++;
while(main_ctr<n)
goto label;
printf("Designed by Uday kumar and Dileep Basam ");
getch();
}
There is a memory related issue in line no 53
int* p = (int*) malloc( string_length + 1 ) ;
Allocate memory for size of integer times (string_length + 1)
int* p = (int*) malloc( sizeof(int)*(string_length + 1) ) ;
or replace int* with unsigned char* which will limit the string_length to 255(Unsigned Char has max value of 255 ).
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.