wsl@eosp1.UUCP (Warren Lobel) (12/12/84)
My friends and I have come across an interesting coding problem. We are trying to write a program that given a string of digits (or letters) of length N will generate all N factorial permutations of those digits. For example: For the word 'cat' the program will generate the following: cat cta act atc tca tac The ordering is arbitrary and should be dependent on the algorithm used. At first this seems to be a rather trivial task, however, it is much more difficult then it appears to be initially. I would appreciate any help in writing this algorithm, preferrably in 'C' but any language (though I suspect a language that can handle recursion is best) will do. Please mail me the solution or at least which newsgroup it is posted in. Thanks a lot Warren S. Lobel Exxon Office Systems Princeton, NJ
lip@masscomp.UUCP (John Lipinski) (12/13/84)
For Warren Lobel at Exxon Office Systems, who requested a solution
to the permutation problem. The following C program takes a string
as an argument and prints out the list of permutations. It is a very
interesting algorithm.
- John Lipinski
------------------------------------------------------------------------
/* permutate: prints a list of all possible permutations of a string. */
/* usage: permutate string */
main(argc,argv)
int argc;
char **argv;
{
char *word, *malloc();
if (argc < 2) exit(1);
word = malloc(strlen(argv[1]) + 2);
strcpy(word,argv[1]);
permutate(word,strlen(word)-1);
}
permutate(word,right)
char word[];
int right;
{
int left;
if (right > 0) {
for(left = right; left >= 0; left--) {
swap(word,left,right);
permutate(word,right-1);
swap(word,left,right);
}
return;
} else
printf("%s\n",word);
}
swap(s,l,r)
char s[];
int l, r;
{
char c;
c = s[l];
s[l] = s[r];
s[r] = c;
}lwall@sdcrdcf.UUCP (Larry Wall) (12/15/84)
In article <174@masscomp.UUCP> lip@masscomp.UUCP (John Lipinski) writes: >For Warren Lobel at Exxon Office Systems, who requested a solution >to the permutation problem. The following C program takes a string >as an argument and prints out the list of permutations. It is a very >interesting algorithm. Yes, it is interesting. It looks suspiciously like a change ringing algorithm. Can any of you Anglophiles confirm that? For that matter, can any of you Angles across the water confirm it? (Or do Angles qualify as Anglophiles?) For those of you who haven't heard of change ringing, it is an artform practiced by the British in which a set of tuned bells is rung through all possible permutations. For an enjoyable introduction to the topic I would recommend the mystery novel The Nine Tailors by Dorothy L. Sayers. Larry Wall {allegra,burdvax,cbosgd,hplabs,ihnp4,sdcsvax}!sdcrdcf!lwall
gwyn@brl-tgr.ARPA (Doug Gwyn <gwyn>) (12/18/84)
There is a permutation generator in the Collected Algorithms of ACM
(long ago, so probably in the bound Vol. 1).
You can also design a permutation generator by recursive application
of the rule:
Perm( N ) = { N-inserted-at-each-position-in-Perm( n-1 ) }
This makes a pleasant programming exercise.kay@flame.UUCP (Kay Dekker) (12/21/84)
[nil] >Yes, it is interesting. It looks suspiciously like a change ringing >algorithm. Can any of you Anglophiles confirm that? For that matter, >can any of you Angles across the water confirm it? (Or do Angles qualify >as Anglophiles?) Yes, this is indeed a change-ringing algorithm. I wrote a nicer-looking one in algol-68 z-quillion years ago on a Dec-10. Are we the only nation to indulge in the joyful art of change-ringing? Kay. (non Angeli, sed Angli) ... -- "But what we need to know is, do people want nasally-insertable computers?" ... mcvax!ukc!flame!kay
ken@turtlevax.UUCP (Ken Turkowski) (01/02/85)
What is change-ringing?
--
Ken Turkowski @ CADLINC, Menlo Park, CA
UUCP: {amd,decwrl,nsc,spar}!turtlevax!ken
ARPA: turtlevax!ken@DECWRL.ARPA