Newsgroups: comp.lang.c
Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!think.com!snorkelwacker.mit.edu!thunder.mcrcim.mcgill.edu!mouse
From: mouse@thunder.mcrcim.mcgill.edu (der Mouse)
Subject: Re: ** Some Help Please **
Message-ID: <1991Jun7.134309.21475@thunder.mcrcim.mcgill.edu>
Organization: McGill Research Centre for Intelligent Machines
References: <12007@skye.cs.ed.ac.uk>
Date: Fri, 7 Jun 91 13:43:09 GMT
Lines: 87

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