Permutation Counting Problem

I get 2016 (with the permutations generator I just published) but finding a general formula seems not so easy

Dirk Vdm

Dirk,

How did you find this result? Counting all possible permutations?

I made a little program to run through the permutations, counting only the ones with no adjacent equals Look at thread 'Permutation algorithm for list with duplcate numbers' in sci.math. It appeared the day before you posted your puzzle. Meanwhile Lutz Tautenhahn has created a little java script to list all the *normal* permutations. The script can easily be adapted to: - either list or count - allow adjacent equals or not. If you ask her/him, I'm sure she/he will gladly adapt her/his script

Dirk Vdm

Can you give some more information about this generator? Is it online? Is it an algorithm or computer code?

Here's another possible way of doing it, if you've got a C++ compiler with stl.

#include <algorithm>

char str[] = &#039;MISSISSIPPI&#039;; char *begin = &amp;str[0], *end = &amp;str[strlen(str)]; sort(begere's another possible way of doing it, if you've got a C++ compiler with stl.

#include <algorithm>

char str[] = 'MISSISSIPPI'; char *begin = &str[0], *end = &str[strlen(str)]; sort(begin,end); int permutations = 1; while( next_permutation(begin,end) ) ++permutations;

NB: This code is untested.

[snip]

stoopid, should be IIIIMPPSSSS (for MISSISSIPPI) what a dreadful word

Dirk Vdm

[VB program snipped]

Here's a C program that also computes 2016. It runs in about 2.6/r seconds on my r-GHz Pentium.

/* generate permutations in lexicographic order using an algorithm due to Dijkstra, and count certain ones. jiw Compile permuteMS with gcc -O6 permuteMS.c -o permuteMS */

#include <stdio.h> #include <stdlib.h> #define n 11

int main() { int i, j, k=0, r, s, temp; int pi[n+1]; char *MS = ' MISSISSIPPI';

for (i=0; i <= n; i++) pi[i] = i;

i = 1; while (i) {

// Do something with this permutation for (i=1; i < n; i++) if (MS[pi[i]]

Actually, it is not too hard to figure this out without a computer, although I personally probably wouldn't have found all my mistakes if Dirk hadn't published the right answer.

There are 8C4 = 70 ways to interleave the S's and I's. Of these, there are 2, 6, 18, 18, 18, 6 and 2 ways to do it in 8 through 2 'groups' of identical letters, respectively. These numbers are obtained by multiplying the 2 choices for which number goes first by the 3C(4-g) ways of dividing the 4-g 'extra' characters of each type into the g groups, since we must have at least one character in each group. Thus, for example, there are 2*3C1*3C2 = 18 ways of interleaving the S's and I's into 5 groups.

If we have 8-r groups, so that r is the number of repeats, we must put r of the MP's into the gaps, and we are then left with 11-r places (other than the first spot of a gap) to put the next MP, 10-r for the one after that for a total of (11-r)C(3-r) ways to place the MPs, which should be multiplied by the 3 ways to choose which is the M. We must then subtract that number of ways which leave the two Ps together, which is just the number of ways to place to distinct letters while breaking up r repeats: 2*(10-r)C(2-r).

So we have:

8 groups: 3*11C3 - 2*10C2 = 405; 405*2=810 7 groups: 3*10C2 - 2*9C1 = 117; 117*6=702 6 groups: 3*9C1 - 2 = 25; 25*18 = 450 5 groups: 3 = 3; 3*18 = 54.

This in fact adds up to 2106.

I will also append a C program that counts (and prints) these combinations. It seems to be hundreds of times faster than the earlier-posted C program (at least on my machine), probably because it treats equivalent letters as equivalent, and also breaks off permutations when it gets stuck.

Jonathan Dushoff

Jonathan, your code work very well, but how could make a faster code just to count using their formulas?

Can anybody explain to me how to jon found these results?

Thanks,

Basically, I am first calculating how many different ways there are to put the 4 S's and I's in any order and with a certain number of repeats. Then I am multiplying each by the number of ways each allows for putting 2 P's and an M to end with no repeated letters.

There are 2 ways to write the S's and I's with no repeats (one is 'SISISISI'. For each of these ways there are then 405 ways to add the M and P's (for example 'SPIPSISMISI'.

There are 6 ways to write them with one repeat (one is 'SISIISIS'. For each of these ways there are then 117 ways to add the M and P's (for example 'SPIPSIMISIS'. There are a lot fewer ways because you have to separate the repeated letters.

There are 18 ways to write them with two repeats, but each of these only leaves 25 ways to place the M and P's.

Finally, there are 18 ways to write them with three repeats, which only leaves 3 ways to place the M and P's.

If you write them with more than three repeats, the M and P's can't be placed.

Thus the total number of ways is 2*405 + 6*117 + 18*25 + 18*3. There are details about how I calculated each of those eight numbers in the original post (repeated below). C refers to the choose function: nCk = n!/(k!(n-k)!).

I hope this is helpful.

Jonathan Dushoff

(I earlier wrote the following