** Some Help Please **
der Mouse
mouse at thunder.mcrcim.mcgill.edu
Fri Jun 7 23:43:09 AEST 1991
In article <12007 at skye.cs.ed.ac.uk>, sam at 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 at larry.mcrcim.mcgill.edu
More information about the Comp.lang.c
mailing list