simple program to find permutation of all letters of a word

Question

code2cplus 0 Newbie Poster

20 Years Ago

a simple program to find out the permutations of all the letters in the word

ex:
abc gives

abc
acb
bac
bca
cba
cab

void swap(char *p,char *q){
char c;
c=*p;
*p=*q;
*q=c;
}



void perm(char *a,int m,int n)
{

   if(m==n){
for(int i=0;i<=n;i++)
  cout<<a[i];
    }

else
{
for(int j=n;j<=m;j++)
{
swap(a[j],a[n]);
perm(a,m,n+1);
swap(&a[j],&a[n]);
}

}



int main()
{
  char *a = "haia";
 perm(a,strlen(a)-1,0);
getch();
return 0;
}

c c++

12 Contributors
12 Replies
699 Views
7 Years Discussion Span
Latest Post 12 Years Ago Latest Post by Assembly Guy

Dani AI

Generated 10 Months Ago

This thread highlights two common pitfalls when writing permutations code in C/C++. 's original attempt passed characters where the swap routine expected pointers; correctly flagged that mismatch. also reminded everyone that trying to modify a string literal is undefined behavior. The practical fixes are: work on a writable buffer (or use std::string) and keep the swap/backtrack pair intact so each recursive branch restores the array for the next iteration.

The idea behind the algorithm is simple backtracking: pick a position, try every candidate character in that position, recurse to fill the next position, then undo the change (swap back). That final swap is not optional — without it later iterations see a mutated array and results are wrong or duplicated (this explains 's surprise). If the input contains repeated letters, you will also get repeated outputs unless you deduplicate (skip equal characters at a given level or collect results into a set).

If you can use C++, prefer the STL: sort the string then iterate with std::next_permutation to produce each distinct permutation exactly once. Example:

#include <algorithm>
#include <iostream>
#include <string>

int main() {
    std::string s = "aba"; // input
    std::sort(s.begin(), s.end());
    do {
        std::cout << s << '\n';
    } while (std::next_permutation(s.begin(), s.end()));
}

For a pure C solution, allocate a writable char array (not a literal), implement a swap that operates on indices or references, recurse with explicit start/end indices, and always swap back after recursion. Replace unsafe helpers like gets() or nonstandard getch() with fgets/scanf or std::getline.

Finally: watch the factorial explosion — printing all permutations is only practical for very small strings (roughly n <= 8–10). For the "pronounceable" filter (), follow 's idea: generate candidates and then filter them with a small list of allowed digraphs/syllable rules rather than trying to bake full phonetics into the generator.

All 12 Replies

~s.o.s~ 2,560 Failure as a human

20 Years Ago

Please my friend try ur code before posting it on the forum so that other ppl are not misled.

THe code u have posted doesnt work.

jephthah 1,888 Posting Maven

16 Years Ago

Hi friends... This works.. Try out..
Its the corrected one

so, when you say "works" ... you really mean "crashes with a fatal runtime error", right?

thanks for resurrecting a 4 year old thread to post your non-working crap code.

Solicko 3 Newbie Poster

16 Years Ago

Guys, in strict C code you cant do char *a = "hai"; without first allocating the necessary memory for it. Either use malloc function, or change the line to : char a[3] = "hai";

tesuji commented: for beating the masters :) +3

Reply to this topic

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.

roverphoenix 0 Newbie Poster · Answer 1 · 2006-08-22T22:00:28+00:00

dude

void swap(char *p,char *q) , thts the function def, how are you calling it
swap(a[j],a[n]);?? , the function expects a pointer not a chracter, no wonder it crashes

binoy.jayan -1 Newbie Poster · Answer 2 · 2010-04-06T11:09:49+00:00

Hi friends... This works.. Try out..
Its the corrected one

#include<stdio.h>
#include<string.h>

   void swap(char *p,char *q)
   {
   char c;
   c=*p;
   *p=*q;
   *q=c;
   }
   
  void perm(char *a,int m,int n)
  {
	int i,j;
  	if(m==n)
  	{
  	for(i=0;i<=n;i++)
  		printf("%c", a[i]);
	printf("\n");
  	}
  	else
  	{  
  	for(j=n;j<=m;j++)
  	{
  		swap(&a[j],&a[n]);
 	 	perm(a,m,n+1);
  		swap(&a[j],&a[n]);
  	}
  	}
  }

  int main()
  {
  char *a = "hai";
  perm(a,strlen(a)-1,0);
  getch();
  return 0;
  }

Nick Evan 4,005 Industrious Poster Team Colleague Featured Poster · Answer 3 · 2010-04-09T02:11:07+00:00

so, when you say "works" ... you really mean "crashes with a fatal runtime error", right?
thanks for resurrecting a 4 year old thread to post your non-working crap code.

I guess it could be worse... The swap function uses a temp-var instead of the xor-swap for example?

binoy.jayan -1 Newbie Poster · Answer 4 · 2010-07-10T22:08:49+00:00

Hi Jephthah, I appologize if the code I posted doesnt work.
I ran a few test cases and it was woking fine. Thats why I posted it.

thejokerguy 0 Newbie Poster · Answer 5 · 2010-09-27T16:13:33+00:00

I put a[10] and removed calling second swap function.
It's Working! Thanks.But I didn't get the logic of this program.
Can somebody please explain?

#include<stdio.h>
#include<string.h>

   void swap(char *p,char *q)
   {
   char c;
   c=*p;
   *p=*q;
   *q=c;
   }
   
  void perm(char *a,int m,int n)
  {
	int i,j;
  	if(m==n)
  	{
  	for(i=0;i<=n;i++)
  		printf("%c", a[i]);
	printf("\n");
  	}
  	else
  	{  
  	for(j=n;j<=m;j++)
  	{
  		#include<stdio.h>
#include<string.h>

   void swap(char *p,char *q)
   {
   char c;
   c=*p;
   *p=*q;
   *q=c;
   }
   
  void perm(char *a,int m,int n)
  {
    int i,j;
      if(m==n)
      {
      for(i=0;i<=n;i++)
          printf("%c", a[i]);
    printf("\n");
      }
      else
      {  
      for(j=n;j<=m;j++)
      {
          swap(&a[j],&a[n]);
          perm(a,m,n+1);
          	[B]//swap(&a[j],&a[n]);[/B]
      }
      }
  }

  int main()
  {
  char a[10] = "swap";
  perm(a,strlen(a)-1,0);
  //getch();
  return 0;
  }
  		
  	}
  	}
  }

  int main()
  {
  char a[10] = "swap";
  perm(a,strlen(a)-1,0);
  //getch();
  return 0;
  }

ragziraghu 0 Newbie Poster · Answer 6 · 2010-10-30T00:15:44+00:00

ragziraghu 0 Newbie Poster

15 Years Ago

binoy.jayan's corrected code works fine.

bharadwaj.p.s 0 Newbie Poster · Answer 7 · 2011-04-06T14:44:24+00:00

Hai can any one modify this code to produce the combination that will be able to pronounce? I mean if the input is abc then it should produce cab and bac only. not all of it.

Mehdi_1 0 Newbie Poster · Answer 8 · 2013-11-29T22:13:57+00:00

this is my code

#include <stdio.h>
#include <string.h>
#include <conio.h>

int main(){
    char x[40],b;
    int i,j,l;
    puts("enter string :");
    gets(x);
    j = (strlen(x) -1)*strlen(x);
    i=0;
    l=0;
    for(i=0;i<j/2;i++){

        for(l=0;l<strlen(x)-1;l++){
            b = x[l];
            x[l] = x[l+1];
            x[l+1] = b;
            x[strlen(x)] = '\0';
            puts(x);
        }
    }
    getchar;
    return 0;
}

Assembly Guy 72 Posting Whiz · Answer 9 · 2013-11-29T22:50:50+00:00

Hai can any one modify this code to produce the combination that will be able to pronounce? I mean if the input is abc then it should produce cab and bac only. not all of it.

To do this, you'd have to sit down and write out pairs (maybe even triplets) of letters which are pronouncable. You'd then have to create an array of these in your program and go from there... Unfortunately, it's not an overly easy or quick task.

simple program to find permutation of all letters of a word

Dani AI

Recommended Answers Collapse Answers

All 12 Replies

Recommended Answers