1

I am developing a probability analysis program for a board game. As part of an algorithm* I need to calculate the possible permutations of partitions of a number (plus some padding), such that all partition components cannot occupy any position that is lower than the total length of the permutation, in digits, minus the value of the component.

(It is extremely unlikely, however, that the number that will be partitioned will ever be higher than 8, and the length of the permutations will never be higher than 7.)


For instance, say I have the partition of 4, "211", and I want to find the permutations when there is a padding of 2, i.e. length of 5:

0 1 2 3 4 (array indexes)

5 4 3 2 1 (maximum value of partition component that can be allocated to each index)

2 1 1 _ _ (the partition plus 2 empty indexes)

This is represented as an array like so {2,1,1,0,0}

There are 6 permutations when 2 is in the 0 index (4! / 2! 2!), and there are 4 indexes that 2 can occupy (2 cannot be placed into the last index) so overall there are 24 permutations for this case (a 1 can occupy any index).

The output for input "21100":

21100, 21010, 21001, 20110, 20101, 20011

02110, 02101, 02011, 12100, 12010, 12001

00211, 10210, 11200, 10201, 01210, 01201

10021, 01021, 00121, 11020, 10120 01120

Note that this is simply the set of all permutations of "21100" minus those where 2 is in the 4th index. This is a relatively simple case.


The problem can be described as combining n different permutation groups, as the above case can be expressed as the combining of the permutations of x=1 n=4 and those of x=2 n=5, where x is the value count and n is the "space" count.

My difficulty is formulating a method that can obtain all possibilities computationally, and any advice would be greatly appreciated. -Please excuse any muddling of terminology in my question.


*The algorithm answers the following question:

There is a set of n units that are attacked k times. Each attack has p chance to miss and q (1 - p) chance to damage a random unit from the set. A unit that is damaged for a second time is destroyed and is removed from the set.

What is the probability of there being x undamaged units, y damaged units and z destroyed units after the attacks?

If anyone knows a more direct approach to this problem, please let me know.

Bergi
  • 630,263
  • 148
  • 957
  • 1,375
Tom
  • 11
  • 3
  • 1
    I'm a TA in combinatorics, and I still didn't understand your question, can you please try to formally define your input and expected output better? – amit Mar 19 '15 at 11:03
  • A bulleted list of each rule/criteria for a valid permutation (for example, "xyz numbers cannot be placed in the last index" would be one) is probably the best way to do this. – Alex Mar 19 '15 at 11:11
  • 1
    One thing that is unclear is the placement condition. I cannot see how "numbers cannot be placed into any index that is lower than length-number-1" translates to "2 cannot be placed into the last index". – Rafał Dowgird Mar 19 '15 at 11:32
  • @Tom: I really think you need to be more precise with your terminology. Make sure that you use `number` and `digit` correctly in the question and `length-number-1` is not very clear. – Matt Ko Mar 19 '15 at 12:57
  • I added some further explanation and tried to standardise my iffy syntax, if you would please take another look. – Tom Mar 19 '15 at 19:28
  • Please let me know anyone if I can clarify anything further. – Tom Mar 21 '15 at 11:40

1 Answers1

0

I am going to use the algorithm to generate all permutations of the multiset as given in the answer to this question

How to generate all the permutations of a multiset?

and then filter to fit my criteria.

Tom
  • 11
  • 3