dave@cs.arizona.edu (Dave P. Schaumann) (01/21/91)
In article <59459@aurs01.UUCP> you write: >I am looking for help on a c programming class assignment. >I am suppose to write a program that takes an input string array, >up to six characters maximum, and print all combinations of the >characters in the string. For example, if "cat" in the input, >the output would be something like this: >cat cta atc act tca tac You will probably hear this quite a lot in the following days: USENET IS NOT THE PLACE TO GET YOUR HOMEWORK DONE FOR YOU!!! If you really can't think of an algorithm, maybe a trip to the library is in order. >Thanks in advance... >*********************************************** >* MARK VARNELL ...mcnc!aurgate!varnell * >*********************************************** Dave Schaumann | And then -- what then? Then, future... dave@cs.arizona.edu | -Weather Report
prg@mgweed.UUCP (Gunsul) (01/22/91)
In article <705@caslon.cs.arizona.edu>, dave@cs.arizona.edu (Dave P. Schaumann) writes: > > In article <59459@aurs01.UUCP> you write: > >I am looking for help on a c programming class assignment. > >I am suppose to write a program that takes an input string array, > >up to six characters maximum, and print all combinations of the > >characters in the string. For example, if "cat" in the input, > >the output would be something like this: > >cat cta atc act tca tac > > You will probably hear this quite a lot in the following days: > > USENET IS NOT THE PLACE TO GET YOUR HOMEWORK DONE FOR YOU!!! > > If you really can't think of an algorithm, maybe a trip to the library is > in order. > > >Thanks in advance... > >*********************************************** > >* MARK VARNELL ...mcnc!aurgate!varnell * > >*********************************************** > > > Dave Schaumann | And then -- what then? Then, future... > dave@cs.arizona.edu | -Weather Report I've seen some other request for help shot down before Mark, maybe you weren't reading this group at the time. I'll probably get flamed for responding, however, it bothers me a little bit that the request for help is 'blown-off' so quickly. On the other hand, a request for help should probably be a bit more specific. If you've worked on the problem for some time and are stuck, you might let people know where you are and what you have done. If you've done nothing and don't want to do anything, the response Dave gave is certainly the correct one. I think the subject has probably been beat to death a few times in this newsgroup judging by some of the responses I've seen. I'll just add my two cents worth then move on to the rest of my posting. If a request for help in this newsgroup came from an individual employed by one of the many businesses on the net, many people would have jumped to offer their clever answer to the problem! I guess what made me respond to this posting is I was talking with my nephew (hi David!) on the phone while reading your article. He convinced me that my first impression was wrong, and that an individual asking for help should be given the benefit of the doubt. Even us "old guys" can learn something from a teenager. Last February I needed a program just like the one you described and thought it would be a simple task to write it. I was wrong again! It sounded sooooo simple -- it's not! It was only simple after I finished it and looked back over what I had written. By the way, I asked everyone I could think of if they had done something similar to what I needed -- nobody shot me down... I'm glad to see you are in a 'C' class, I've been to a couple of them some time back, and think I've learned as much looking at other peoples code and seeing how they did something. I don't think I've ever seen two people code something the same way -- not that one is wrong, just different. I wouldn't have just posted the program I wrote to answer your question, however since I see that someone else already posted something, I'll send what I have. Unfortunately, the manual page doesn't look very good when it's 'nroff'd instead of troff'd. JUMBLE(1L) UNIX System V (LOCAL) JUMBLE(1L) NAME jumble - Arrange characters in all possible combinations SYNOPSIS jumble [-d] [-n] string (2-10 characters long) DESCRIPTION Jumble will output a line of characters for each possible combination of letters input as an argument, up to 10 characters. The length (10) may be changed at compile time to limit the output to something reasonable. Jumble was originally written to generate words for code practice using only characters know by the person learning the code, instead of sending just '5 character code groups' (boring!). The output of jumble was dumped to a file, sorted, run through spell, the misspelled words removed with the 'diff' command, leaving only real words. As the name implies, this program should be helpful when you get stuck playing jumble! OPTIONS Jumble has the following options available: -d Display all combinations, starting with single letters to n letters, allowing letters to be re-used. (d for duplicate letters.) -n Same as the -d options except do not allow letters to be re-used. (n for no duplicates.) ||________________________________________________________________|| ||________________________________________________________________|| || jumble ab | jumble -d ab | jumble -n ab || ||_________________|________________________|_____________________|| ||All combinations | All combinations of | All combinations of|| ||of n letters, no | 1 to n letters with | 1 to n letters with|| ||duplicates. | duplicates. | duplicates. || ||_________________|________________________|_____________________|| || | | || || n! | n | n _______ || || | i R 1 ni | i R 1 (n- i)! || ||_________________|________________________|_____________________|| || ab | a | a || || ba | b | b || || | aa | ba || || | ba | ab || || | ab | || || | bb | || ||_________________|________________________|_____________________|| ||________________________________________________________________|| Page 1 (printed 1/21/91) JUMBLE(1L) UNIX System V (LOCAL) JUMBLE(1L) CAVEATS jumble -d abcdef = 55,986 'words' (380,712 characters) jumble -d abcdefg = 960,799 'words' (7,526,267 characters!) AUTHOR Phil Gunsul, AT&T Information Systems (..!att!mgweed!prg) And here is the code... /* */ /* Jumble -- To compile: */ /* */ /* make jumble */ /* */ /* Manual page: */ /* */ /* tbl jumble.1 | eqn -T(favorite printer) -p11 | troff -man */ /* */ #include <stdio.h> #define SIZE 10 extern int optind; main(argc, argv) char *argv[]; { register int i, j, k, number; int dflg, nflg, backup, length; char buff[SIZE + 2], *ptr[SIZE]; (void)atoi("@(#)jumble 1.0 PRGunsul"); dflg = nflg = 0; while ((i = getopt(argc, argv, "dn")) >= 0) { switch (i) { case 'd': ++dflg; case 'n': ++nflg; break; default: usagexit(argv[0]); } } argv += (optind - 1); argc -= (optind - 1); buff[0] = '\0'; /* '0' the zero element */ strcpy(&buff[1], argv[1]); /* Move string into buffer */ length = strlen(&buff[1]); /* starting in position #1 (not 0!) */ buff[length + 1] = 0x7f; /* Terminate string with '7f' ident */ if (length > SIZE || length < 2 || argc == 1 || optind > 2) usagexit(argv[0]); if (nflg) { for (i = 0; i < SIZE; i++) /* Point ptrs to '0' in array */ ptr[i] = buff; number = 1; } else { for (ptr[0] = &buff[i], i = length - 1, j = 1; i >= 0; i--) ptr[j++] = &buff[i]; /* Preset pointers */ ptr[0] = buff; number = length; } i = 0; while (i < length) { /* Loop until we run out of characters! */ ptr[i]++; if (*ptr[i] == 0x7f) { ptr[i++] = &buff[1]; if (i == number) /* incr. number of char. displayed */ number = i + 1; continue; } if (!dflg) { /* This loop will detect a pointer (least significant) */ /* that is pointing at the same letter as a more significant */ /* pointer. If a duplicate is found, go back up to the */ /* 'while' loop and check for the 'terminator'. */ backup = i = 0; k = number - 1; while (i < k) { for (j = i + 1; j < number; j++) if ( ptr[i] == ptr[j]) { backup++; k = 0; break; } i++; } if (backup) { --i; /* Move to correct pointer */ continue; } } /* Output a line */ for (i = 0; *ptr[i]; i++) /* print using the pointers */ putchar(*ptr[i]); putchar('\n'); i = 0; /* Point to least sig. pointer */ } } usagexit(ptr) char *ptr; { fprintf(stderr, "%s%s%s%d%s%s%s", "usage: ", ptr, " [ -d ] [ -n ] string (2 - ", SIZE, " characters)\n", " -d all combinations including Duplicate letters\n", " -n all combinations No duplicate letters\n"); exit(1); } That's it... Sorry if I rambled on... -- AT&T | This space | (708)-859-4485 Phil Gunsul | intentionally | prg@mgweed.ATT.COM Montgomery, IL | left blank.. | AT&T Information Systems