----------------------------------- boredstudent3 Sun Nov 14, 2004 11:41 pm re: permutations in C language,,not C++, a subset of the C++ ----------------------------------- hello folks...i need to determine the different combinations when given a set of numbers and order does matter so essentially what i need to do is find all the sets,,don't know if that makes sense or not but i know when doing permutations by hand u can obviously write out all the different combinations but how can u do such a thing in C?...like i'm pretty sure that i'll have to use a loop to iterate through all the permutations and possibly an if statement to check for repetitions but how do i actuallly go about attaining the combinations? thanks for your time boredstudent3- ----------------------------------- wtd Mon Nov 15, 2004 1:00 am ----------------------------------- http://mathforum.org/dr.math/faq/faq.comb.perm.html ----------------------------------- boredstudent3 Wed Nov 17, 2004 11:40 am ----------------------------------- hmmm,,thanks for your reply wtd but i don't need to find the number of possible permutations,,instead say if i was given the set of numbers {1,2,3} i need to write a prgm to get the combinations such as: 123 132 213 231 321 312 ...how do i go about getting these sets?...=p...argh,prgm'ing is not my cup of tea...bleh,,=) ----------------------------------- md Wed Nov 17, 2004 4:27 pm ----------------------------------- one way is to recursively build the permutaions for example using characters... #include #include void GeneratePermutaions(char *start, char *values) { // a buffer to hold the start string, plus one more character char *buf = new char[strlen(start) + 2]; // create a new character array to hold the new possible values char *nv = new char[strlen(values)]; if( strlen(values) > 1) { // for each item in value... for( int i = 0; i < strlen(values); i++) { // empty the new value string nv[0] = '\0'; // copy all the values in values to nv except values[i] for( int j = 0; j < strlen(values); j++) { if( j != i) { char b[2]; b[0] = values[j]; b[1] = '\0'; strcat(nv, b); } } // set buf to start strcpy(buf, start); // now add values[i] to buf (use a copy, tis easier char b[2]; b[0] = values[i]; b[1] = '\0'; strcat(buf, b); // now keep generating GeneratePermutaions(buf, nv); } } else { // if strlen(values) == 1 // concatenate v to start, and print it strcpy(buf, start); strcat(buf, values); printf("%s\n", buf); } delete buf; delete nv; } int main(int argc, char* argv[]) { // generate the permutaions of the string 123 GeneratePermutaions("", "123"); return 0; } generates: 123 132 213 231 312 321 ** if this is for an assigment then you'd better not submit this... ----------------------------------- bugzpodder Wed Nov 17, 2004 5:09 pm ----------------------------------- search for SEPA algorithm ----------------------------------- boredstudent3 Sat Nov 20, 2004 12:27 am ----------------------------------- -wow,,thanks alot for the ideas corkflake,,i appreciate it pal -no,,even though this is for an assignment i won't submit the code which u have posted b/c plagiarism has a very hefty price in uni,,heh... -hey bugz why is the relevence of searching SEPA?...is this an acroynm?...=),,nm bugz...SEPA = simple efficient permutation algorithm...hehe,,awesome tip man...thanks alot!!! ----------------------------------- bugzpodder Sat Nov 20, 2004 12:31 am ----------------------------------- fine, dont search for SEPA algorithm which is an algorithm to generate all permutations effeciently in O(1) time (per permutation) without overhead of recursion or excessive data structures ----------------------------------- boredstudent3 Sat Nov 20, 2004 3:56 pm ----------------------------------- wait, lemme get this straight,, bugz is SEPA "code" that alot of programmers use?,,cuz i'm doing this for an assignment and if isn't sth which is common to programmers then i don't think i should use it cuz it could constitute as plagerism correct?...=( ----------------------------------- bugzpodder Sat Nov 20, 2004 4:05 pm ----------------------------------- you think you can just take the code and claim it as yours without referencing it? OF COURSE NOT. you reference where you got the code from if you didnt come up with it. ----------------------------------- wtd Sat Nov 20, 2004 7:28 pm ----------------------------------- While you should still give credit where it's due, implementing an algorithm is not the same as copying and pasting code.[/u] ----------------------------------- bugzpodder Sat Nov 20, 2004 9:05 pm ----------------------------------- if you notice, it is SEPA "code", not SEPA algorithm, as I believe all the resources in google gives you the algorithm in C code rather than pseudocode. And taking other's code and change the variable names does not make it your own code, it is still plagiarism ----------------------------------- wtd Sat Nov 20, 2004 9:46 pm ----------------------------------- if you notice, it is SEPA "code", not SEPA algorithm, as I believe all the resources in google gives you the algorithm in C code rather than pseudocode. And taking other's code and change the variable names does not make it your own code, it is still plagiarism Honestly, in this case I think it would be sufficient to credit the author with the algorithm. Especially when one is shooting for efficiency and speed, there just aren't that many ways to write this one, especially in C. ----------------------------------- boredstudent3 Sun Nov 21, 2004 1:07 am ----------------------------------- well thanks alot guys for your posts,, in the end i managed to write the code myself using a different method and this is just an introductory programming course which i have to take so the instructor is not looking for efficiency (length of code, amount of memory i use, number of vars, etc). bored-