Non recursive implementation of Permutations of a string

Updated ~s.o.s~ 0 Tallied Votes 2K Views Share

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

Dani AI

Generated

Nice idea, . If you want a simple, non-recursive approach that scales beyond 3 chars (as flagged) and avoids deep call stacks, implement the classic lexicographic next_permutation. Start by sorting the string. Then, repeatedly transform it to the next permutation in-place and print until there is no next one. This runs in O(n! * n), uses O(1) extra space, and naturally handles duplicates: starting from the sorted string yields each distinct arrangement exactly once.

Here is a tiny, drop-in C helper you can call in a loop after printing the initial, sorted string:

// returns 1 if advanced, 0 if it was the last permutation
int next_permutation(char *s, size_t n) {
    if (n < 2) return 0;
    size_t i = n - 1;
    while (i > 0 && s[i - 1] >= s[i]) --i;
    if (i == 0) return 0;
    size_t j = n - 1;
    while (s[j] <= s[i - 1]) --j;
    char t = s[i - 1]; s[i - 1] = s[j]; s[j] = t;
    for (size_t a = i, b = n - 1; a < b; ++a, --b) { t = s[a]; s[a] = s[b]; s[b] = t; }
    return 1;
}

Notes specific to posts above:

  • : replace gets with fgets, return int main(void), and drop conio.h for portability. Also, a = a[i+1]; assigns to an array (illegal); swap characters instead. Gotos and many static locals make control flow brittle here.
  • ’s point stands: always allocate using sizeof(*ptr) * count. For stack-free solutions, you do not need extra arrays anyway; just swap in-place.
  • Testing tip: verify for strings with duplicates (e.g., "aabc") and for length > 3 to ensure ordering and counts are correct.

The same algorithm maps cleanly to Python if you prefer that tag, but the C version above meets the non-recursive goal and is easy to drop into your program.

Windsurfer 0 Newbie Poster

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

~s.o.s~ 2,560 Failure as a human Team Colleague Featured Poster

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

dileepkumar235 -5 Newbie Poster
#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();
}
samir1 0 Newbie Poster

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

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.