445,897 Members | 1,955 Online
Need help? Post your question and get tips & solutions from a community of 445,897 IT Pros & Developers. It's quick & easy.

# permutation generation

 P: n/a How to generate different permutations of n char array? ex : for n= 3, and basic string = abc bca cab bac cab ..... ... .. Jun 19 '06 #1
27 Replies

 P: n/a onkar wrote: How to generate different permutations of n char array? ex : for n= 3, and basic string = abc bca cab bac cab .... .. . Go see Google Groups - search comp.lang.c for 'permutations' - finds 250+ results -- ============== Not a pedant ============== Jun 19 '06 #2

 P: n/a onkar said: How to generate different permutations of n char array? ex : for n= 3, and basic string = abc bca cab bac cab Think of your array as being in two parts - the left part and the right part. Initially, the left part is empty. (To keep track, just store the number of elements in the left part.) IF n - left > 0 take the right part, and rotate it one place. Now recurse, for example Permute(s, n, left + 1). Now rotate it back again. ELSE You have a permutation. END IF Have a go at it; if you get stuck, show us your best attempt and we'll do what we can to help you fix it up. -- Richard Heathfield "Usenet is a strange place" - dmr 29/7/1999 http://www.cpax.org.uk email: rjh at above domain (but drop the www, obviously) Jun 19 '06 #3

 P: n/a onkar wrote: How to generate different permutations of n char array? ex : for n= 3, and basic string = abc bca cab bac cab .... .. . Is the array allowed to contain the same character more than once ? If yes do you want all printed permutations to look different from each other or are repeats ok ? Jun 19 '06 #4

 P: n/a Richard Heathfield wrote: Think of your array as being in two parts - the left part and the right part. Initially, the left part is empty. (To keep track, just store the number of elements in the left part.) IF n - left > 0 take the right part, and rotate it one place. Now recurse, for example Permute(s, n, left + 1). Now rotate it back again. ELSE You have a permutation. END IF Have a go at it; if you get stuck, show us your best attempt and we'll do what we can to help you fix it up. I write a function to populate the permutations based on an original string. But it seems that I don't make the logic correct, the function can not get all the permutations. It can only get a part of them, others are missed. Comments are welcome, thanks in advance! #include #include int pmtgen(char *dest[], const char *src) { const int len = strlen(src); char *p = malloc(len + 1); int i, j, k; int cnt = 0; char c; strcpy(p, src); strcpy(*dest++, p); cnt++; /*the original string*/ for (i = 0; i < len; ++i){ for (j = i + 1; j < len; ++j){ /*exchanging*/ p[i] = p[i] + p[j]; p[j] = p[i] - p[j]; p[i] = p[i] - p[j]; strcpy(*dest++, p); cnt++; strcpy(p, src); } if (i != 0 && i != 1){ /*inserting a char at the begining*/ c = p[i]; for (k = i; k > 0; --k){ p[k] = p[k - 1]; } p[0] = c; strcpy(*dest++, p); cnt++; strcpy(p, src); } if (i != len - 1 && i != len - 1 - 1){ /*appending a char at the end*/ c = p[i]; for (k = i; k < len - 1; ++k){ p[k] = p[k + 1]; } p[len - 1] = c; strcpy(*dest++, p); cnt++; strcpy(p, src); } } free(p); return cnt; } #include #define ROW 12 #define COL 5 int main(void) { char *a[ROW]; int cnt; int i, j; for (j = 0; j < ROW; j++){ a[j] = malloc(COL); if (!a[j]){ return 0; } } cnt = pmtgen(a, "abc"); printf("%d permutations: ", cnt); for (i = 0; i < ROW; i++){ printf("%s\t", a[i]); } for (j = 0; j < ROW; j++){ free(a[j]); } printf("\n"); return 0; } \$ gcc -g -W -Wall -pedantic -ansi test.c \$ ./a.out 6 permutations: abc bac cba bca acb cab \$ lovecreatesbeauty Jun 19 '06 #5

 P: n/a lovecreatesbeauty said: I write a function to populate the permutations based on an original string. But it seems that I don't make the logic correct, the function can not get all the permutations. It can only get a part of them, others are missed. Comments are welcome, thanks in advance! cnt = pmtgen(a, "abc"); \$ gcc -g -W -Wall -pedantic -ansi test.c \$ ./a.out 6 permutations: abc bac cba bca acb cab You appear to have found six permutations of the three characters. Which permutations do you think you missed? -- Richard Heathfield "Usenet is a strange place" - dmr 29/7/1999 http://www.cpax.org.uk email: rjh at above domain (but drop the www, obviously) Jun 19 '06 #6

 P: n/a lovecreatesbeauty wrote: I write a function to populate the permutations based on an original string. But it seems that I don't make the logic correct, the function can not get all the permutations. It can only get a part of them, others are missed. Comments are welcome, thanks in advance! for (i = 0; i < len; ++i){ for (j = i + 1; j < len; ++j){ /*exchanging*/ p[i] = p[i] + p[j]; p[j] = p[i] - p[j]; p[i] = p[i] - p[j]; What advantage does that have over: tmp = p[i]; p[i] = p[j]; p[j] = tmp; ? You save one declaration, but you add 3 arithmetic operations, 4 array dereferences, and you make the code less clear. Jun 19 '06 #7

 P: n/a Bill Pursell schrieb: lovecreatesbeauty wrote:I write a function to populate the permutations based on an originalstring. But it seems that I don't make the logic correct, the functioncan not get all the permutations. It can only get a part of them,others are missed. Comments are welcome, thanks in advance! for (i = 0; i < len; ++i){ for (j = i + 1; j < len; ++j){ /*exchanging*/ p[i] = p[i] + p[j]; p[j] = p[i] - p[j]; p[i] = p[i] - p[j]; What advantage does that have over: tmp = p[i]; p[i] = p[j]; p[j] = tmp; ? You save one declaration, but you add 3 arithmetic operations, 4 array dereferences, and you make the code less clear. In addition, you risk signed overflow -- p is a char * and char could be effectively signed char. Cheers Michael -- E-Mail: Mine is an /at/ gmx /dot/ de address. Jun 19 '06 #8

 P: n/a Richard Heathfield wrote: \$ gcc -g -W -Wall -pedantic -ansi test.c \$ ./a.out 6 permutations: abc bac cba bca acb cab You appear to have found six permutations of the three characters. Which permutations do you think you missed? \$ gcc test.c \$ ./a.out 11 permutations: abcd bacd cbad dbca bcda acbd adcb acdb abdc cabd dabc \$ gcc test.c \$ ./a.out 17 permutations: abcde bacde cbade dbcae ebcda bcdea acbde adcbe aecdb acdeb abdce abedc cabde abdec abced dabce eabcd \$ When the length of the base string is 4 or 5 (or more than 3, I guess), e.g. "abcd" or "abcde", the result is not correct. For "abcd", there should be total 24 permutations, for "abcde" 120 permutations (A(m,n) = n! / (n - m)!). I will continue to improve it. Thanks. lovecreatesbeauty Jun 20 '06 #9

 P: n/a pemo wrote: onkar wrote: How to generate different permutations of n char array? ex : for n= 3, and basic string = abc bca cab bac cab .... .. . Go see Google Groups - search comp.lang.c for 'permutations' - finds 250+ results Just give them the code already... http://groups.google.com/group/comp....c0260bb56e83f2 -- Peter Jun 20 '06 #10

 P: n/a "lovecreatesbeauty" wrote in message news:11**********************@u72g2000cwu.googlegr oups.com... Richard Heathfield wrote: > \$ gcc -g -W -Wall -pedantic -ansi test.c > \$ ./a.out > 6 permutations: abc bac cba bca acb cab You appear to have found six permutations of the three characters. Which permutations do you think you missed? \$ gcc test.c \$ ./a.out 11 permutations: abcd bacd cbad dbca bcda acbd adcb acdb abdc cabd dabc \$ gcc test.c \$ ./a.out 17 permutations: abcde bacde cbade dbcae ebcda bcdea acbde adcbe aecdb acdeb abdce abedc cabde abdec abced dabce eabcd \$ When the length of the base string is 4 or 5 (or more than 3, I guess), e.g. "abcd" or "abcde", the result is not correct. For "abcd", there should be total 24 permutations, for "abcde" 120 permutations (A(m,n) = n! / (n - m)!). I will continue to improve it. Thanks. A web search for "permuation algorithm" will turn up plenty of examples. I get 12,900 hits with this: http://www.google.com/search?hl=en&q...n+algorithm%22 lovecreatesbeauty Jun 20 '06 #11

 P: n/a lovecreatesbeauty said: \$ gcc test.c \$ ./a.out 11 permutations: abcd bacd cbad dbca bcda acbd adcb acdb abdc cabd dabc \$ gcc test.c \$ ./a.out 17 permutations: abcde bacde cbade dbcae ebcda bcdea acbde adcbe aecdb acdeb abdce abedc cabde abdec abced dabce eabcd \$ When the length of the base string is 4 or 5 (or more than 3, I guess), e.g. "abcd" or "abcde", the result is not correct. For "abcd", there should be total 24 permutations, for "abcde" 120 permutations (A(m,n) = n! / (n - m)!). I will continue to improve it. I claim no credit for the following code, which I've adapted from "Programs and Data Structures in C", 2nd edition, by Leendert Ammeraal. My contribution was little more than to make it readable. ;-) (I am being unfair to Mr Ammeraal - it's a fine book. I just happen to prefer my way of doing things.) #include #include void Permute(char *Perm, size_t n, size_t unchanged) { size_t outer = 0; size_t inner = 0; int temp = 0; if(unchanged < n) { for(outer = unchanged; outer < n; outer++) { temp = Perm[outer]; for(inner = outer; inner > unchanged; inner--) { Perm[inner] = Perm[inner - 1]; } Perm[unchanged] = temp; Permute(Perm, n, unchanged + 1); for(inner = unchanged; inner < outer; inner++) { Perm[inner] = Perm[inner + 1]; } Perm[outer] = temp; } } else { printf("%s\n", Perm); } } int main(int argc, char **argv) { char Input[256] = {0}; size_t len = 0; if(argc > 1) { len = strlen(argv[1]); if(len > sizeof Input - 1) { fprintf(stderr, "word too long for demo - truncating\n"); argv[1][sizeof Input - 1] = '\0'; } strcpy(Input, argv[1]); len = strlen(Input); } else { len = 3; strcpy(Input, "ABC"); } Permute(Input, len, 0); return 0; } -- Richard Heathfield "Usenet is a strange place" - dmr 29/7/1999 http://www.cpax.org.uk email: rjh at above domain (but drop the www, obviously) Jun 20 '06 #13

 P: n/a Richard Heathfield wrote: I claim no credit for the following code, which I've adapted from "Programs and Data Structures in C", 2nd edition, by Leendert Ammeraal. My contribution was little more than to make it readable. ;-) (I am being unfair to Mr Ammeraal - it's a fine book. I just happen to prefer my way of doing things.) That program fails at this situation which seems to be overcome by CBFalconer's program in another post in this thread. \$ ./a.out ABCC 0: ABCC 1: ABCC 2: ACBC 3: ACCB 4: ACBC 5: ACCB 17: CCBA 23: CCBA \$ lovecreatesbeauty Jun 20 '06 #15

 P: n/a lovecreatesbeauty said: Richard Heathfield wrote: I claim no credit for the following code, which I've adapted from "Programs and Data Structures in C", 2nd edition, by Leendert Ammeraal. My contribution was little more than to make it readable. ;-) (I am being unfair to Mr Ammeraal - it's a fine book. I just happen to prefer my way of doing things.) That program fails at this situation (repeated letter issue) Ah, I didn't realise you needed uniqueness. That isn't a problem I've faced, but I would probably solve it either by pouring the combinations into a binary search tree or by passing the output through sort | uniq, depending on the situation. -- Richard Heathfield "Usenet is a strange place" - dmr 29/7/1999 http://www.cpax.org.uk email: rjh at above domain (but drop the www, obviously) Jun 20 '06 #16

 P: n/a Richard Heathfield wrote: Ah, I didn't realise you needed uniqueness. That isn't a problem I've faced, but I would probably solve it either by pouring the combinations into a binary search tree or by passing the output through sort | uniq, depending on the situation. Yes, thank you. If possible, I would like to read your masterpiece again and see how those magic are applied to the code. Your Sincerely lovecreatesbeauty Jun 20 '06 #17

 P: n/a Richard Heathfield writes: [...] Well, you'd either change printf("%s\n", Perm); to a call to a binary search tree insertion routine, or you'd just let the program run like this: ./perm daddy | sort | uniq or ./perm daddy | sort -u -- Keith Thompson (The_Other_Keith) ks***@mib.org San Diego Supercomputer Center <*> We must do something. This is something. Therefore, we must do this. Jun 20 '06 #19

 P: n/a Richard Heathfield wrote: lovecreatesbeauty said: Richard Heathfield wrote: I claim no credit for the following code, which I've adapted from "Programs and Data Structures in C", 2nd edition, by Leendert Ammeraal. My contribution was little more than to make it readable. ;-) (I am being unfair to Mr Ammeraal - it's a fine book. I just happen to prefer my way of doing things.) That program fails at this situation (repeated letter issue) Ah, I didn't realise you needed uniqueness. That isn't a problem I've faced, but I would probably solve it either by pouring the combinations into a binary search tree or by passing the output through sort | uniq, depending on the situation. That was the script component I mentioned in my post. The OP has obviously not bothered to look up my posting of the code yet. The script part was: sort | uniq | pr -a -T --columns=8 -- "I don't know where bin Laden is. I have no idea and really don't care. It's not that important." - G.W. Bush, 2002-03-13 "No, we've had no evidence that Saddam Hussein was involved with September the 11th." - George Walker Bush 2003-09-17 Jun 20 '06 #20

 P: n/a CBFalconer wrote: That was the script component I mentioned in my post. The OP has Hi, it was not the OP but me has responded to your posts. :) obviously not bothered to look up my posting of the code yet. The script part was: sort | uniq | pr -a -T --columns=8 I would like to see how those "unique" are programmed in your C code but not just in a dummy shell script. :) Yes, if you have done it in C code already. To be frank, the permutation algorithm is a little difficult to me. If I was Newton, I can give a perfect solution quickly on that. I think so. lovecreatesbeauty Jun 21 '06 #21

 P: n/a CBFalconer wrote: [1] c:\dnld\scratch>jumble abcde string="abcde", max=120, len=5 No script here, right? [1] c:\dnld\scratch>jumble abcdd string="abcdd", max=120, len=5 Hint: both a c program and a script are involved. Script is used here, right? Script has its short, it brings your the flaw in the result of your program. I mean the "max=120" is not suitable for the corresponding situation. There will be no such a flaw if it's programmed in C code totally. lovecreatesbeauty -- A baby calf is not afraid of tigers - Saying Jun 21 '06 #22

 P: n/a Groovy hepcat lovecreatesbeauty was jivin' on 20 Jun 2006 18:56:19 -0700 in comp.lang.c. Re: permutation generation's a cool scene! Dig it! CBFalconer wrote: That was the script component I mentioned in my post. The OP hasHi, it was not the OP but me has responded to your posts. :) obviously not bothered to look up my posting of the code yet. The script part was: sort | uniq | pr -a -T --columns=8I would like to see how those "unique" are programmed in your C codebut not just in a dummy shell script. :) Yes, if you have done it in C It's simple, really. It surprised me how simple it was when I figured it out. All you do is sort the substring first; then when rotating, if the same character comes into the initial position of the substring as was there previously, you just keep rotating. To demonstrate this, take the (sorted) string "abbc". Now, on first iteration of the critical loop the permutation is "abbc". Then you rotate the string, and the second iteration yeilds "bbca". Rotate again, and we get "bcab". But, since this string begins with the same letter as the previous one, we skip this one and keep revolving. So we next get "cabb". I hope that makes sense. -- Dig the even newer still, yet more improved, sig! http://alphalink.com.au/~phaywood/ "Ain't I'm a dog?" - Ronny Self, Ain't I'm a Dog, written by G. Sherry & W. Walker. I know it's not "technically correct" English; but since when was rock & roll "technically correct"? Jun 21 '06 #23

 P: n/a lovecreatesbeauty wrote: CBFalconer wrote: That was the script component I mentioned in my post. The OP has Hi, it was not the OP but me has responded to your posts. :) obviously not bothered to look up my posting of the code yet. The script part was: sort | uniq | pr -a -T --columns=8 I would like to see how those "unique" are programmed in your C code but not just in a dummy shell script. :) Yes, if you have done it in C code already. To be frank, the permutation algorithm is a little difficult to me. If I was Newton, I can give a perfect solution quickly on that. I think so. They are NOT in my C code, why should they be? The point of the script is to simply run existing tools so that the combination produces the desired result. -- "I don't know where bin Laden is. I have no idea and really don't care. It's not that important." - G.W. Bush, 2002-03-13 "No, we've had no evidence that Saddam Hussein was involved with September the 11th." - George Walker Bush 2003-09-17 Jun 21 '06 #24

 P: n/a "lovecreatesbeauty" writes: To be frank, the permutation algorithm is a little difficult to me. An alternative approach would be: size = strlen(argv[1]); strcpy(permuted, argv[1]); do { printf("%s\n", permuted); i = size-1; while (i > 0 && permuted[i] <= permuted[i-1]) { --i; } if (i > 0) { j = size-1; while (permuted[j] <= permuted[i-1]) { --j; } tmp = permuted[j]; permuted[j] = permuted[i-1]; permuted[i-1] = tmp; } j = size-1; while (i < j) { tmp = permuted[j]; permuted[j] = permuted[i]; permuted[i] = tmp; ++i; --j; } } while (strcmp(permuted, argv[1]) != 0); and there is no need to filter out duplicates. Yours, -- Jean-Marc Jun 21 '06 #25

 P: n/a lovecreatesbeauty said: CBFalconer wrote: That was the script component I mentioned in my post. The OP has Hi, it was not the OP but me has responded to your posts. :) obviously not bothered to look up my posting of the code yet. The script part was: sort | uniq | pr -a -T --columns=8 I would like to see how those "unique" are programmed in your C code I explained that before. All you have to do is pour them into some kind of container that keeps its contents sorted, such as a binary search tree or a hash table. This will trivially enable you to eliminate duplicates. -- Richard Heathfield "Usenet is a strange place" - dmr 29/7/1999 http://www.cpax.org.uk email: rjh at above domain (but drop the www, obviously) Jun 21 '06 #26

 P: n/a Peter Shaggy Haywood said: It's simple, really. It surprised me how simple it was when I figured it out. All you do is sort the substring first; then when rotating, if the same character comes into the initial position of the substring as was there previously, you just keep rotating. Neat. I hadn't thought of that. It certainly makes anagram generators more practical. I hope you'll accept this biscuit -> O <- for Ronny as a token of thanks. -- Richard Heathfield "Usenet is a strange place" - dmr 29/7/1999 http://www.cpax.org.uk email: rjh at above domain (but drop the www, obviously) Jun 21 '06 #27

 P: n/a Jean-Marc Bourguet wrote: An alternative approach would be: I want to keep this interface in my coming perm() function, like: int perm(char *dest[], const char *src) I've seen lots doesn't use such a interface and use recursive calls like the one provided by Richard in this thread. ... Permute(Perm, n, unchanged + 1); ... Thank you. I'll study your code and want to get inspired from it. lovecreatesbeauty Jun 21 '06 #28

### This discussion thread is closed

Replies have been disabled for this discussion.