Join 136,460 C++ Programmers for FREE! Get instant access to thousands of C++ experts, tutorials, code snippets, and more! There are 1,757 people online right now. Registration is fast and FREE... Join Now!
I am making a little permutation/scrambler app and this is a key part of the code. If someone knows a simple way to find all possible combinations of a string including those that are shorter than the string input, please let me know. Right know I am just running several permutations and alternating the characters input so that all characters are used.
Example, 1234 are input, run permutations of --
234 134 124 123
This is simple when dropping only one character but when dropping 4 from a string of 6... it's a lot of combinations to do manually.
This post has been edited by dwayne: 2 Aug, 2008 - 09:41 PM
Dream.In.Code has a policy by which we prefer to see a good faith effort on your part before providing source code for homework assignments. Please post the code you have written in an effort to resolve the problem, and our members would be happy to provide some guidance. Be sure to include a description of any errors you are encountering as well.
int permute(char* set, int begin, int end) { int i; int range = end - begin; if (range == 1) { cout << set << endl; } else { for(i=0; i<range; i++) { swap(&set[begin], &set[begin+i]); //initial swap permute(set, begin+1, end); //recursion swap(&set[begin], &set[begin+i]); //swap back } } return 0; }
int permutate5(char* p6) { //declare string for 5 character permutations char p5[6] = {p6[1], p6[2], p6[3], p6[4], p6[5], p6[6]}; //exclude element 0 permute(p5, 0, strlen(p5)); //calculate //reset variable will go here and element one of p6 will be excluded return 0; }
int main() { char str[7]; //main string cout << "Please enter a string: "; cin.getline(str, 7); //take string cout << "Permutating \"" << str << "\"" << endl; permute(str, 0, strlen(str)); //permute the string cout << "Calculated all possible 6 character permutations of \"" << str << "\"" << endl; //permutate 2-5 will go here when completed
}
BTW, this is a "personal" project, not my homework. If it were homework, it would be an awful weird assignment. Well, there's the code, so...
Also, how is the source code related to resetting a char variable/pointer?
This post has been edited by dwayne: 2 Aug, 2008 - 06:44 PM
int permute(char* set, int begin, int end) { int i; int range = end - begin; if (range == 1) { cout << set << endl; } else { for(i=0; i<range; i++) { swap(&set[begin], &set[begin+i]); //initial swap permute(set, begin+1, end); //recursion swap(&set[begin], &set[begin+i]); //swap back } } return 0; }
//Example Implementation -- Up to you on how to use int main() { char str[255]; //string cout << "Please enter a string: "; cin.getline(str, 255); //take string permute(str, 0, strlen(str)); //permutate the string return 0; }
edit: You already have string permutes down. Why not just create a new array/string for your thing?
Alternately, I would create a c style string (char array) and only run a loop from the beginning to whatever end point you want.
Another option is setting the pointer back to the original value and using ptr arithmetic go to whatever place you would like.
cpp
//some control structure permute(str, 0, strlen(str-1)) //so on and so forth
Also, thats not really good programming practice.
This post has been edited by KYA: 2 Aug, 2008 - 07:08 PM
edit: You already have string permutes down. Why not just create a new array/string for your thing?
I am not sure what you mean? I am still sending the new array to the same function.
QUOTE(KYA @ 2 Aug, 2008 - 08:05 PM)
Alternately, I would create a c style string (char array) and only run a loop from the beginning to whatever end point you want.
How do I do this?
QUOTE(KYA @ 2 Aug, 2008 - 08:05 PM)
Another option is setting the pointer back to the original value and using ptr arithmetic go to whatever place you would like.
A bit complicated for my purposes, but it is an option.
QUOTE(KYA @ 2 Aug, 2008 - 08:05 PM)
cpp
//some control structure permute(str, 0, strlen(str-1)) //so on and so forth
Also, thats not really good programming practice.
This does not work for me, it outputs nothing and when I feed it a fixed variable it just gives fewer results but still with 6 letters.
Also, is there a truly better way to cut down the length without cutting out any possible results? If I read all this correctly then you are still using my method.
Hmm, I reread your post and you seem to just want to display all possible string permutations, in which case either yours or my code will work just fine for any number of chars within a string.
I don't believe you are understanding now. I need to input 6 letters, it needs to output every possible combination that can be made with those letters down to 2 letter combinations. Also, how do I go about setting a new value to a char array?
EDIT: I fixed the problem of editing the array, I am use to programming in C# but am trying to move to C++ so...
This post has been edited by dwayne: 2 Aug, 2008 - 09:17 PM
Problem solved, I used next_combination along with that bit of permutation code and stuck it in a do-while loop with the next_combination as an argument. It required a new array for every length though that probably could be overcome but right now it will spit out 1950 results in about a second so...
I may post a good tutorial later once I get my program up and running. Thanks for all your help.
Hi OK heres my assignment question- Write a program that, given n and alphabet Z as inputs, outputs all strings of length n over the alphabet Z.
now alphabet here means a string array where for example Z = {a, c} can be an alphabet of 2 symbols and if I want to out all the strings of length 3, this is what I should get (9 strings in total) - aaa aac aca caa acc cac cca ccc
Now i dont have any code as I am still struggling with concepts... First idea I had in mind was like to do a matrix of width n and length = total number of strings.... but, then how do I fill up the matrix??
I have no idea how to approach this problem - there is another idea i came up with which was like initialising the sequence of length n to the first symbol of the alphabet ..But again how would I come around to changing the sequence - I cant figure it out.. any ideas??
| 