need way to find all character combinations in a
Gunsul
prg at mgweed.UUCP
Tue Jan 22 15:35:47 AEST 1991
In article <705 at caslon.cs.arizona.edu>, dave at cs.arizona.edu (Dave P. Schaumann) writes:
>
> In article <59459 at 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 at 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 at mgweed.ATT.COM
Montgomery, IL | left blank.. | AT&T Information Systems
More information about the Comp.lang.c
mailing list