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.

Edited by ~s.o.s~: remove typo from title

// 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;
}
4
Contributors
4
Replies
12
Views
11 Years
Discussion Span
Last Post by samir1
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();
}

Edited by happygeek: fixed formatting

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

Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.