sam@cs.ed.ac.uk (S Manoharan) (06/05/91)
There is a wee problem I want to solve. There are `m' mailboxes
(named 0 to m-1) which get `n' mails (named 0 to n-1) over a
period of time. I want to generate all the possible ways of these
mails arriving at the mailboxes. There should be
factorial(n) * pow(m, n) possibilities.
For instance, if m = 2 and n = 2 then the possibilities would be
[m0: 0, 1; m1: -] [m0: -; m1: 0, 1] [m0: 0; m1: 1]
[m0: 1, 0; m1: -] [m0: -; m1: 1, 0] [m0: 1; m1: 0]
All I want is to print these possibilites for any given values
(small, say, <= 10) of `m' and `n'.
Can anyone help me to get hold of a C code or an algorithm to
tackle this. It seems to beat me.
Thanks in advance.
Ps - Sorry, if I am posting this to a wrong newsgroup.
--
S Manoharan Bitnet : sam%lfcs.ed.ac.uk@ukacrl.bitnet
Dept of Computer Science Uucp : sam%lfcs.ed.ac.uk@ukc.uucp
University of Edinburgh Fax : +44 31 667 7209
Edinburgh EH9 3JZ UK. Voice : +44 31 650 5115 (Office)eoo@let.rug.nl (Eize Oosting) (06/07/91)
In article <12007@skye.cs.ed.ac.uk> sam@lfcs.ed.ac.uk (S Manoharan) writes: > [Stuff deleted] > >Can anyone help me to get hold of a C code or an algorithm to >tackle this. It seems to beat me. > >Thanks in advance. > >Ps - Sorry, if I am posting this to a wrong newsgroup. > Yes, you should have send this to the following newsgroup: someone.stupid.enough.to.do.my.homework.?.please.be.! It's a problem which requires about 3 or 4 for() loops. It's too simple. /\__________/\ /\___________________________________________________/\ / \ / \ | Letteren- | Marvin Minsky once defined Artificial Intelligence as: | | Faculteit | '... the science of making machines do things that | | R.U. Groningen | would require intelligence if done by men'. | | The Netherlands| | | | Does this include formatting a floppy? | | eoo@let.rug.nl | Eize Oosting | \ __________ / \ ___________________________________________________ / \/ \/ \/ \/
mouse@thunder.mcrcim.mcgill.edu (der Mouse) (06/07/91)
In article <12007@skye.cs.ed.ac.uk>, sam@cs.ed.ac.uk (S Manoharan) writes: > There is a wee problem I want to solve. There are `m' mailboxes > (named 0 to m-1) which get `n' mails (named 0 to n-1) over a period > of time. I want to generate all the possible ways of these mails > arriving at the mailboxes. This isn't a C question; this is an algorithms question, and a rather elementary one at that. > There should be > factorial(n) * pow(m, n) possibilities. Yes and no. There are n! m^n ways of the letters arriving in the mailboxes, but in your notation for printing the results these aren't all different. > For instance, if m = 2 and n = 2 then the possibilities would be > [m0: 0, 1; m1: -] [m0: -; m1: 0, 1] [m0: 0; m1: 1] > [m0: 1, 0; m1: -] [m0: -; m1: 1, 0] [m0: 1; m1: 0] Well, that agrees with neither the formula you gave (2! * 2^2 = 8) or my program below (which does however produce only six *different* lines of output). I won't explain why; see the next paragraph. In case this is, as I suspect, a homework problem, I've left a bug in. The basic algorithm is sound, but I want to make sure you don't pass a homework assignment without learning anything from it. (You need to fix the bug to get the output I mentioned above.) On the assumption that N is a compile-time constant, and that M fits in a char, here it is. Note that the coding style is not entirely to be recommended; in particular, it is under-commented and excessively compact. It's just a straightforward enumeration of M^N, and then for each of those, an equally straightforward enumeration of N!. You don't want to try this for M and N over about 4. The combinatorial explosion gets bad - work out values with that formula you gave: M=N=5, total=375000; M=N=6, total=33592320.... char b[N]; char t[N]; char o[N]; printways_(n) int n; { int i; if (n < 0) { int m; for (m=0;m<M;m++) { printf("%sm%d: ",m?"; ":"[",m); i = 0; for (n=0;n<N;n++) if (b[n] == m) printf("%s%d",i++?", ":"",o[n]); if (! i) printf("-"); } printf("]\n"); } else { for (i=0;i<N;i++) { if (! t[i]) { o[n] = i; t[i] = 1; printways_(n-i); t[i] = 0; } } } } printways() { int i; bzero(&b[0],N); bzero(&t[0],N); do { printways_(N-1); for (i=0;(i<N)&&((++b[i])>=M);i++) b[i] = 0; } while (i < N); } der Mouse old: mcgill-vision!mouse new: mouse@larry.mcrcim.mcgill.edu