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;
} 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:
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.sizeof(*ptr) * count. For stack-free solutions, you do not need extra arrays anyway; just swap in-place.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.
It doesn't work for any string that has more than 3 characters :S
Changes made and now working for any kind and length of input -- thanks for letting me know it didn't work previously.
#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();
}
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 ).
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.