DaniWeb IT Discussion Community - Code Snippet Non recursive or no recursion implemetation of Permutations of a string

DaniWeb IT Discussion Community (http://www.daniweb.com/forums/index.php)

- C (http://www.daniweb.com/forums/forum118.html)

- - Code Snippet: Non recursive or no recursion implemetation of Permutations of a string (http://www.daniweb.com/forums/thread216767.html)

~s.o.s~

Aug 6th, 2006 4:58 pm

Non recursive or no recursion implemetation of Permutations of a string

Hello friends 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 feedbacks, constructive criticisms 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;
}

Windsurfer

Oct 1st, 2006 8:32 pm

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

~s.o.s~

Oct 29th, 2006 2:03 pm

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

dileepkumar235

Jan 18th, 2009 12:10 pm

#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[i]=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();
}

All times are GMT -4. The time now is 1:53 am.