[comp.lang.c] ** Some Help Please **

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