2

I am programmer and have developed an algorithm to run a processor intensive function on all the permutations of 2 letters (X and O) when we define how many X's and O's there will be.

For example, I may run F(10, 5) which would run all the permutations of length 15 with 10 X's and 5 O's. If I ran F(4,5) it would run all the permutations of length 9 with 4 X's and 5 O's. See below for example I did quite a bit of research, and everything I found to calculate this would allow for any amount of X's or O's. That formula would be 2^n where N is the total length. This is not what I need because I specify the amount of X's and O's.

I also found the n! / (n - r)!r! formula but that is completely wrong because I have a defined length.

I also found "derangement" but have no clue what I am looking at or how to apply it to my use case (if it even applies). Derangement on MathWorld

The reason I want to calculate the total number is so I can give a progress bar and estimated time remaining. Obviously this is not needed, but I am running permutations like F(10,20) which has millions, if not billions of permutations and they can take quite a long time. It would be great to know how far and how many left there are to run.

I am at a loss as to how to come up with the formula needed. Maybe it is obvious and you can just point out something obvious I am missing. I thought I may try to use 2^N - (all the permutations of 2^N which do not have the correct number) but then I am back to original problem with trying to figure how many permutations do not have the correct number.

I can post the entire algorithm I use to calculate all the possible permutations if that would assist in coming up with a formula to calculate the total number of permutations.

Example Data

If I run F(2, 3) it would run:

XXOOO
XOXOO
OXXOO
XOOXO
OXOXO
OOXXO
XOOOX
OXOOX
OOXOX
OOOXX

So, F(2, 3) has 10 permutations.

If I run F(3, 3) it would run:

XXXOOO
XXOXOO
XOXXOO
OXXXOO
XXOOXO
XOXOXO
OXXOXO
XOOXXO
OXOXXO
OOXXXO
XXOOOX
XOXOOX
OXXOOX
XOOXOX
OXOXOX
OOXXOX
XOOOXX
OXOOXX
OOXOXX
OOOXXX

So, F(3, 3) has 20 permutations.

mrkmg
  • 21
  • 1
    The formula you rejected is correct. In your notation, $F(a,b)=\frac{(a+b)!}{a!b!}$. There are other equivalent versions which may be computationally more convenient. – André Nicolas Feb 27 '15 at 16:24
  • Ahh, I see. Thank you! – mrkmg Feb 27 '15 at 16:35
  • The rest of your question is quite interesting. I think of it as finding a way of listing the permutations of $a$ X's and $b$ O's in a systematic way so that you have a "nice" estimate of how far a particular permutation is in the list. I believe I have seen such nice enumerations. I hope that someone knowledgeable about such things will give an answer that lets you produce a good "progress bar.' – André Nicolas Feb 27 '15 at 16:43
  • The output you see in the example data is the output from the actual algorithm. I plugged in the formula and it worked! I am showing estimated time left now and all is good. Thank you again so much! – mrkmg Feb 27 '15 at 16:59
  • Now that you know how to compute the total count $|F(a,b)=\frac{(a+b)!}{a!,b!}$, could you simply add a running count and consider the ratio (running count)/(total count)? – Laars Helenius Feb 27 '15 at 17:18
  • 1
    @LaarsHelenius That is what I did. – mrkmg Mar 16 '15 at 18:27

0 Answers0