word permutation

[neonblues]

ok guys i think i needed some help here...
im trying to get all possible permutation of a seven-letter word
for example:
char base[] = "drawing";

drawing = (7^7) = 823,543 perms
which means i cant sort another word/s( from 1to7-letter word; just 3 to 7-letter) from drawing
maybe draw, wing, win etc...

i have this code using recursive function but it can only permutate 7-letter perms

example : drawing, rawingd, awingdr, etc...

#include<iostream>
#include<cstring>

using namespace std;

void char_permutation(char str[],char append[])
{
int length = strlen(str);
if (length)
{
for(int i=0;i<length;++i)
{
char* str1 = new char[length+1];
int cnt;
int cnt2;
for(cnt=0,cnt2=0; cnt<length; ++cnt,++cnt2)
{
if (cnt == i)
{
str1[cnt] = str[++cnt2];
continue;
}
else
str1[cnt] = str[cnt2];
}
str1[cnt] = '\0';

int alength = strlen(append);
char* append1 = new char [alength+2];
strncpy(append1,append,alength);
append1[alength] = str[i];
append1[alength+1] = '\0';

char_permutation(str1,append1);

delete []str1;
delete []append1;
}
}
else
{
cout << append << endl;
}
}


int main()
{
char str[] = "drawing"; // shows a little humor
char append[] = "\0";

cout << "Original = " << str << endl;
char_permutation(str,append);
cout << "Done ........" << endl;

cin.get(); // wait
return 0;
}

thank you!!!

[Smok006]

Hello!
First of all u are talking about much more perms that they really are.
1,2,3={(1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)}. Permutation of a number of elements is that number factorial(!).
3!=1*2*3=6
7!(the number of your application)=1*2*...*7=5040.
Generally speaking
n!=1*2*...*n.
If I understand correctly u want to create something like this:
d
d r
d r a
.....
drawing
......
w i n g
w i n g a
....etc. If this is true the easiest method is backtracking. I thing u should find this method explain very well somewhere on this forum. It's a little late for me to explain it now and I don't think I can make u understand me(not your fault but mine's).
If u want (and it will not be to late) I will post here an example of this app.
Regards!


P.S.: http://www.cplusplus.com/forum/general/4902/

[neonblues]

yeah thanks can you post your example?

[buffbill]

There is standard C++ generic algorithm which will do this
Its name is next_permutation and is defined in the 'algorithm' header
As Smok006 says there are 5040 or 7! combinations
e.g.

int main()
{char* s="drawing";
      for(int i=0;i<5040;i++)
       {next_permutation(s,s+7);
         cout<<(i%4?'\t':'\n')<<s;}//print 4  seven char words to a line
}

[Smok006]

Hello again!

If u still want that example here u go, but I think u should listen to buffbill, 'cause that algorithm might work more efficiently. The only problem: it doesn't do what u really want. U must use a loop to get what u want (and I thing is easier this way.)


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

using namespace std;


int stack[100];
char word[100];

//===========================print function=====================================
void print(int k)
{
for(int i=0;i<=k;i++)
cout<<word[stack[i]-1]<<' ';
cout<<endl;
}

//==============================is_ok function==================================
/*Verify if element from "k" position (from stack) was used*/
int is_ok(int k,int min)
{
for(int i=0;i<k;i++)
if(stack[k]==stack[i])
return 0;
return 1;
}

//==============================backtraking-principal function==================
void back(int min, int max, int n)
{
int k=0;
while(k>=0)
if(stack[k]<n)
{

stack[k]++;
if(is_ok(k,min))
{
if((k>=min-1)&&(k<max))//only prints words wuth the imput
print(k); //lenght
stack[++k]=0;
}
}
else k--;

}

//==============================================================================
//-------------------------------MAIN-------------------------------------------
//==============================================================================

int main()
{
int min,max,n;
char c;
cout<<"Please insert the word(or syntax)!\n";
gets(word);
n=strlen(word);
cout<<"How many characters you want at least? For all press 'a'";
// the section above ask u how many char(acter)s at least u want to create words
cin>>c;
if((c=='a')||(c=='A')) //maybe CapsLock is on :D
{
min=n;
max=n;
}
else
{
min=c-48; //this convert u one digit to a "number"(if the
//answer('c') is grater than 9 here u'll got a
//problem u can use atoi() to pass by this "bug");
cout<<"How many characters you want at most? For all press 'a'";
cin>>c;
if((c=='a')||(c=='A'))
max=n;
else
max=c-48;
//u may test if min or max > strlen(word),or if it is any other
//key then 0-9 or a,A etc

}
if (min>max)
{
cout<<"ERROR: min > max!!!";//change the text...
getch();
exit(1);
}
back(min, max,n);
getch();

return 0;
}


Get rid of anything that is useless. And u might want to use pointers! ;))