1,105,409 Community Members

Non recursive implementation of Permutations of a string

Member Avatar
(~s.o.s~)
Reputation Points: 2,496 [?]
Q&As Helped to Solve: 992 [?]
Skill Endorsements: 72 [?]
 
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;
}
Member Avatar
Windsurfer
Newbie Poster
3 posts since Oct 2006
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

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

Member Avatar
~s.o.s~
Failure as a human
10,399 posts since Jun 2006
Reputation Points: 2,496 [?]
Q&As Helped to Solve: 992 [?]
Skill Endorsements: 72 [?]
Administrator
Featured
 
0
 

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

Member Avatar
dileepkumar235
Newbie Poster
13 posts since Jan 2009
Reputation Points: -5 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
-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();
}
Member Avatar
samir1
Newbie Poster
1 post since Feb 2010
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
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 ).

You
Post:
Start New Discussion
View similar articles that have also been tagged: