Permutations but with some numbers kept in an order

Question

Ok, I have had a browse around and I have looking for either a C or python solution to this problem. I would prefer python...although it is my weaker language (of 2 very weak languages).

A set of numbers, such as 0 0 1 7 0 0 3 0 0 4

1. Find all permutations of the set.
2. The numbers >0 must stay in that order (NOT POSITION!)
3. There MUST be a 0 between numbers, a 0 is not required at the start and end of the set though. As long as there is AT LEAST ONE 0 between numbers >0.

So firstly, I thought of just finding all possible permutations and then removing the chaff (checking that if n>0 , !n+1>0) for each permutation and then the first number >0 == 1, 2nd # >0 ==7 etc. etc.

I then stopped and thought that was daft, say there were 12 numbers, that would give 12! permutations. This in the order of 500,000,000 permutations of which I would have to run through again to get rid of chaff.

Say I had 40-50 sets of these number sets to go through, that is a fair whack of time.

Is there a more logical way? I thought of somehow having python do permutations somehow taking those rules in to account (if n>0, n+1 MUST == 0) and (n=first number, n2=2nd etc.)

An example of a smaller set would be (NOT ALL PERMUTATIONS, but gives idea):

1,2,3,0,0,0,0,0

1. 1,0,2,0,3,0,0,0
2. 0,1,0,2,0,3,0,0
3. 0,0,1,0,2,0,3,0
4. 0,0,1,0,0,2,0,3
5. 0,1,0,0,2,0,3,0

etc. etc. So 1,2,3 is in order but the "0"s are just shifted about?

Thanks!

Answer 1

Basically you want to reduce the number of combinations you have to compute by grouping things according to their invariants. Since the non-zero numbers must be in a fixed order let's start with that:

   1 2 3

Since there must be 0's between them add them in

   1 0 2 0 3

Now what you are left with is three 0's to place and you need to figure how many combinations give distinct sequences. Clearly from this example the possible positions you have are: before the 1, between the 1 and 2, between the 2 and 3 and after the 3. You have 4 positions in which to decide how to split up the remaining three 0's. This is a combination problem with repetition, for which the solution here is (3 + 4 - 1) Choose 3 (which is 20).

Hopefully the way that I went through this example problem is enough for you to generalize this to arbitrary sequences, so I will leave that as an exercise to the reader.