re: permutations in C language,,not C++, a subset of the C++

[boredstudent3]

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]

http://mathforum.org/dr.math/faq/faq.comb.perm.html

[boredstudent3]

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]

one way is to recursively build the permutaions
for example using characters...

code:

#include <stdio.h> #include <string.h> 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]

search for SEPA algorithm

[boredstudent3]

-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]

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]

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]

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]

While you should still give credit where it's due, implementing an algorithm is not the same as copying and pasting code.[/u]

[bugzpodder]

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]

bugzpodder wrote:

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]

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-