1.11M Members

Non recursive implementation of Permutations of a string

 
0
 

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;
}
 
0
 

It doesn't work for any string that has more than 3 characters :S

 
0
 

Changes made and now working for any kind and length of input -- thanks for letting me know it didn't work previously.

 
-1
 
#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();
}
 
0
 

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 ).

Isn't it about time forums rewarded their contributors?

Earn rewards points for helping others. Gain kudos. Cash out. Get better answers yourself.

It's as simple as contributing editorial or replying to discussions labeled or OP Kudos

You
This is an OP Kudos discussion and contributors may be rewarded
Post:
Start New Discussion
View similar articles that have also been tagged: